☕ DSA Java Articles

Topics › Arrays › Medium

Stock Buy and Sell

Medium TUF ID 2798 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array prices where prices[i] is the price of a stock on day i. You may buy on one day and sell on a later day, at most once. Return the maximum profit you can make. If no transaction is profitable (prices never rise), return 0: you simply do not trade.

This is LeetCode’s “Best Time to Buy and Sell Stock” (the first of the series). Only one transaction is allowed, which keeps the problem simple: the answer is the largest prices[j] - prices[i] with i < j.

Constraints: 0 ≤ n ≤ 10^5, 0 ≤ prices[i] ≤ 10^4. Because prices are non-negative and bounded, every difference fits in an int.

Example 1

prices = [7, 1, 5, 3, 6, 4]
answer = 5          // buy on day 1 (price 1), sell on day 4 (price 6)

Example 2

prices = [7, 6, 4, 3, 1]
answer = 0          // the price only falls, so do nothing

Example 3

prices = [2, 4, 1]
answer = 2          // buy at 2, sell at 4; the cheaper price 1 comes too late to sell after it

Approach 1: Brute force

Intuition. A transaction is a pair of days (i, j) with i < j. Try all of them and keep the largest difference. Starting the inner loop at i + 1 guarantees we sell strictly after we buy. Initialising the answer to 0 encodes “do not trade if nothing is profitable”.

Algorithm.

  1. Set best = 0.
  2. For every buy day i, for every sell day j > i: best = max(best, prices[j] - prices[i]).
  3. Return best.
static int bruteForce(int[] prices) {
    int best = 0;
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            best = Math.max(best, prices[j] - prices[i]);
        }
    }
    return best;
}

Complexity. Time O(n^2): about n^2 / 2 pairs. Space O(1).

For n = 10^5 that is 5 × 10^9 subtractions, far too slow.

Approach 2: Better, suffix maximum

Intuition. For a fixed buy day i, the best sell is the highest price on any later day. Instead of searching for it each time, precompute maxRight[i], the maximum of prices[i..n-1], in one right-to-left pass. Then the best profit for buying on day i is maxRight[i] - prices[i] (using maxRight[i] rather than maxRight[i + 1] is harmless, since selling on the buy day gives profit 0, which never beats the initial best = 0). One more pass takes the maximum over all i.

Algorithm.

  1. If the array is empty, return 0.
  2. Build maxRight from the right: maxRight[n-1] = prices[n-1], maxRight[i] = max(prices[i], maxRight[i+1]).
  3. Return the maximum over i of maxRight[i] - prices[i], starting from 0.
static int better(int[] prices) {
    int n = prices.length;
    if (n == 0) return 0;
    int[] maxRight = new int[n];          // maxRight[i] = highest price on day i or later
    maxRight[n - 1] = prices[n - 1];
    for (int i = n - 2; i >= 0; i--) maxRight[i] = Math.max(prices[i], maxRight[i + 1]);
    int best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, maxRight[i] - prices[i]);
    return best;
}

Complexity. Time O(n): two linear passes. Space O(n) for the auxiliary array.

This “precompute the best thing to my right” step is a general technique and worth recognising. Here it is not quite optimal because we can get the same information without storing it, by flipping the direction of the scan.

Approach 3: Optimal, track the minimum so far

Intuition. Flip the viewpoint: for a fixed sell day j, the best buy is the lowest price on any earlier day. Scanning left to right, that lowest price is just a running minimum, which needs one variable, not an array. At each day, either the price is a new minimum (a better future buy) or it is a candidate sell whose profit is price - minSoFar. Keep the best profit seen.

Why is this complete? Every transaction (i, j) has prices[i] ≥ minSoFar at the time we process j, so prices[j] - minSoFar ≥ prices[j] - prices[i]. The value we compute at day j is therefore at least as good as any transaction selling on day j, and it is itself a legal transaction (the minimum occurred on some earlier day, or on day j itself, in which case we are in the if branch and record nothing). Taking the maximum over all j covers every sell day.

Algorithm.

  1. Set minSoFar = +∞, best = 0.
  2. For every price p: if p < minSoFar, set minSoFar = p; otherwise best = max(best, p - minSoFar).
  3. Return best.
static int optimal(int[] prices) {
    int minSoFar = Integer.MAX_VALUE, best = 0;
    for (int p : prices) {
        if (p < minSoFar) minSoFar = p;
        else best = Math.max(best, p - minSoFar);
    }
    return best;
}

Dry run on prices = [7, 1, 5, 3, 6, 4]:

day price minSoFar after profit if sold today best
0 7 7 – (new minimum) 0
1 1 1 – (new minimum) 0
2 5 1 4 4
3 3 1 2 4
4 6 1 5 5
5 4 1 3 5

Complexity. Time O(n): one pass. Space O(1): two integers.

Connection to Kadane’s algorithm

Define diff[i] = prices[i] - prices[i-1], the day-to-day change. The profit of buying on day i and selling on day j is the sum diff[i+1] + ... + diff[j]. So the maximum profit is the maximum subarray sum of diff (with the empty subarray allowed, giving 0). Running Kadane’s algorithm on diff is therefore an equivalent O(n) solution; the running minimum above is what that algorithm turns into once you simplify it. Seeing this makes the harder variants of the stock problem (several transactions, cooldown, fees) feel less like new problems and more like constrained versions of a familiar one.

Edge cases and pitfalls