Problem Statement

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Additional information

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Example 1:

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

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

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

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Brute Force

Intuition

The most straightforward way to find the maximum profit is to calculate the profit for every possible pair of buy and sell days. We can iterate through every day i to buy, and for each i, iterate through every subsequent day j to sell. We track the maximum difference prices[j] - prices[i].

Algorithm

1. Initialize max_profit to 0.

2. Iterate i from 0 to n-1 (Buy Day).

3. Iterate j from i + 1 to n-1 (Sell Day).

4. Calculate profit = prices[j] - prices[i].

5. If profit is greater than max_profit, update max_profit.

6. Return max_profit.

def max_profit(prices: list[int]) -> int:
    max_p = 0
    n = len(prices)
    
    for i in range(n):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            if profit > max_p:
                max_p = profit
                
    return max_p

Time & Space Complexity

• Time complexity: O(n^2)

  • Reason: We use two nested loops to check all pairs.

• Space complexity: O(1)

  • Reason: We only use a single variable to store the max profit.

Two Pointers (Sliding Window)

Intuition

We initialize the Left pointer (l) at day 0 (buy) and the Right pointer (r) at day 1 (sell).

• If prices[l] < prices[r], we have a profit. We check if this is the max profit so far. Then we move our sell day (r) forward to see if we can sell higher later.

• If prices[l] >= prices[r], it means we found a price lower than our buying price. It never makes sense to keep the old buy day. We act "greedy" and move our buy pointer l to the current index r.

Algorithm

1. Initialize l = 0 and r = 1.

2. While r < len(prices):

   • If prices[l] < prices[r]:

     • Calculate profit = prices[r] - prices[l].

     • Update max_profit.

   • Else:

     • Move l to r (we found a new lowest valley).

   • Increment r.

def max_profit(prices: list[int]) -> int:
    l, r = 0, 1 # Left=Buy, Right=Sell
    max_p = 0
    
    while r < len(prices):
        if prices[l] < prices[r]:
            profit = prices[r] - prices[l]
            max_p = max(max_p, profit)
        else:
            l = r # Shift buy pointer to the new minimum found
        r += 1
        
    return max_p

Time & Space Complexity

• Time: $O(n)$ - We scan the array once.

• Space: $O(1)$ - Only two pointers are used.