Problem Description

You are given an array prices where prices[i] represents the price of a stock on day i.

Your goal is to find the maximum profit you can make by:

1. Buying the stock on exactly one day
2. Selling the stock on a different day in the future (after the buy day)

You need to return the maximum profit possible from this single buy-sell transaction. If no profit can be made (for example, if prices only decrease), return 0.

Key constraints:

• You must buy before you sell (the sell day must come after the buy day)
• You can only make one transaction (one buy and one sell)
• You cannot buy and sell on the same day

Example scenarios:

• If prices = [7, 1, 5, 3, 6, 4], the maximum profit would be 5 (buy at price 1 on day 2, sell at price 6 on day 5)
• If prices = [7, 6, 4, 3, 1], the maximum profit would be 0 (prices keep decreasing, so no profit is possible)

The solution maintains a running minimum price (mi) as it iterates through the array, and for each price, calculates the potential profit if selling at that price. The variable ans keeps track of the maximum profit found so far. The algorithm efficiently finds the best buy-sell pair in a single pass through the array with O(n) time complexity.

Intuition

To maximize profit, we want to buy at the lowest price and sell at the highest price, but with the constraint that the sell day must come after the buy day.

A naive approach would be to check every possible pair of buy and sell days, which would take O(n²) time. However, we can make a key observation: for any given selling day, the best buying day would always be the day with the minimum price before it.

Think about it this way - if we're selling on day i, we want to buy at the cheapest price from days 0 to i-1. We don't need to check all previous days individually; we just need to know what the minimum price was up to that point.

This leads us to the insight that we can solve this problem in a single pass:

• As we iterate through each day, we consider it as a potential selling day
• For each potential selling day, we calculate the profit using the minimum price we've seen so far as the buying price
• We keep track of the maximum profit we can achieve

The brilliance of this approach is that we're simultaneously:

1. Tracking the minimum price seen so far (mi)
2. Calculating the profit if we sell at the current price (v - mi)
3. Updating our answer with the maximum profit found (ans = max(ans, v - mi))

By maintaining the running minimum, we avoid redundant comparisons and reduce the time complexity from O(n²) to O(n). Each price is examined only once, either as a potential buying price (updating mi) or as a selling price (calculating profit).

Solution Approach

The solution uses a single-pass greedy algorithm with two variables to track the minimum price and maximum profit.

Algorithm Steps:

1. Initialize variables:

   • ans = 0: Stores the maximum profit found so far (initially 0 since we haven't made any transactions)
   • mi = inf: Stores the minimum price seen so far (initialized to infinity so any price will be smaller)

2. Iterate through each price in the array:

   for v in prices:

   For each price v, we treat it as a potential selling price.

3. Calculate potential profit:

   ans = max(ans, v - mi)

   • Calculate the profit if we sell at current price v and bought at the minimum price mi seen so far
   • Update ans only if this profit is greater than the current maximum profit
   • The expression v - mi gives us the profit (selling price - buying price)

4. Update minimum price:

   mi = min(mi, v)

   • After considering v as a selling price, we now consider it as a potential buying price for future transactions
   • Update mi if the current price v is lower than the previous minimum

5. Return the result:

   return ans

   • After processing all prices, ans contains the maximum profit possible

Why this works:

The algorithm maintains the invariant that at each position i, we know:

• The minimum price from positions 0 to i-1 (stored in mi)
• The maximum profit achievable from positions 0 to i (stored in ans)

By updating these values in the correct order (first calculate profit, then update minimum), we ensure that we never "buy and sell on the same day" since we use the minimum from previous days to calculate today's potential profit.

Time Complexity: O(n) - single pass through the array
Space Complexity: O(1) - only using two variables regardless of input size

Example Walkthrough

Let's walk through the algorithm with prices = [7, 1, 5, 3, 6, 4]:

Initial State:

• ans = 0 (no profit yet)
• mi = inf (no minimum price seen yet)

Day 0 (price = 7):

• Calculate profit: ans = max(0, 7 - inf) → ans = 0 (can't have negative infinity as buy price)
• Update minimum: mi = min(inf, 7) → mi = 7
• State: ans = 0, mi = 7

Day 1 (price = 1):

• Calculate profit: ans = max(0, 1 - 7) → ans = max(0, -6) → ans = 0 (no profit if we sell at 1 after buying at 7)
• Update minimum: mi = min(7, 1) → mi = 1 (found a better buying price!)
• State: ans = 0, mi = 1

Day 2 (price = 5):

• Calculate profit: ans = max(0, 5 - 1) → ans = max(0, 4) → ans = 4 (profit of 4 if we buy at 1 and sell at 5)
• Update minimum: mi = min(1, 5) → mi = 1 (keep the lower price)
• State: ans = 4, mi = 1

Day 3 (price = 3):

• Calculate profit: ans = max(4, 3 - 1) → ans = max(4, 2) → ans = 4 (current best profit is still 4)
• Update minimum: mi = min(1, 3) → mi = 1
• State: ans = 4, mi = 1

Day 4 (price = 6):

• Calculate profit: ans = max(4, 6 - 1) → ans = max(4, 5) → ans = 5 (new best profit!)
• Update minimum: mi = min(1, 6) → mi = 1
• State: ans = 5, mi = 1

Day 5 (price = 4):

• Calculate profit: ans = max(5, 4 - 1) → ans = max(5, 3) → ans = 5 (keep the best profit)
• Update minimum: mi = min(1, 4) → mi = 1
• State: ans = 5, mi = 1

Final Result: ans = 5

The algorithm correctly identifies that buying at price 1 (day 1) and selling at price 6 (day 4) gives the maximum profit of 5.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array prices. This is because the algorithm iterates through the prices array exactly once, performing constant-time operations (max, min, and arithmetic operations) for each element.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size - specifically, it maintains two variables ans and mi to track the maximum profit and minimum price seen so far.

Common Pitfalls

1. Updating minimum price before calculating profit

One of the most common mistakes is reversing the order of operations within the loop:

Incorrect Implementation:

def maxProfit(self, prices: List[int]) -> int:
    max_profit = 0
    min_price = float('inf')
  
    for current_price in prices:
        min_price = min(min_price, current_price)  # ❌ Updated BEFORE calculating profit
        max_profit = max(max_profit, current_price - min_price)
  
    return max_profit

Why this fails: If you update min_price first, when calculating the profit for the current day, you might be using the current day's price as both the buying and selling price, effectively allowing "same-day" transactions. This would always result in zero profit for that calculation.

Example where it fails:

• prices = [2, 1, 4]
• Incorrect approach: Returns 3 (incorrectly allows buying and selling at price 1)
• Correct approach: Returns 3 (buy at 1, sell at 4)

While this example gives the same answer, consider prices = [5] - the incorrect approach would return 0 (correct by coincidence), but the logic is fundamentally flawed.

2. Not handling edge cases properly

Potential Issues:

• Empty array or single-element array
• All prices are the same
• Prices only decrease

Solution:

def maxProfit(self, prices: List[int]) -> int:
    # Handle edge case explicitly
    if not prices or len(prices) < 2:
        return 0
  
    max_profit = 0
    min_price = prices[0]  # Can safely use first element instead of infinity
  
    for i in range(1, len(prices)):  # Start from index 1
        max_profit = max(max_profit, prices[i] - min_price)
        min_price = min(min_price, prices[i])
  
    return max_profit

3. Integer overflow concerns (in other languages)

While Python handles arbitrary precision integers, in languages like Java or C++, you might face overflow when using Integer.MAX_VALUE or INT_MAX as the initial minimum price.

Better initialization approach:

def maxProfit(self, prices: List[int]) -> int:
    if not prices:
        return 0
  
    max_profit = 0
    min_price = prices[0]  # Use first element instead of infinity
  
    for current_price in prices[1:]:  # Skip first element
        max_profit = max(max_profit, current_price - min_price)
        min_price = min(min_price, current_price)
  
    return max_profit

This approach avoids potential overflow issues and is more intuitive since the first price is a valid starting point for the minimum price.