#8 · Sliding Window

Best Time to Buy and Sell Stock

Given daily prices, choose one day to buy and a later day to sell to maximize profit. Return the maximum profit, or 0 if no profitable trade exists.

EasyLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Running aggregate (two scalars)

Instead of storing history, keep just the cheapest price seen so far and the best profit so far. Each new day is judged against the cheapest earlier day, which is the only buy day that could be optimal for it.

Memory layout

Two registers/integers: no allocation. The input array is read once, sequentially, which is the best case for prefetching.

Operation	Cost
process one day	O(1)
whole scan	O(n)
extra space	O(1)

Precomputed suffix-maximum array

maxAfter[i] = highest price after day i, so the best profit for buying on day i is maxAfter[i] − prices[i]. It trades O(n) memory for turning the inner loop into a lookup.

Memory layout

A second contiguous array of the same length as the input, built in one right-to-left pass.

Operation	Cost
build	O(n)
query best sell price after i	O(1)
space	O(n)

Why it fits

For any sell day, the best buy day is simply the cheapest day before it. So we never need to compare against every earlier day, only against one running minimum.
A scan from left to right has all the information it needs at each step; there is nothing in the future that could change the decision about the past, so a single pass suffices.
Profit over a span equals the sum of daily changes, so the problem is also "largest sum of a contiguous run of changes": the Kadane formulation.

Why alternatives degrade

Nested loops over all (buy, sell) pairs:: O(n²) pairs, but only one buy day per sell day (the running minimum) can matter.
Sorting prices:: Destroys the order, and the buy day must come before the sell day; sorting would allow selling before buying.
Monotonic stack / heap:: Correct but heavier than needed; a single running minimum already captures what the stack would keep.

Four approaches, from naive to production

1 · beginner

Try every (buy, sell) pair

time O(n²)space O(1)

For each buy day, check every later sell day and keep the largest profit.

int maxProfit(vector<int>& prices) {
    int best = 0;
    int n = prices.size();
    for (int buy = 0; buy < n; buy++) {
        for (int sell = buy + 1; sell < n; sell++) {
            best = max(best, prices[sell] - prices[buy]);
        }
    }
    return best;
}

public int maxProfit(int[] prices) {
    int best = 0;
    int n = prices.length;
    for (int buy = 0; buy < n; buy++) {
        for (int sell = buy + 1; sell < n; sell++) {
            best = Math.max(best, prices[sell] - prices[buy]);
        }
    }
    return best;
}

def max_profit(prices: list[int]) -> int:
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

function maxProfit(prices: number[]): number {
  let best = 0;
  for (let buy = 0; buy < prices.length; buy++) {
    for (let sell = buy + 1; sell < prices.length; sell++) {
      best = Math.max(best, prices[sell] - prices[buy]);
    }
  }
  return best;
}

Flaws & bottlenecks

About n²/2 pairs: ~5 × 10⁹ for n = 10⁵, which will time out.
For each sell day, only the cheapest earlier day matters, yet every earlier day is evaluated.
No early exit and no reuse of earlier work.

Interviewer cross-questions

Where is the wasted work?

Say: For a fixed sell day, the profit is maximized by the lowest buy price before it. Looping over all earlier buy days recomputes that minimum from scratch every time. Carrying a running minimum removes the inner loop.

What if no profitable trade exists (prices only fall)?

Say: best starts at 0 and only increases when a positive profit appears, so the answer is 0 ("do not trade"). Returning a negative number would be wrong for this problem.

Can you buy and sell on the same day?

Say: The inner loop starts at buy + 1, so a trade needs two different days. Same-day trading would only ever give profit 0, which best already covers.

2 · intermediate

Precompute the best later price

time O(n)space O(n)

Build maxAfter[i], the highest price after day i, from right to left. Then the best trade for each buy day is a single subtraction.

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<int> maxAfter(n, 0);
    for (int i = n - 2; i >= 0; i--) {
        maxAfter[i] = max(maxAfter[i + 1], prices[i + 1]);
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        best = max(best, maxAfter[i] - prices[i]);
    }
    return best;
}

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] maxAfter = new int[n];
    for (int i = n - 2; i >= 0; i--) {
        maxAfter[i] = Math.max(maxAfter[i + 1], prices[i + 1]);
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        best = Math.max(best, maxAfter[i] - prices[i]);
    }
    return best;
}

def max_profit(prices: list[int]) -> int:
    n = len(prices)
    max_after = [0] * n
    for i in range(n - 2, -1, -1):
        max_after[i] = max(max_after[i + 1], prices[i + 1])
    best = 0
    for i in range(n):
        best = max(best, max_after[i] - prices[i])
    return best

function maxProfit(prices: number[]): number {
  const n = prices.length;
  const maxAfter = new Array<number>(n).fill(0);
  for (let i = n - 2; i >= 0; i--) {
    maxAfter[i] = Math.max(maxAfter[i + 1], prices[i + 1]);
  }
  let best = 0;
  for (let i = 0; i < n; i++) {
    best = Math.max(best, maxAfter[i] - prices[i]);
  }
  return best;
}

Flaws & bottlenecks

Two passes and an extra array of n numbers.
Reads memory twice (once building, once evaluating) where a single pass would do.
The sentinel 0 for the last day relies on prices being non-negative.

Interviewer cross-questions

Why fill maxAfter from right to left?

Say: maxAfter[i] depends on maxAfter[i + 1] (everything to the right), so the right neighbour must already be final. Filling left to right would need the future.

Can you drop the extra array?

Say: Yes. Flip the roles and scan left to right keeping the minimum price so far instead of the maximum to the right. That needs only two scalars and one pass: the advanced approach.

What if prices can be negative?

Say: The sentinel 0 for the last day would be wrong. Use -Infinity (or the last price itself) as the base case, or initialize the suffix maximum with prices[n-1] and loop from n−2.

3 · advanced

One pass with a running minimum

time O(n)space O(1)

Scan once, remembering the lowest price so far. At each day, the best profit if we sold today is price − minPrice.

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int best = 0;
    for (int price : prices) {
        if (price < minPrice) minPrice = price;
        else best = max(best, price - minPrice);
    }
    return best;
}

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int best = 0;
    for (int price : prices) {
        if (price < minPrice) minPrice = price;
        else best = Math.max(best, price - minPrice);
    }
    return best;
}

def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    best = 0
    for price in prices:
        if price < min_price: min_price = price
        else: best = max(best, price - min_price)
    return best

function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let best = 0;
  for (const price of prices) {
    if (price < minPrice) minPrice = price;
    else best = Math.max(best, price - minPrice);
  }
  return best;
}

Flaws & bottlenecks

The ∞ sentinel for minPrice is a float/special value in some languages (use the first price or INT_MAX instead).
Returns only the profit, not the days; reconstructing them needs two extra index variables.
Works for a single transaction only; multiple transactions or a cooldown change the algorithm (it becomes DP).

Interviewer cross-questions

Why is it correct to buy at the minimum so far?

Say: For a given sell day, the profit is price − buy price, which is largest when the buy price is the smallest among earlier days. The running minimum is exactly that, so scanning once and tracking it covers every possible optimal trade.

How would you also return the buy and sell days?

Say: Store the index when minPrice updates, and when best improves record that index as buyDay and the current index as sellDay.

How does this change with unlimited transactions?

Say: Then you can take every upward move: sum the positive differences prices[i] − prices[i−1]. With a transaction limit k or a cooldown, you need DP over states (holding / not holding).

4 · expert

Kadane on daily differences

time O(n)space O(1)

Profit over a span is the sum of daily changes, so the best trade is the maximum-sum contiguous run of changes. Keep a running gain, clamped at 0, and the best so far.

int maxProfit(const vector<int>& prices) {
    int n = prices.size();
    if (n < 2) return 0;
    long long best = 0;
    long long run = 0;
    for (int i = 1; i < n; i++) {
        run = max(0LL, run + ((long long)prices[i] - prices[i - 1]));
        if (run > best) best = run;
    }
    return (int)best;
}

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n < 2) return 0;
    long best = 0;
    long run = 0;
    for (int i = 1; i < n; i++) {
        run = Math.max(0L, run + ((long) prices[i] - prices[i - 1]));
        if (run > best) best = run;
    }
    return (int) best;
}

def max_profit(prices: Sequence[int]) -> int:
    n = len(prices)
    if n < 2: return 0
    best = 0
    run = 0
    for i in range(1, n):
        run = max(0, run + (prices[i] - prices[i - 1]))
        if run > best: best = run
    return best

function maxProfit(prices: ArrayLike<number>): number {
  const n = prices.length;
  if (n < 2) return 0;
  let best = 0;
  let run = 0;
  for (let i = 1; i < n; i++) {
    run = Math.max(0, run + (prices[i] - prices[i - 1]));
    if (run > best) best = run;
  }
  return best;
}

Flaws & bottlenecks

Less obvious to read than the running-minimum version, which matters in code review.
Differences can overflow narrow integer types for extreme prices; compute them in a wider type.
Recovering the buy/sell days needs extra bookkeeping for where the current run started.

Interviewer cross-questions

Why is this the same as Maximum Subarray?

Say: Buying on day a and selling on day b earns prices[b] − prices[a] = the sum of daily changes d[a+1..b]. So the best trade is the contiguous run of d with the largest sum, which is exactly Kadane's algorithm: extend the run, or restart when it goes negative.

Why clamp run at 0?

Say: A negative running gain can only hurt any trade that continues through it. Resetting to 0 means "start a new trade today", which is equivalent to buying at today's price.

How do you guard against overflow?

Say: prices[i] − prices[i−1] can overflow a 32-bit int for extreme inputs, and run can accumulate. Use 64-bit for diff and run (long / long long), then clamp or check the result against the return type.

Synchronized code walkthrough

Showing: Try every (buy, sell) pair — shares the player above; click any step to jump.

int maxProfit(vector<int>& prices) {
    int best = 0;
    int n = prices.size();
    for (int buy = 0; buy < n; buy++) {
        for (int sell = buy + 1; sell < n; sell++) {
            best = max(best, prices[sell] - prices[buy]);
        }
    }
    return best;
}

public int maxProfit(int[] prices) {
    int best = 0;
    int n = prices.length;
    for (int buy = 0; buy < n; buy++) {
        for (int sell = buy + 1; sell < n; sell++) {
            best = Math.max(best, prices[sell] - prices[buy]);
        }
    }
    return best;
}

def max_profit(prices: list[int]) -> int:
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

function maxProfit(prices: number[]): number {
  let best = 0;
  for (let buy = 0; buy < prices.length; buy++) {
    for (let sell = buy + 1; sell < prices.length; sell++) {
      best = Math.max(best, prices[sell] - prices[buy]);
    }
  }
  return best;
}

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<int> maxAfter(n, 0);
    for (int i = n - 2; i >= 0; i--) {
        maxAfter[i] = max(maxAfter[i + 1], prices[i + 1]);
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        best = max(best, maxAfter[i] - prices[i]);
    }
    return best;
}

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] maxAfter = new int[n];
    for (int i = n - 2; i >= 0; i--) {
        maxAfter[i] = Math.max(maxAfter[i + 1], prices[i + 1]);
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        best = Math.max(best, maxAfter[i] - prices[i]);
    }
    return best;
}

def max_profit(prices: list[int]) -> int:
    n = len(prices)
    max_after = [0] * n
    for i in range(n - 2, -1, -1):
        max_after[i] = max(max_after[i + 1], prices[i + 1])
    best = 0
    for i in range(n):
        best = max(best, max_after[i] - prices[i])
    return best

function maxProfit(prices: number[]): number {
  const n = prices.length;
  const maxAfter = new Array<number>(n).fill(0);
  for (let i = n - 2; i >= 0; i--) {
    maxAfter[i] = Math.max(maxAfter[i + 1], prices[i + 1]);
  }
  let best = 0;
  for (let i = 0; i < n; i++) {
    best = Math.max(best, maxAfter[i] - prices[i]);
  }
  return best;
}

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int best = 0;
    for (int price : prices) {
        if (price < minPrice) minPrice = price;
        else best = max(best, price - minPrice);
    }
    return best;
}

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int best = 0;
    for (int price : prices) {
        if (price < minPrice) minPrice = price;
        else best = Math.max(best, price - minPrice);
    }
    return best;
}

def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    best = 0
    for price in prices:
        if price < min_price: min_price = price
        else: best = max(best, price - min_price)
    return best

function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let best = 0;
  for (const price of prices) {
    if (price < minPrice) minPrice = price;
    else best = Math.max(best, price - minPrice);
  }
  return best;
}

int maxProfit(const vector<int>& prices) {
    int n = prices.size();
    if (n < 2) return 0;
    long long best = 0;
    long long run = 0;
    for (int i = 1; i < n; i++) {
        run = max(0LL, run + ((long long)prices[i] - prices[i - 1]));
        if (run > best) best = run;
    }
    return (int)best;
}

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n < 2) return 0;
    long best = 0;
    long run = 0;
    for (int i = 1; i < n; i++) {
        run = Math.max(0L, run + ((long) prices[i] - prices[i - 1]));
        if (run > best) best = run;
    }
    return (int) best;
}

def max_profit(prices: Sequence[int]) -> int:
    n = len(prices)
    if n < 2: return 0
    best = 0
    run = 0
    for i in range(1, n):
        run = max(0, run + (prices[i] - prices[i - 1]))
        if run > best: best = run
    return best

function maxProfit(prices: ArrayLike<number>): number {
  const n = prices.length;
  if (n < 2) return 0;
  let best = 0;
  let run = 0;
  for (let i = 1; i < n; i++) {
    run = Math.max(0, run + (prices[i] - prices[i - 1]));
    if (run > best) best = run;
  }
  return best;
}