SyntaxPilot
Courses/DSA and Coding Problems/Lesson 3
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 3 of 90

Best Time to Buy and Sell Stock (running minimum)

queued

These are the notes for DSA episode 3. The stock problem (LeetCode 121) is a placement and interview favourite, and the trick behind it, carrying the best value seen so far, is the seed of dynamic programming. You will see the brute force over every pair of days, watch it time out, invent the running minimum, and write the one-pass O(n) solution. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A vegetable trader at the mandi wrote down a week of tomato prices: ₹7, 1, 5, 3, 6, 4 per kilo. He will buy one crate on one day and sell it on a later day. What is the best profit he could have made? If prices only fell, the best plan is not to trade: profit 0.

Problem statement

Given prices, where prices[i] is the price on day i, choose a buy day i and a sell day j with i < j to maximise prices[j] - prices[i]. Return the maximum profit, or 0 if no trade makes money. Constraints: 1 ≤ n ≤ 10⁵.

prices answer why
[7, 1, 5, 3, 6, 4] 5 buy at 1 (day 1), sell at 6 (day 4)
[7, 6, 4, 3, 1] 0 every later price is lower

Brute force: every pair of days

public class Main {
    static int maxProfit(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;
    }
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit(new int[]{7, 6, 4, 3, 1}));
    }
}

Output:

5
0

On ten lakh (1,000,000) days:

int n = 1000000, prices[] = new int[n];
for (int i = 0; i < n; i++) prices[i] = (int) (i * 7919L % 1000003);
Time Limit Exceeded (8 s)

Why it is slow

  • n(n-1)/2 pairs: O(n²), about 5 × 10¹¹ for n = 10⁶.
  • Fix the sell day j. The best buy day is simply the cheapest day before j. The inner loop recomputes that minimum from scratch for every j, even though it only changes when a cheaper price appears.

The key insight: the running minimum

You already do this in real life: nobody remembers every petrol price of the week, just the lowest one seen so far.

  • minSoFar: the cheapest price up to today.
  • price - minSoFar: the best profit if you sell today.
  • best: the best of those over all days.

Two variables replace the whole inner loop.

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

day price minSoFar sell today best
0 7 7 0 0
1 1 1 0 0
2 5 1 4 4
3 3 1 2 4
4 6 1 5 5
5 4 1 3 5

The optimal solution: one pass

public class Main {
    static int maxProfit(int[] prices) {
        int minSoFar = Integer.MAX_VALUE, best = 0;
        for (int price : prices) {
            minSoFar = Math.min(minSoFar, price);
            best = Math.max(best, price - minSoFar);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit(new int[]{7, 6, 4, 3, 1}));
        System.out.println(maxProfit(new int[]{5}));
        System.out.println(maxProfit(new int[]{}));
        System.out.println(maxProfit(new int[]{3, 3, 3}));
    }
}

Output:

5
0
0
0
0

Updating minSoFar before best is safe: on a new cheapest day we compute price - price = 0, the same as buying and selling on the same day. One crore (10,000,000) days finish in a few milliseconds:

1000002   15 ms

The same solution in C++ and Python

#include <bits/stdc++.h>
using namespace std;

int maxProfit(const vector<int>& prices) {
    int minSoFar = INT_MAX, best = 0;
    for (int price : prices) {
        minSoFar = min(minSoFar, price);
        best = max(best, price - minSoFar);
    }
    return best;
}

int main() {
    cout << maxProfit({7, 1, 5, 3, 6, 4}) << "\n";   // 5
    cout << maxProfit({7, 6, 4, 3, 1}) << "\n";      // 0
}
def max_profit(prices):
    min_so_far, best = float("inf"), 0
    for price in prices:
        min_so_far = min(min_so_far, price)
        best = max(best, price - min_so_far)
    return best

print(max_profit([7, 1, 5, 3, 6, 4]))   # 5
print(max_profit([7, 6, 4, 3, 1]))      # 0

Complexity

Approach Time Extra space n = 10⁶
Every pair of days O(n²) O(1) Time Limit Exceeded
Running minimum O(n) O(1) milliseconds

Printing the buy and sell days

Remember the day of the minimum instead of the price:

public class Main {
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        int minDay = 0, buy = 0, sell = 0, best = 0;
        for (int day = 1; day < prices.length; day++) {
            if (prices[day] < prices[minDay]) minDay = day;
            if (prices[day] - prices[minDay] > best) {
                best = prices[day] - prices[minDay];
                buy = minDay;
                sell = day;
            }
        }
        System.out.println("Buy on day " + buy + " at " + prices[buy]);
        System.out.println("Sell on day " + sell + " at " + prices[sell]);
        System.out.println("Profit: " + best);
    }
}

Output:

Buy on day 1 at 1
Sell on day 4 at 6
Profit: 5

Common mistakes

Mistake What you see Why Fix
return max - min; 3 for [2, 4, 1] (answer is 2) the minimum (1) comes after the maximum (4): you can't sell before buying carry the minimum before each day
int minSoFar = 0; 7 for [7, 1, 5, 3, 6, 4] no price is below 0, so it "buys for free" start at Integer.MAX_VALUE or prices[0]
best = Integer.MIN_VALUE in the pair loops -1 for [7, 6, 4, 3, 1] the answer must be 0 when every trade loses best = 0
minSoFar = prices[0] on an empty array ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0 there is no day 0 check prices.length first

The pattern

Walk once and carry the best thing seen so far: a running minimum, maximum or sum. The profit from day i to day j is also the sum of the daily price changes in between, so the best trade is the best stretch of daily changes: that is Kadane's algorithm, next episode. Later in the course: many trades, cooldowns and transaction fees, with dynamic programming.

Practice

  1. Find the biggest loss: buy on day i, sell on a later day j, minimise prices[j] - prices[i] (report it as a negative number, or 0 if prices never fall).
Solution

Carry the maximum so far and track worst = min(worst, price - maxSoFar).

int maxSoFar = Integer.MIN_VALUE, worst = 0;
for (int price : prices) {
    maxSoFar = Math.max(maxSoFar, price);
    worst = Math.min(worst, price - maxSoFar);
}

For [7, 1, 5, 3, 6, 4] this gives -6 (buy at 7, sell at 1).

  1. Maximum difference a[j] - a[i] with i < j, where the answer may be negative ([5, 4, 2] → -1).
Solution

Start best = Integer.MIN_VALUE, minSoFar = a[0], and loop from index 1: update best with a[j] - minSoFar before updating minSoFar, so you never compare a day with itself.

  1. Solve it walking from the right with a running maximum.
Solution
int maxRight = Integer.MIN_VALUE, best = 0;
for (int i = prices.length - 1; i >= 0; i--) {
    maxRight = Math.max(maxRight, prices[i]);
    best = Math.max(best, maxRight - prices[i]);
}

Same answer, O(n): the best sell day for buy day i is the most expensive day from i onward.

Quick quiz

What does maxProfit(new int[]{3, 8, 2, 6, 1, 4}) return?

  • 7
  • 5
  • 4
  • 3
Answer

5. minSoFar goes 3, 3, 2, 2, 1, 1; selling today gives 0, 5, 0, 4, 0, 3. Buying at 1 comes too late to sell at 8.

Interview questions

  1. Why is the running minimum correct? For any sell day, the best buy day is the cheapest earlier day; minSoFar is exactly that, kept up to date in O(1) per day.
  2. What is the time and space complexity? O(n) time, O(1) space.
  3. How is this related to Kadane's algorithm? Profit = sum of daily changes over a stretch, so the answer is the maximum subarray sum of the change array.
  4. What if you can trade many times? Add up every positive daily change (Stock II); with cooldowns or fees, use dynamic programming.

Glossary

Term Meaning
Buy day / sell day The indexes i and j of the trade; the sell day must come later (i < j)
Profit prices[j] - prices[i]
Running minimum The smallest value seen so far while walking the array, updated in O(1) per step
Integer.MAX_VALUE The largest int, 2,147,483,647: a safe starting value for a minimum
One pass Walking the array exactly once
Edge case An unusual input that often breaks code: empty, one element, all equal, all falling
Dynamic programming Building the answer for step i from answers already computed for earlier steps

Summary

  • Every pair of days is O(n²) and times out for big n.
  • For any sell day, the best buy is the cheapest day before it: carry minSoFar.
  • best = max(best, price - minSoFar): O(n) time, O(1) space.
  • max - min is wrong: it ignores the order of days.

Next episode: Kadane's algorithm, the maximum subarray.