Running Min/Max Tracking

You are given an array of stock prices where prices[i] is the price on day i. You want to buy one share and later sell it to maximize your profit. You must buy before you sell. What is the maximum profit you can achieve?

This is LeetCode 121, "Best Time to Buy and Sell Stock," and it is one of the most elegant examples of a pattern that shows up constantly in array problems: tracking a running minimum (or maximum) as you scan through the data.

Why brute force is unnecessary

The naive approach checks every pair (i, j) where i < j and computes prices[j] - prices[i], keeping the maximum. That is $O(n^2)$: for each of the n possible buy days, you check every future sell day. It works, but it is doing far too much redundant computation.

Think about it this way: when you are considering selling on day j, you do not actually care about every previous day's price. You only care about the cheapest day before j, because that is the day you would have bought. The profit on day j is prices[j] - min(prices[0], prices[1], ..., prices[j-1]). If you track that minimum as you go, you never need to look backward.

The running minimum insight

As you scan from left to right, maintain a single variable: min_price, the minimum price seen so far. At each day j, the best profit you could achieve by selling on day j is prices[j] - min_price. Update your global best profit if this is larger, then update min_price if today's price is even lower.

That is the entire algorithm. One pass, two variables, $O(n)$ time, $O(1)$ space.

Walked example: prices = [7, 1, 5, 3, 6, 4]

Let's trace through the array step by step.

Day 0, price = 7: min_price = 7, profit = 7 - 7 = 0, max_profit = 0.

Day 1, price = 1: profit = 1 - 7 = -6, not better than 0. But 1 < 7, so min_price = 1.

Day 2, price = 5: profit = 5 - 1 = 4, better than 0, so max_profit = 4. min_price stays 1.

Day 3, price = 3: profit = 3 - 1 = 2, not better than 4. min_price stays 1.

Day 4, price = 6: profit = 6 - 1 = 5, better than 4, so max_profit = 5. min_price stays 1.

Day 5, price = 4: profit = 4 - 1 = 3, not better than 5. min_price stays 1.

Final answer: 5 (buy on day 1 at price 1, sell on day 4 at price 6).

Notice how the running minimum "remembers" the best buy opportunity from the past without needing to store the entire history. On day 4, we do not scan backward to find that day 1 was the cheapest. min_price already holds that information.

Code: Best Time to Buy and Sell Stock

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)
    return max_profit

The order of the two updates matters subtly. We compute the profit before updating min_price. If we updated min_price first, we might compute a profit of 0 (selling on the same day we buy), which is harmless for correctness since max_profit is initialized to 0, but the original order is cleaner in intent: "given the best buy price so far, what profit would I get by selling today?"

You could also swap the lines and the code would still be correct for this problem (since buying and selling on the same day yields 0 profit, which never beats a real profit). But the "compute profit first, then update min" order generalizes more cleanly to variants where you need strict inequality.

Why this is a greedy pattern

This algorithm is greedy in a specific sense: at each step, it makes the locally optimal choice by assuming you bought at the best possible past price. It never reconsiders or backtracks. The running minimum is what makes the greedy approach valid: it compresses the entire history of past prices into a single number that captures all the information needed for future decisions.

Compare this to a problem like "best time to buy and sell stock with at most k transactions." There, a single running minimum is not enough because your buy decision depends on how many transactions you have left. That problem requires dynamic programming. The single-transaction version is special precisely because the running minimum captures everything.

Maximum difference between two elements

The problem "find the maximum value of nums[j] - nums[i] where j > i" is structurally identical to the stock problem. Replace "prices" with "nums," "buy" with "pick the smaller index," and "sell" with "pick the larger index." The code is the same:

def maximumDifference(nums):
    min_val = nums[0]
    max_diff = -1  # or 0, depending on the problem's requirements
    for j in range(1, len(nums)):
        if nums[j] - min_val > 0:
            max_diff = max(max_diff, nums[j] - min_val)
        min_val = min(min_val, nums[j])
    return max_diff

Some variants require the difference to be strictly positive (return -1 if no valid pair exists). Others allow zero. Read the problem statement carefully, but the core technique is identical.

Running maximum from the right

Some problems flip the direction. Instead of "best past value" (running minimum from the left), they need "best future value" (running maximum from the right).

For example: given an array, for each element find the maximum element that appears after it. You scan right to left, maintaining a running maximum. At each position, the answer is the running maximum (excluding the current element), then you update the running maximum with the current element.

def maxToTheRight(nums):
    n = len(nums)
    result = [0] * n
    right_max = float('-inf')
    for i in range(n - 1, -1, -1):
        result[i] = right_max
        right_max = max(right_max, nums[i])
    return result

This is the mirror image of the running minimum pattern. The choice between left-to-right minimum and right-to-left maximum depends on the problem's constraint direction: does the answer at position i depend on what came before (use a left-to-right scan) or what comes after (use a right-to-left scan)?

Container With Most Water

Consider LeetCode 11. Container With Most Water: given an array height where height[i] is the height of a vertical line at position i, find two lines that together with the x-axis form a container holding the most water. The area between lines at positions i and j is min(height[i], height[j]) * (j - i).

This is a related two-pointer variant rather than a pure running-min problem, but the underlying intuition connects. Start with the widest container (left = 0, right = n-1). The area is limited by the shorter line. If you move the taller line inward, the width decreases and the height cannot increase (it is still capped by the shorter line), so the area can only decrease. Therefore, you should always move the shorter line inward, since it is the only move that has a chance of increasing the area.

def maxArea(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        w = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, w * h)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

The connection to running min/max: the two-pointer approach implicitly tracks the best height seen from each side. Moving the shorter pointer inward is analogous to saying "the current minimum is limiting us, so let's try to improve it." The greedy reasoning is the same: we can discard possibilities that provably cannot beat the current best.

The connection to Kadane's algorithm

There is a deep connection between running minimum tracking and Kadane's algorithm for maximum subarray sum. Consider the stock problem again: the profit prices[j] - prices[i] can be rewritten as the sum of daily changes (prices[1] - prices[0]) + (prices[2] - prices[1]) + ... + (prices[j] - prices[j-1]) for the subarray from i+1 to j. In other words, the maximum profit equals the maximum subarray sum of the difference array diff[k] = prices[k] - prices[k-1].

Kadane's algorithm on the difference array:

def maxProfit(prices):
    max_profit = 0
    current_sum = 0
    for i in range(1, len(prices)):
        current_sum += prices[i] - prices[i - 1]
        if current_sum < 0:
            current_sum = 0
        max_profit = max(max_profit, current_sum)
    return max_profit

This produces the same result as the running minimum approach. The equivalence is not a coincidence: resetting current_sum to 0 in Kadane's is equivalent to moving the buy point to the current day in the running minimum version. Both algorithms are making the same greedy decision: if the accumulated gain has gone negative, it is better to start fresh.

This duality is useful because some problems are easier to think about in "running min" form and others in "maximum subarray" form. Recognizing that they are the same thing gives you flexibility.

When to use running min vs. running max vs. both

Running minimum (left to right): Use when the answer at each position depends on the smallest (or best-to-buy) value seen so far. Classic examples: best time to buy and sell stock, maximum difference with j > i.

Running maximum (right to left): Use when the answer at each position depends on the largest (or best future) value that comes after it. Example: for each element, find the greatest element to its right.

Both directions: When the answer at position i depends on aggregates from both sides, you are in two-pass territory (see the two-pass assignment pattern). Trapping Rain Water uses both a left-running max and a right-running max. The distinction between "running min/max tracking" and "two-pass assignment" is one of degree: running min/max tracking typically needs only one direction and $O(1)$ space, while two-pass problems need both directions.

Running minimum of a transformed value: Sometimes you do not track the minimum of the raw array but of a computed quantity. For example, in some DP problems, you might track min(dp[j] - some_function(j)) as j increases, which lets you compute dp[i] in $O(1)$ per step instead of $O(n)$. This is the same pattern applied inside a DP recurrence.

Best Time to Buy and Sell Stock II

In the original stock problem you are limited to one transaction. LeetCode 122 removes that constraint: you can buy and sell as many times as you like (but must sell before buying again). The insight is delightfully simple: you collect every upward move. Whenever today's price exceeds yesterday's, add the difference to your profit. You are effectively "buying" at every local valley and "selling" at every local peak, but you never need to find the valleys and peaks explicitly.

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

Why does summing every positive daily change give the optimal answer? Any multi-day profit (buy on day i, sell on day j) equals the sum of consecutive daily changes from i+1 to j. Skipping any positive change can only reduce the total, and including a negative change can only reduce it. So taking exactly the positive changes is optimal. One pass, $O(n)$ time, $O(1)$ space.

Best Time to Buy and Sell Stock with Cooldown

With LeetCode 309, a new constraint enters: after selling, you must wait one day before buying again. A single running minimum is no longer sufficient because your decision to buy depends on past sell-and-cooldown history. This calls for a state machine DP with three states:

• held: you own a share (you either bought today or continued holding).
• sold: you sold a share today (entering cooldown tomorrow).
• cooldown: you are resting today after selling yesterday (free to buy tomorrow).

At each day, transition between states:

def maxProfit(prices):
    if not prices:
        return 0
    held = -prices[0]
    sold = 0
    cooldown = 0
    for i in range(1, len(prices)):
        prev_held, prev_sold, prev_cooldown = held, sold, cooldown
        held = max(prev_held, prev_cooldown - prices[i])
        sold = prev_held + prices[i]
        cooldown = max(prev_cooldown, prev_sold)
    return max(sold, cooldown)

held can come from continuing to hold or buying after a cooldown day. sold must come from holding and selling today. cooldown can come from staying idle or transitioning from sold (the mandatory wait). The answer is max(sold, cooldown). You never want to end holding a share. Time is $O(n)$, space is $O(1)$ since only three variables roll forward.

Complexity

The running min/max pattern is about as efficient as an algorithm can be:

• Time: $O(n)$: a single pass through the array, doing $O(1)$ work per element.
• Space: $O(1)$: you only store the running extreme and the current best answer.

This is what makes the pattern so powerful. It reduces $O(n^2)$ brute-force pair enumeration to $O(n)$ by recognizing that you do not need to remember every past element, only the most extreme one. Whenever you find yourself writing a nested loop where the inner loop searches for "the best previous value," stop and ask whether a running minimum or maximum can replace that inner loop. Almost always, it can.

Recognizing this pattern

You're probably looking at running min/max tracking when:

• The problem asks for the best pair $(i, j)$ with $i < j$ satisfying some maximize/minimize property, and a brute-force double loop would be the obvious approach.
• The "best $j$ for index $i$" depends only on a single extreme value seen before $i$: minimum price, maximum height, smallest prefix sum.
• You're processing a single array left-to-right and never need to revisit any specific earlier element, only the running aggregate.
• Words like "buy/sell," "profit," "max difference," "best window," or "earliest/latest" appear with no auxiliary structure required.
• Constraints push $n$ into $10^5$ or $10^6$, ruling out the $O(n^2)$ brute force.

Common templates:

• Best buy/sell once (running min, max profit): track minimum so far, update best $price[i] - min$. Example: Best Time to Buy and Sell Stock.
• Max difference / largest gap with order: same as above but generalized to any element pair. Example: Maximum Difference Between Increasing Elements.
• Max subarray sum (Kadane): running min prefix sum yields max subarray, or its dual form on running sum. Example: Maximum Subarray.
• Running max with rolling state machine: extend to multi-state DP variants like cooldown or fees. Example: Best Time to Buy and Sell Stock with Cooldown.
• Max product / non-additive running aggregate: track both running max and running min because signs can flip. Example: Maximum Product Subarray.