Sliding Window

Variable Size Window

The window grows and shrinks to satisfy a condition. Expand right to include more, shrink left when the condition breaks. Classic example: longest substring with at most K distinct characters.

O(n)

How It Works

A variable-size sliding window grows and shrinks as it scans, always trying to keep the window valid under some condition. The right pointer advances to admit new elements; whenever the condition breaks — say the count of distinct characters exceeds K — the left pointer advances until validity is restored. You record the best window (longest or shortest, depending on the goal) along the way.

This beats the brute-force enumeration of all O(n²) subarrays because each pointer only ever moves forward. Both pointers traverse the array at most once, so total work is O(n), with extra space limited to whatever state (often a frequency map) is needed to test the condition.

Step-by-Step Visualization

Target sum >= 7. Start with empty window

Sum2

Min Length∞

1/5

Code

Java

static int minSubarrayLen(int target, int[] nums) {
  int left = 0, sum = 0, minLen = Integer.MAX_VALUE;

  for (int right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left++];
    }
  }

  return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

// Example: minSubarrayLen(7, new int[]{2,3,1,2,4,3}) → 2

Tips & Gotchas

1Use a hash set or map to track window contents

2Expand right to grow, shrink left when constraint violated

3The window size is dynamic — determined by the problem condition

Practice Problems

1Longest Substring Without Repeating Characters
2Longest Substring with At Most K Distinct Characters
3Max Consecutive Ones III
4Fruit Into Baskets

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 do I know a problem calls for a variable-size window?

Look for phrases like 'longest subarray such that...' or 'shortest substring containing...' where the constraint depends on window contents, not a fixed length. If the valid-window property is monotonic — expanding can only break it, shrinking can only restore it — a variable window applies.

Why is the variable window O(n) even though there are two nested loops?

The inner while-loop advances the left pointer, and that pointer never moves backward. Across the entire run, left moves at most n times total, so the combined work of both loops is bounded by 2n, which is O(n).

What state do I keep inside the window?

Keep the minimum needed to check the constraint in O(1): a running sum for sum constraints, a hash map of counts for distinct-character constraints, or a counter of zeros for flip problems. Update it incrementally as elements enter and leave.