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)/2pairs: 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
- 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).
- Maximum difference
a[j] - a[i]withi < 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.
- 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
- Why is the running minimum correct? For any sell day, the best buy day is the cheapest earlier day;
minSoFaris exactly that, kept up to date in O(1) per day. - What is the time and space complexity? O(n) time, O(1) space.
- 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.
- 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 - minis wrong: it ignores the order of days.
Next episode: Kadane's algorithm, the maximum subarray.