Best Time to Buy and Sell Stock V

Medium

Asked by:

11 views

Topics:

ArraysDynamic Programming

You are given an integer array prices where prices[i] is the price of a stock in dollars on the i^th day, and an integer k.

You are allowed to make at most k transactions, where each transaction can be either of the following:

Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].
Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most k transactions.

Example 1:

Input: prices = [1,7,9,8,2], k = 2

Output: 14

Explanation:

We can make $14 of profit through 2 transactions:

A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

Example 2:

Input: prices = [12,16,19,19,8,1,19,13,9], k = 3

Output: 36

Explanation:

We can make $36 of profit through 3 transactions:

A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

Constraints:

2 <= prices.length <= 10³
1 <= prices[i] <= 10⁹
1 <= k <= prices.length / 2

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can I perform multiple transactions (buy and sell multiple times) within the given price array, or am I limited to just one transaction?
Are there any transaction fees or constraints on the number of transactions I can make?
If no profit can be made (i.e., the prices are always decreasing), what should the function return? Should it return 0, null, or throw an exception?
Can the input array be empty, or contain null values, and if so, how should I handle those cases?
Are there any constraints on how close the buy and sell days need to be? Could I buy and sell on the same day?

Brute Force Solution

Approach

The brute force method in this case means trying every single possible combination of buy and sell actions. We want to explore all possible trading strategies to find the one that gives us the maximum profit, no matter how inefficient.

Here's how the algorithm would work step-by-step:

First, consider every single day as a potential day to buy the stock.
For each of those buy days, consider every day AFTER it as a potential day to sell the stock.
Calculate the profit for each of these buy and sell combinations (sell price minus buy price).
Next, consider making multiple transactions. So, after each sell day, explore further buying opportunities from the next day onwards.
Keep track of the total profit for each sequence of buy and sell actions that you tried.
After exploring ALL possible sequences of buying and selling, compare the total profits from all the sequences.
Finally, select the sequence that resulted in the highest overall profit. That's your best possible profit.

Code Implementation

def best_time_to_buy_and_sell_stock_v_brute_force(prices):
    max_profit = 0
    number_of_days = len(prices)

    def calculate_max_profit(start_day, current_profit):
        nonlocal max_profit

        if start_day >= number_of_days:
            max_profit = max(max_profit, current_profit)
            return

        # Explore the option of not making any transaction
        max_profit = max(max_profit, current_profit)

        for buying_day in range(start_day, number_of_days):
            for selling_day in range(buying_day + 1, number_of_days):
                profit = prices[selling_day] - prices[buying_day]

                # Explore further transactions after this sell
                calculate_max_profit(selling_day + 1, current_profit + profit)

    # Begin exploring all possible transaction sequences
    calculate_max_profit(0, 0)

    return max_profit

Big(O) Analysis

Time Complexity

O(n^k) – The described brute force approach explores all possible combinations of buy and sell days, including multiple transactions. In the worst case, for each day, we consider it as a buy day and then iterate through all subsequent days as potential sell days. After each sell, we recursively explore further buy/sell opportunities from the next day onwards. The depth of this recursion can be up to n, representing multiple transactions. Therefore, the complexity is exponential with respect to the input size, 'n', and the number of possible transactions, let's say 'k', hence O(n^k), where k can grow close to n.

Space Complexity

O(N^N) – The brute force method, as described, explores every possible combination of buy and sell actions, including multiple transactions. This implies a recursive exploration of the decision tree where at each step (day), we can either buy, sell, or do nothing. In the worst-case scenario, where we make transactions on nearly every day, the depth of the recursion could be proportional to N (number of days), and at each level, we may need to store intermediate profits for the subsequence of buy and sell actions we have taken. This could lead to the space needed to store all the possible intermediate profit values during the exploration, thus leading to an exponential relationship with N. Therefore, the space used for call stack and storing intermediate profits could grow exponentially, up to O(N^N).

Optimal Solution

Approach

The best strategy is to keep track of potential opportunities to profit. We aim to capture all positive price differences to maximize earnings, without actually buying and selling on the same day. Think of it as finding all the upswings and summing them up.

Here's how the algorithm would work step-by-step:

Start at the beginning of the price list.
Look for every day where the price is higher than the previous day.
If a day's price is higher, treat it as a profitable transaction and add the difference to your total profit.
If a day's price is not higher, ignore it.
Continue doing this for every day in the list.
The final total profit is the best you can do by buying and selling as many times as you want.

Code Implementation

def max_profit(prices):
    maximum_total_profit = 0
    
    # Iterate through prices to find profitable transactions
    for i in range(1, len(prices)):
        # Check if the current day's price is higher
        if prices[i] > prices[i - 1]:
            # Add the difference to the total profit
            maximum_total_profit += prices[i] - prices[i - 1]

    return maximum_total_profit

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the price list once, examining each day's price to determine if it's higher than the previous day's price. This comparison operation is performed for each element in the input array. Therefore, the time complexity is directly proportional to the number of days (n), resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the input price list but doesn't create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited elements. It only uses a constant number of variables to store the running total profit. Thus, the space used remains constant irrespective of the input size N (the number of days), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
prices is null or empty	Return 0 immediately as no transaction is possible.
prices array contains only one element	Return 0 immediately as no transaction is possible.
prices array is very large (performance considerations)	Ensure algorithm has optimal time complexity, such as O(n), to avoid timeouts.
prices array contains all identical values	Return 0 as no profit can be made.
prices array contains only decreasing values	Return 0 as no profit can be made.
prices array contains negative values (invalid price)	Throw an IllegalArgumentException or handle it based on requirements.
prices array causes integer overflow when calculating profit	Use a larger data type like long to store profit.
The prices array contain consecutive increasing prices.	Sum the daily increases in stock price to find the profit.

prices is null or empty

How to Handle:

Return 0 immediately as no transaction is possible.

prices array contains only one element

How to Handle:

Return 0 immediately as no transaction is possible.

prices array is very large (performance considerations)

How to Handle:

Ensure algorithm has optimal time complexity, such as O(n), to avoid timeouts.

prices array contains all identical values

How to Handle:

Return 0 as no profit can be made.

prices array contains only decreasing values

How to Handle:

Return 0 as no profit can be made.

prices array contains negative values (invalid price)

How to Handle:

Throw an IllegalArgumentException or handle it based on requirements.

prices array causes integer overflow when calculating profit

How to Handle:

Use a larger data type like long to store profit.

The prices array contain consecutive increasing prices.

How to Handle:

Sum the daily increases in stock price to find the profit.