Best Time to Buy and Sell Stock II

Medium

Apple

28 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

1 <= prices.length <= 3 * 10⁴
0 <= prices[i] <= 10⁴

Best Time to Buy and Sell Stock II

Medium

Apple

28 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

1 <= prices.length <= 3 * 10⁴
0 <= prices[i] <= 10⁴

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:

What are the possible ranges for the stock prices (prices[i]) and the length of the prices array?
Can the prices array be empty? If so, what should I return?
Is it possible for stock prices to be non-integers (e.g., floats)?
Can I buy and sell stock on the same day (if the price remains constant)?
If no transactions are possible that yield a profit, what value should I return?

Brute Force Solution

Approach

The problem is about finding the maximum profit from buying and selling a stock, allowing multiple transactions. The brute force strategy explores every single possible sequence of buy and sell actions. It checks all combinations to find the one with the highest profit.

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

Imagine you can either buy or sell the stock on each day, or do nothing.
Start by considering you do nothing on the first day. See what happens if you only start buying or selling on the second day and so on.
For each of those cases, consider every possible action you can take on the next day: buy, sell, or nothing.
Continue doing this for every day, building out a huge tree of possibilities. Each path from the top of the tree to the bottom represents a different series of buying and selling decisions.
For each of these paths (series of decisions), calculate the total profit you would make if you followed that particular buying and selling strategy.
Once you've considered every single path, compare all the profits you calculated.
The largest profit among all the paths is the answer.

Code Implementation

def max_profit_brute_force(prices):
    def calculate_max_profit(prices, current_index, holding_stock):
        # Base case: reached the end of the prices list
        if current_index >= len(prices):
            return 0

        # Option 1: Do nothing on this day
        profit_if_do_nothing = calculate_max_profit(prices, current_index + 1, holding_stock)

        profit_if_buy = 0
        profit_if_sell = 0

        #If not holding, can consider buying
        if not holding_stock:
            profit_if_buy = -prices[current_index] + calculate_max_profit(prices, current_index + 1, True)

        #If holding, can consider selling
        else:
            profit_if_sell = prices[current_index] + calculate_max_profit(prices, current_index + 1, False)

        return max(profit_if_do_nothing, profit_if_buy, profit_if_sell)

    # Initiate recursion.
    # Start from the beginning with no stock.
    return calculate_max_profit(prices, 0, False)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores every possible combination of buy and sell decisions for each day. Each day offers a choice: buy, sell, or do nothing. With n days, this leads to 3^n possible decision paths. However, a more accurate analysis considering only buy or sell (or do nothing) results in a branching factor of approximately 2 for each day after the initial day, leading to approximately 2^(n-1) or simply 2^n possible scenarios. Therefore, the time complexity grows exponentially with the number of days, resulting in O(2^n).

Space Complexity

O(N) – The brute force solution described explores every possible sequence of buy/sell actions using a decision tree. The depth of this tree can be N in the worst case, where N is the number of days (prices in the input). Each level of the tree represents a recursive call, and each call stores its own local variables and state. Therefore, the maximum call stack depth due to recursion is proportional to N, resulting in O(N) auxiliary space complexity.

Optimal Solution

Approach

The key idea is to maximize profit by buying low and selling high whenever possible. We don't need to find the absolute lowest buy price and highest sell price overall; we can simply accumulate profits from all the increasing price intervals.

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

Imagine you're walking through the prices day by day.
If the price tomorrow is higher than today, buy today and sell tomorrow. This gives you a profit.
If the price tomorrow is lower than today, don't do anything today. Wait for a better opportunity.
Keep doing this day by day. Add up all the profits you made from buying low and selling high.
The total profit you've accumulated will be the maximum profit you can make.

Code Implementation

def max_profit(prices):
    maximum_profit = 0

    # Iterate through the prices, starting from the second day
    for i in range(1, len(prices)):
        # Check if the current day's price is higher than the previous day's price
        if prices[i] > prices[i - 1]:
            # Accumulate profit if today's price exceeds yesterday's.
            maximum_profit += prices[i] - prices[i - 1]

    # Return the maximum profit that can be obtained
    return maximum_profit

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the array of prices once, comparing each day's price with the next day's price. The number of iterations is directly proportional to the number of days, n, represented by the input array's size. Each comparison and potential profit calculation takes constant time. Therefore, the overall time complexity is linear with respect to the input size n.

Space Complexity

O(1) – The provided strategy only involves iterating through the prices and accumulating profit. It doesn't require creating any additional data structures like arrays, hash maps, or trees to store intermediate results or track visited states. The space used is therefore independent of the input size, N, where N is the number of prices. The space complexity is constant because only a few variables (like the current profit) are used, regardless of how large the input array becomes.

Edge Cases

Case	How to Handle
Empty or null 'prices' array	Return 0 as no profit can be made with no prices.
'prices' array with only one element	Return 0 as no transaction (buy and sell) can occur.
'prices' array with two elements, decreasing order	Return 0 as there is no opportunity to make a profit (price decreased).
'prices' array with all identical values	Return 0 as there's no price fluctuation, so no profit.
'prices' array with monotonically increasing values	The algorithm should correctly sum the differences between consecutive days to maximize profit in this ideal scenario.
'prices' array with monotonically decreasing values	The algorithm correctly returns zero profit since no transaction is profitable.
'prices' array with a mix of increasing and decreasing values, large range	Greedy approach correctly accumulates profits from all increasing subsequences.
Large 'prices' array with integer overflow potential in profit calculation (if using certain languages)	Use appropriate data types (e.g., long) to prevent integer overflow during profit calculation, or use modulo if relevant.