Sliding Window

Expand–Shrink

Keep expanding the right boundary until a constraint is violated, then shrink from the left until it's valid again. Track the best valid window seen. Used in minimum window substring problems.

O(n)

How It Works

Expand–shrink is the two-phase rhythm behind minimum-window problems. Phase one: move the right boundary outward, absorbing elements until the window satisfies the requirement — for example, it covers every character of a target string. Phase two: contract from the left, discarding elements while the window stays valid, recording the smallest valid window before it breaks. Then resume expanding.

Brute force would test all O(n²) substrings and validate each in O(n). Here, each element is added once and removed once, and validity is tracked incrementally with counters, so the total cost is O(n) time with O(k) space for the character or element counts being matched.

Step-by-Step Visualization

Find longest substring without repeats

Window [0..0]

Windowa

Max1

1/5

Code

Java

static int lengthOfLongestSubstring(String s) {
  Set<Character> set = new HashSet<>();
  int left = 0, maxLen = 0;

  for (int right = 0; right < s.length(); right++) {
    while (set.contains(s.charAt(right))) {
      set.remove(s.charAt(left++));
    }
    set.add(s.charAt(right));
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

// Example: lengthOfLongestSubstring("abcabcbb") → 3

Tips & Gotchas

1Keep expanding right until a condition is violated

2Then shrink from left until the condition is restored

3Use a frequency map or set to track the window state

Practice Problems

1Minimum Window Substring
2Minimum Size Subarray Sum
3Substring with Concatenation of All Words

About the Sliding Window Pattern

Instead of recalculating from scratch for every subarray, keep a 'window' that slides across the array. As the window moves right, add the new element and remove the old one. This turns O(n·k) brute force into O(n).

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

How does expand–shrink differ from a plain variable-size window?

They are close cousins, but the emphasis flips. A typical variable window maximizes a valid window and shrinks only when validity breaks; expand–shrink minimizes, so once the window becomes valid you shrink aggressively while it remains valid, capturing the tightest window at each step.

How do I check window validity in O(1) during shrinking?

Maintain a 'satisfied count' alongside the frequency map — for instance, the number of required characters whose needed quota is currently met. Increment or decrement it as characters enter and leave, so validity is a single integer comparison rather than a full map scan.