Best Time to Buy and Sell Stock II

Medium

Apple

19 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<sup>th</sup> 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. Let's walk through a few examples.

Example 1: prices = [7,1,5,3,6,4]

Here's how one might derive the answer:

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: prices = [1,2,3,4,5]

Here's how one might derive the answer:

Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3: prices = [7,6,4,3,1]

Here's how one might derive the answer:

There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

With these examples in mind, how would you go about implementing the function to find the maximum profit?

Best Time to Buy and Sell Stock II

Medium

Apple

19 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<sup>th</sup> 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. Let's walk through a few examples.

Example 1: prices = [7,1,5,3,6,4]

Here's how one might derive the answer:

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: prices = [1,2,3,4,5]

Here's how one might derive the answer:

Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3: prices = [7,6,4,3,1]

Here's how one might derive the answer:

There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

With these examples in mind, how would you go about implementing the function to find the maximum profit?

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 is the range of values for the stock prices in the `prices` array? Can they be negative, zero, or very large?
What should I return if the `prices` array is empty or contains only one element?
Are there any restrictions on the number of transactions I can make on a given day (e.g., can I buy and sell on the same day)?
Can I only hold one share of the stock at a time, or can I buy multiple shares before selling?
Is the input array guaranteed to be valid (e.g., no null values)? Are there any other potential edge cases I should be aware of?

Brute Force Solution

Approach

To find the most profit from stock trades, the brute force method considers every single possible combination of buying and selling. It's like going through every 'what if' scenario to see which one makes the most money. We’ll check all buy/sell options to determine the maximum profit.

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

Start by considering you don't do any transaction at all, calculating the profit if you simply don't buy or sell.
Then, explore buying on the first day and selling on any of the later days, calculating the profit from each potential sale.
Next, explore buying on the second day, and selling on any day after that, calculating profits accordingly.
Continue this pattern, considering buying on each possible day, and then selling on any later day.
After exploring single buy and sell options, consider multiple transactions. For example, buy on day one, sell on day two, then buy again on day three and sell on a later day. Explore all such combinations of multiple transactions.
For each possible set of transactions you consider, calculate the total profit.
Finally, compare the profits from all the different scenarios and pick the one with the highest profit. This is the maximum profit you could have made.

Code Implementation

def max_profit_brute_force(prices):
    def calculate_max_profit(prices, start_day):
        # Base case: If we reach the end of the list, there's no profit
        if start_day >= len(prices):
            return 0

        max_profit = 0

        for current_day in range(start_day, len(prices)):
            max_profit_from_current_day = 0
            # Try selling on each day after the current day
            for selling_day in range(current_day + 1, len(prices)):
                if prices[selling_day] > prices[current_day]:
                    # Calculate profit from this transaction
                    current_profit = prices[selling_day] - prices[current_day]
                    # Recursively calculate profit from future transactions after selling.
                    current_profit += calculate_max_profit(prices, selling_day + 1)
                    max_profit_from_current_day = max(max_profit_from_current_day, current_profit)

            max_profit = max(max_profit, max_profit_from_current_day)

        return max_profit

    # Start the calculation from the beginning of the price list.
    return calculate_max_profit(prices, 0)

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of buying and selling stocks. For each day, we have two choices: either buy/sell the stock or do nothing. This decision tree branches out for each day, leading to an exponential number of possibilities. Specifically, for n days, there are approximately 2^n possible scenarios to consider. Thus, the time complexity is O(2^n).

Space Complexity

O(N^N) – The brute force approach explores all possible combinations of buy and sell transactions, potentially involving multiple recursive calls. The depth of the recursion could, in the worst-case scenario, reach N, and at each level, there could be multiple branches representing different transaction options. The number of possible combinations grows exponentially, potentially leading to a recursion tree where each node stores the current profit and transaction history. Therefore, the auxiliary space required to store the call stack and intermediate results grows exponentially with the input size N, resulting in O(N^N) space complexity, where N is the number of days (prices).

Optimal Solution

Approach

The goal is to make as much profit as possible by buying and selling stock. The optimal strategy focuses on identifying every profitable rise in stock price and capitalizing on it immediately, instead of trying to predict larger, potentially missed gains.

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

Go through the stock prices one day at a time.
If the price today is higher than the price yesterday, then buy the stock yesterday and sell it today. This gives you a profit.
If the price today is not higher than the price yesterday, then don't do anything, just wait for the next day.
Keep doing this for every day's price.
At the end, add up all the profits you made from each buy and sell.
This total is the maximum profit you can get.

Code Implementation

def max_profit_from_stock(prices):
    max_profit = 0
    
    # Iterate through the prices starting
    # from the second day.
    for i in range(1, len(prices)):

        # Check if today's price is higher
        # than yesterday's price.
        if prices[i] > prices[i - 1]:

            # If it is, calculate the profit
            # and add it to the total profit.
            profit = prices[i] - prices[i - 1]
            max_profit += profit

    return max_profit

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of stock prices exactly once. For each day's price, it performs a constant-time comparison with the previous day's price. The number of comparisons is directly proportional to the number of days (n). Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm calculates the profit by iterating through the stock prices and comparing the current day's price to the previous day's price. It only uses a single variable to accumulate the total profit. No additional data structures, like arrays or hash maps, are created that scale with the input size N (the number of stock prices). Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Empty input array	Return 0, as no transactions are possible with no prices.
Array with only one price	Return 0, as a single day doesn't allow for a buy and sell.
Prices are in strictly decreasing order	Return 0, as there are no profitable buying opportunities.
Prices are in strictly increasing order	Calculate profit as price[n-1] - price[0], effectively buying on day 0 and selling on day n-1.
Array with duplicate consecutive prices	The algorithm should correctly ignore consecutive days with same prices, only considering price changes.
Large input array leading to potential integer overflow in profit calculation	Use a data type that can accommodate large profits (e.g., long long in C++ or long in Java) or handle potential overflow with checks.
Input array with very small price fluctuations	The algorithm should still work correctly, summing all positive price differences.
Input array with very large price fluctuations	The algorithm should still work correctly, summing all positive price differences assuming there is no overflow.