Tracking Minimum Pattern

Why this pattern matters for LeetCode

The brute force tries every buy/sell pair — O(n²). Tracking Minimum is O(n): carry the cheapest price seen so far, and at each price compute what the profit would be if you sold today. One variable eliminates the need to scan backward. The critical order matters: you must update the minimum BEFORE computing profit, because you can't sell before you buy.

What the Tracking Minimum pattern is

The tracking minimum (or maximum) pattern maintains a running best value as you scan forward. Instead of comparing every pair with a nested loop, you remember the smallest (or largest) element seen so far and compute the answer relative to it at each step. This collapses O(n²) pair comparisons into a single O(n) pass. The insight: you never need to look backward — you already have the optimal historical value stored in one variable.

Reach for Tracking Minimum when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Tracking Minimum

• ✓Maximum profit from buy-sell stock (classic Tracking Minimum)
• ✓Maximum difference between two elements where the smaller comes first
• ✓Finding the best 'buy' before the current 'sell' in any single-pass problem
• ✓Any problem where you need the running min or max up to the current position

When NOT to use Tracking Minimum

• ✕You need to track the global maximum — that's a simpler running max pattern
• ✕The problem allows multiple transactions — a different DP or greedy approach is needed
• ✕The minimum doesn't need to come before the maximum — Two Pointers or sorting may apply
• ✕You need the minimum of a window, not the overall minimum so far — use a deque (monotonic queue)

Better alternative: In those cases, Kadane's Algorithm (for subarray sums) or a monotonic deque (for windowed minimums) may be more appropriate.

JavaScript code template

Best Time to Buy and Sell Stock — O(n) time, O(1) space

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    // Update minPrice FIRST — you must buy before you sell
    minPrice = Math.min(minPrice, price);

    // Compute profit if you sold at today's price
    const profit = price - minPrice;

    // Update the best profit seen so far
    maxProfit = Math.max(maxProfit, profit);
  }

  return maxProfit;
}

minPrice tracks the cheapest price seen before or at the current day. Update it first — this ensures you never use today's price as both the buy and sell. Then compute profit assuming you sell at the current price. Update maxProfit if this is better than any previous opportunity. If prices only ever decrease, maxProfit stays 0 (you simply don't transact).

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Initialize minSoFar = Infinity and maxDiff = 0.
2. 2Loop through each value in the array.
3. 3Update minSoFar = Math.min(minSoFar, current) — do this FIRST.
4. 4Compute the current difference: current - minSoFar.
5. 5Update maxDiff = Math.max(maxDiff, currentDiff) if this is the best you've seen.
6. 6Return maxDiff after the loop.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Best Time to Buy and Sell Stock

  Track the minimum price seen so far, compute profit at each step — the textbook Tracking Minimum problem.

  Premium→

Coming soon

• Best Time to Buy and Sell Stock II

  Multiple transactions allowed — greedy: take every upward slope.

  Coming soon
• Maximum Difference Between Increasing Elements

  Same pattern as buy/sell — track the running minimum and compute the max difference where smaller comes first.

  Coming soon

Common mistakes beginners make

• ✕Updating maxProfit before minPrice — this lets you compute profit using today's price as both buy and sell, which is invalid.
• ✕Initializing minPrice to 0 instead of Infinity — with 0, prices like [3, 2, 1] produce a negative difference and wrong profits.
• ✕Returning a negative profit — if prices only decrease, the correct answer is 0 (you don't trade). maxProfit initialized to 0 handles this.
• ✕Nested loop instinct: comparing every pair of buy/sell days is O(n²). The running minimum means you never need to look backward.

Tracking Minimum vs Kadane's vs Sliding Window

Choose the right tool for the job.

Time and space complexity

One pass through the array — each price is visited once. Two variables (minPrice and maxProfit) use O(1) space. No extra arrays, no nested loops, no backward scanning.

Frequently asked questions

Why must I update minPrice before computing profit?

Because you can't sell before you buy. If you compute profit first using today's price, and then update minPrice to today's price, you might be subtracting today's price from itself — profit of 0 at best, or using a future price as the 'buy' date. Update minPrice first to ensure the buy always comes before the sell.

Why initialize minPrice to Infinity and not 0?

Because 0 is not a valid price floor — real prices are all positive. If you initialize to 0, the first Math.min(0, prices[0]) keeps minPrice at 0, and you compute prices[0] - 0 as the profit, which is wrong. Infinity ensures the first real price always wins and becomes the initial minPrice.

How is Tracking Minimum different from Kadane's Algorithm?

Kadane's tracks a running sum and decides at each element whether to extend or restart the subarray. Tracking Minimum keeps a single 'best historical value' (minimum price) and computes a difference (profit) at each step. They solve different shaped problems: Kadane's for contiguous sums, Tracking Minimum for best pair with the smaller value coming first.

Why is this O(n) when the brute force is O(n²)?

The brute force has a nested loop: for each sell day, scan all previous days for the best buy. The inner loop is O(n) per sell day — O(n²) total. Tracking Minimum replaces the inner loop with one O(1) operation: compare the current price to a pre-computed running minimum. You get the same result in O(n) time because the running minimum captures everything the inner loop would have scanned.