Skip to content

259. Best Time to Buy and Sell Stock

šŸ”— LeetCode Problem: 121. Best Time to Buy and Sell Stock
šŸ“Š Difficulty: Easy
šŸ·ļø Topics: Array, Dynamic Programming, State Machines

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.

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.

Example 2: 

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No profit possible, return 0.

Constraints: - 1 <= prices.length <= 10^5 - 0 <= prices[i] <= 10^4

šŸ§’ Understanding The Problem (By Hand)

Let Me Work Example 1 Step By Step

prices = [7, 1, 5, 3, 6, 4]
          0  1  2  3  4  5  (indices)

Rule: Buy one day, sell a LATER day

Let me try all possible buy-sell pairs:

Buy day 0 (price=7):
  Sell day 1: 1 - 7 = -6 (loss)
  Sell day 2: 5 - 7 = -2 (loss)
  Sell day 3: 3 - 7 = -4 (loss)
  Sell day 4: 6 - 7 = -1 (loss)
  Sell day 5: 4 - 7 = -3 (loss)

Buy day 1 (price=1):
  Sell day 2: 5 - 1 = 4 āœ“
  Sell day 3: 3 - 1 = 2
  Sell day 4: 6 - 1 = 5 āœ“āœ“ BEST!
  Sell day 5: 4 - 1 = 3

Buy day 2 (price=5):
  Sell day 3: 3 - 5 = -2
  Sell day 4: 6 - 5 = 1
  Sell day 5: 4 - 5 = -1

Buy day 3 (price=3):
  Sell day 4: 6 - 3 = 3
  Sell day 5: 4 - 3 = 1

Buy day 4 (price=6):
  Sell day 5: 4 - 6 = -2

Maximum profit = 5 (buy at 1, sell at 6)

What Did I Learn?

Key insight:
  To maximize profit, I want to:
    - Buy at the LOWEST price
    - Sell at the HIGHEST price AFTER that

  It's all about finding:
    max(prices[j] - prices[i]) where j > i

šŸ¤” Approach 1: Brute Force

The Idea

Try every possible buy-sell pair:
  For each buy day i:
    For each sell day j > i:
      Calculate profit = prices[j] - prices[i]
      Track maximum

Code

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int buy = 0; buy < prices.length; buy++) {
            for (int sell = buy + 1; sell < prices.length; sell++) {
                int profit = prices[sell] - prices[buy];
                maxProfit = Math.max(maxProfit, profit);
            }
        }

        return maxProfit;
    }
}

Complexity

TIME: O(nĀ²) - two nested loops
SPACE: O(1)

For n=100,000: 10 billion operations āœ— TOO SLOW!

šŸ’” The Key Observation

Let Me Think Differently

As I go through each day, I can ask:

"If I SELL today, when should I have bought?"

Answer: At the MINIMUM price seen so far!

Let me trace this:

Day 0: price=7
  minPrice so far = 7
  If sell today: profit = 7 - 7 = 0
  maxProfit = 0

Day 1: price=1
  minPrice so far = min(7, 1) = 1
  If sell today: profit = 1 - 1 = 0
  maxProfit = 0

Day 2: price=5
  minPrice so far = 1
  If sell today: profit = 5 - 1 = 4
  maxProfit = 4

Day 3: price=3
  minPrice so far = 1
  If sell today: profit = 3 - 1 = 2
  maxProfit = 4

Day 4: price=6
  minPrice so far = 1
  If sell today: profit = 6 - 1 = 5 āœ“
  maxProfit = 5

Day 5: price=4
  minPrice so far = 1
  If sell today: profit = 4 - 1 = 3
  maxProfit = 5

Answer: 5 āœ“

The Pattern

At each day:
  1. Update minimum price seen so far
  2. Calculate profit if we sell today
  3. Update maximum profit

One pass through the array! O(n) āœ“

šŸŽÆ Approach 2: One Pass Solution

Code

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            // Update minimum price
            minPrice = Math.min(minPrice, price);

            // Calculate profit if we sell today
            int profit = price - minPrice;

            // Update maximum profit
            maxProfit = Math.max(maxProfit, profit);
        }

        return maxProfit;
    }
}

Complete Trace

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

i=0, price=7:
  minPrice = min(INF, 7) = 7
  profit = 7 - 7 = 0
  maxProfit = max(0, 0) = 0

i=1, price=1:
  minPrice = min(7, 1) = 1
  profit = 1 - 1 = 0
  maxProfit = max(0, 0) = 0

i=2, price=5:
  minPrice = min(1, 5) = 1
  profit = 5 - 1 = 4
  maxProfit = max(0, 4) = 4

i=3, price=3:
  minPrice = min(1, 3) = 1
  profit = 3 - 1 = 2
  maxProfit = max(4, 2) = 4

i=4, price=6:
  minPrice = min(1, 6) = 1
  profit = 6 - 1 = 5
  maxProfit = max(4, 5) = 5

i=5, price=4:
  minPrice = min(1, 4) = 1
  profit = 4 - 1 = 3
  maxProfit = max(5, 3) = 5

Return 5 āœ“

Complexity

TIME: O(n) - single pass
SPACE: O(1) - only two variables

Much better! āœ“

šŸ”‘ Key Insights

The Simple Pattern

Problem: Find max(prices[j] - prices[i]) where j > i

Solution: For each day j:
  - Track minimum price before day j
  - Calculate profit = prices[j] - minimum
  - Track maximum profit

This reduces O(nĀ²) to O(n)!

Why This Works

We don't need to try all pairs!

For any sell day j:
  Best buy day = day with minimum price before j

By tracking minimum as we go:
  We automatically find the best buy day for each sell day

šŸ’» Complete Working Code

class Solution {
  public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int price : prices) {
      minPrice = Math.min(minPrice, price);
      maxProfit = Math.max(maxProfit, price - minPrice);
    }

    return maxProfit;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.maxProfit(new int[] {7,1,5,3,6,4})); // 5
    System.out.println(sol.maxProfit(new int[] {7,6,4,3,1})); // 0
  }
}

šŸ“ Quick Revision

Algorithm

minPrice = infinity
maxProfit = 0

For each price:
  minPrice = min(minPrice, price)
  profit = price - minPrice
  maxProfit = max(maxProfit, profit)

Return maxProfit

Quick Implementation

public class Solution {
  public int maxProfit(int[] a) {
    // return bruteForce(a);
    return dp(a);
  }

  private int dp(int[] a) {
    int res = 0;
    // consider example [7,1,5,3,6,4]
    // step 1: take 7
    int minSoFar = a[0];

    // step 2: start from 1
    for (int i = 1; i < a.length; i++) {
      res = Math.max(res, a[i] - minSoFar);
      // step 3: track min so far found.
      // put it on paper. So easy
      minSoFar = Math.min(minSoFar, a[i]);
    }

    return res;
  }

  private int bruteForce(int[] a) {
    int res = 0;

    for (int i = 0; i < a.length; i++) {
      // why j = i + 1?
      // becuase you can sell only on any day > i only.
      // and you cannot sell on the same day when we buy it.
      for (int j = i + 1; j < a.length; j++) {
        res = Math.max(res, a[j] - a[i]);
      }
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.maxProfit(new int[] { 7, 1, 5, 3, 6, 4 }) == 5);
    System.out.println(s.maxProfit(new int[] { 7, 6, 4, 3, 1 }) == 0);
  }
}

Complexity

TIME: O(n)
SPACE: O(1)

Key Idea

Track minimum price seen so far
Calculate profit if we sell today
Keep maximum profit

šŸŽ‰ Done!

Simple problem with simple solution: - āœ… One pass through array - āœ… Track minimum price - āœ… Calculate profit at each step - āœ… O(n) time, O(1) space

Clean and efficient! āœ“