Sliding Window

Intermediate · 22 min read · Problem-Solving Patterns, Arrays & Strings

Grow the window, shrink when it breaks the rule — for subarrays and substrings.

"Find the longest substring without repeating characters." The brute force checks every substring — O(n²) of them, each checked in O(n). But neighbouring substrings overlap almost completely: abcd and bcde share three letters. A sliding window exploits that overlap.

The idea: expand right, shrink left

Keep two indexes, L and R, marking a window. Move R forward one step at a time to expand. Whenever the window breaks the rule, move L forward to shrink it until it's valid again. Record the answer whenever the window is valid.

Three templates

The difference between templates 2 and 3 is the while condition: for the longest window, shrink while it's invalid; for the shortest, shrink while it's valid.

Worked problems

A window is valid when length − (count of its most frequent letter) ≤ k — that's how many letters you'd need to change.

The "exactly K" trick

Some problems ask for the number of subarrays with exactly K of something (K distinct numbers, K odd numbers). Exactly is awkward for a window, but at most is easy — so use:

When a sliding window does NOT work

The shrinking step assumes that removing an element from the left makes the window "smaller" in the measured sense — the sum goes down, the count of a letter goes down. With negative numbers, removing an element can increase the sum, so "shrink while sum ≥ target" breaks.

Practice ladder

Interview questions

  • Your sliding-window solution has a while loop inside a for loop. Why is it O(n), not O(n²)?
  • Can you use a sliding window to find the longest subarray with sum equal to k when the array has negative numbers?

Further reading

Key takeaways

  • Sliding window = contiguous range + incrementally updatable condition → O(n).
  • Expand with right; shrink with left. For the longest window, shrink while invalid; for the shortest, shrink while valid.
  • Fixed size k: add the new element, drop a[right − k].
  • exactly(K) = atMost(K) − atMost(K − 1); count with right − left + 1.
  • Negative numbers break sum-based windows — use prefix sums instead.

Previous: Two Pointers · Next: Prefix Sums & Difference Arrays