15.Best Time to Buy and Sell Stock

EasyBlind 75Sliding Window · 1/6

Problem

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

You may complete at most one transaction: choose one day to buy and a later day to sell. Return the maximum profit you can achieve. If no profitable transaction exists, return 0.

Examples

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 1 (price 1) and sell on day 4 (price 6). Profit = 6 - 1 = 5.
             Buying at 1 and selling at 7 is not allowed because day 0 comes before day 1.

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Prices only fall, so every transaction loses money. Do nothing → profit 0.

Constraints

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

💡 Key Insight

For any selling day j, the best buying day is simply the cheapest day before j. So we do not need to try every pair — we sweep left to right, remember the minimum price seen so far, and at each day ask "what if I sold today?". One pass, constant memory.

Brute Force

TimeO(n²)SpaceO(1)

Intuition

Try every possible pair (buy day i, sell day j) with i < j and keep the largest prices[j] - prices[i].

Algorithm

Set maxProfit = 0.
For each i from 0 to n - 1:
For each j from i + 1 to n - 1, update maxProfit = max(maxProfit, prices[j] - prices[i]).
Return maxProfit.

Visualization

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

i=0 (7): 1-7, 5-7, 3-7, 6-7, 4-7  → all negative
i=1 (1): 5-1=4, 3-1=2, 6-1=5 ✓, 4-1=3  → best = 5
i=2 (5): 3-5, 6-5=1, 4-5           → best stays 5
...
answer = 5

Code

java

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                // buy on day i, sell on a later day j
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
}

Complexity

Time: O(n²) — every pair of days is examined; too slow for n = 10^5.
Space: O(1) — only a running maximum.

Two Pointers (Sliding Window)

TimeO(n)SpaceO(1)

Intuition

Keep a left pointer on the buy day and a right pointer on the sell day. If prices[right] is lower than prices[left], then right is a strictly better buy day for every future sale, so jump left to right. Otherwise, record the profit and keep moving right.

Algorithm

left = 0, maxProfit = 0.
For right from 1 to n - 1:
- If prices[right] < prices[left], set left = right (found a cheaper buy day).
- Else update maxProfit = max(maxProfit, prices[right] - prices[left]).
Return maxProfit.

Dry Run

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

right=1: 1 < 7  → left=1
right=2: 5 - 1 = 4  → max=4
right=3: 3 - 1 = 2  → max=4
right=4: 6 - 1 = 5  → max=5
right=5: 4 - 1 = 3  → max=5

Code

java

class Solution {
    public int maxProfit(int[] prices) {
        int left = 0;        // candidate buy day
        int maxProfit = 0;
        for (int right = 1; right < prices.length; right++) {
            if (prices[right] < prices[left]) {
                left = right; // cheaper day found: buy here instead
            } else {
                maxProfit = Math.max(maxProfit, prices[right] - prices[left]);
            }
        }
        return maxProfit;
    }
}

Complexity

Time: O(n) — right visits each day once.
Space: O(1) — two indices and a running maximum.

Running MinimumOptimal

TimeO(n)SpaceO(1)

Intuition

The same idea expressed more directly: track minPrice, the cheapest price seen so far. Each day, the best profit from selling today is price - minPrice. The answer is the maximum of those values. This is also the cleanest form to extend to related problems (it is Kadane's algorithm on the daily price differences).

Algorithm

minPrice = +infinity, maxProfit = 0.
For each price in prices:
- minPrice = min(minPrice, price).
- maxProfit = max(maxProfit, price - minPrice).
Return maxProfit.

Dry Run

flowchart LR
    A["day 0: price 7<br/>min = 7, best = 0"] --> B["day 1: price 1<br/>min = 1, best = 0"]
    B --> C["day 2: price 5<br/>min = 1, best = 4"]
    C --> D["day 3: price 3<br/>min = 1, best = 4"]
    D --> E["day 4: price 6<br/>min = 1, best = 5"]
    E --> F["day 5: price 4<br/>min = 1, best = 5"]
    F --> G["return 5"]

Code

java

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // cheapest buy price so far
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            // profit if we sold today after buying at the cheapest earlier day
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}

Complexity

Time: O(n) — a single pass over prices.
Space: O(1) — two variables.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Two Pointers	O(n)	O(1)
Running Minimum	O(n)	O(1)

Common Pitfalls

Taking max(prices) - min(prices) — the maximum may occur before the minimum, which would mean selling before buying.
Returning a negative number when prices only fall; the answer must be at least 0 (you may skip trading).
Updating maxProfit before minPrice is fine here, but updating minPrice with a future value before computing profit is not — always compare against prices from earlier (or the same) day.
Using a nested loop "because n is small" — n goes up to 10^5, so O(n²) times out.