Sliding Window —

Here's a problem: find the maximum sum of any 5 consecutive elements in an array. The brute force nests two loops — for each starting position, sum the next 5. O(n × k).

But think about what happens when the window moves one position right. You add one new element and remove one old element. What stays the same?

Four of the five elements are identical between consecutive windows. You're recomputing 80% of the work each time. That's the waste. The question is: can you maintain a running result and adjust it incrementally?

Fixed Window

function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

One element in, one element out. Two operations per step, regardless of window size. O(n) total.

This is the pattern: maintain state incrementally rather than recomputing from scratch. Simple when the window is fixed. But what about when it's not?

Variable Window

Now try this: find the longest subarray whose sum doesn't exceed a target. The window can be any size. How do you decide when to shrink it?

Pause. Think about what condition triggers the left pointer to move. What invariant are you maintaining?

function longestSubarray(nums: number[], target: number): number {
  let left = 0, sum = 0, maxLen = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum > target) sum -= nums[left++];
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

The right pointer always advances. The left pointer advances only when the constraint is violated. Here's the question that trips people up in interviews: there's a while loop inside a for loop — isn't that O(n²)?

No. And the reason is crucial to understand. Each pointer moves at most n times total, not n times per iteration. The left pointer never moves backward. Across all iterations of the outer loop, the inner while loop executes at most n times combined. Total work: O(n).

This is the same amortized reasoning from dynamic arrays. Can you see the parallel? In both cases, an operation that looks expensive per-step is actually cheap in aggregate because work is never repeated.

The Hidden Sliding Window

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

This is Best Time to Buy and Sell Stock. No explicit window. No left pointer. But it is a sliding window — minPrice implicitly tracks the left edge (best buy day seen so far). The window stretches from that minimum to the current position.

Recognizing disguised patterns matters more than memorizing templates. When you see a problem that tracks "best so far" while scanning linearly, ask: is there a hidden window here?

The Smell Test

Before reaching for sliding window, check these conditions:

- The problem involves a contiguous subarray or substring (not subsequence — that's different) - You're optimizing max/min/longest/shortest under some constraint - The constraint is monotonic: expanding the window can only make it harder to satisfy, not easier

That monotonicity requirement is the one people miss. If adding an element could improve the constraint (make the sum smaller in a "minimum sum ≥ target" problem), sliding window still works — but the logic inverts. If the relationship isn't monotonic at all, you need a different tool: prefix sums, deques, or segment trees.

Reflection

Explain why the variable-size sliding window is O(n) despite the nested loops. Then: what's the difference between a subarray problem (sliding window candidate) and a subsequence problem (not a candidate)? If you can articulate both, you'll recognize — and reject — sliding window problems correctly.

Original article: [jamesperalta.com](https://jamesperalta.com/learn/dsa/sliding-window)