Sliding Window Pattern

Sliding Window Pattern

Many problems ask about contiguous runs of an array or string: the maximum sum of k consecutive numbers, the longest substring without repeating characters, the shortest subarray whose sum reaches a target. The brute force examines every possible window, which is O(n²) windows, often each recomputed from scratch.

A sliding window keeps one window, defined by a left and a right index, and updates it incrementally. When the window moves, you add the element entering on the right and remove the one leaving on the left, instead of recomputing everything. Each element enters and leaves at most once, so the whole scan is O(n).

There are two kinds:

• Fixed-size windows: the length k is given.
• Variable-size windows: the window grows and shrinks to satisfy a condition, and you want the longest or shortest valid one.

Fixed-size window

int maxSumOfK(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];        // first window
    int best = windowSum;
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right] - nums[right - k];            // add the new element, drop the oldest
        best = Math.max(best, windowSum);
    }
    return best;
}

That's O(n) instead of O(n·k). Other fixed-window problems (averages of every window, the first negative number in each window, anagrams of a pattern) differ only in what summary you maintain: a sum, a count array, or a deque for maximums.

Sliding window maximum needs a trick, because a maximum can't be "un-added". Keep a monotonic deque of indexes whose values are decreasing. Drop smaller values from the back when a new element arrives (they can never be the maximum again), and drop indexes that fall out of the window from the front. The front is always the current maximum, and each index enters and leaves once, so it's O(n).

Variable-size window: the expand/shrink template

for right in 0..n-1:
    add element[right] to the window state
    while the window is INVALID:           (for "longest valid" problems)
        remove element[left] from the state
        left++
    record the answer using the valid window [left, right]

The right pointer only moves forward, and so does the left one. Together they move at most 2n steps. That's why it's O(n), despite the nested while.

Longest substring without repeating characters

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;          // jump past the previous occurrence
        }
        lastSeen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Storing each character's last index lets the left edge jump directly instead of stepping one at a time. The >= left check ignores stale occurrences that are already outside the window, which is a commonly missed detail.

Longest substring with at most k distinct characters

int longestKDistinct(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        count.merge(s.charAt(right), 1, Integer::sum);
        while (count.size() > k) {                             // too many distinct → shrink
            char out = s.charAt(left++);
            if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

"Fruit Into Baskets" is this problem with k = 2. "Max Consecutive Ones III" (flip at most k zeros) is the same template, with the state being "zeros in the window".

Shortest window: shrink while valid

For minimum-length problems, flip the inner loop: expand until the window becomes valid, then shrink while it stays valid, recording the answer inside the shrinking loop.

int minSubArrayLen(int target, int[] nums) {          // shortest subarray with sum ≥ target (positive numbers)
    int left = 0, sum = 0, best = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {                         // valid: try to make it shorter
            best = Math.min(best, right - left + 1);
            sum -= nums[left++];
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

Minimum Window Substring (the smallest window containing all characters of t) uses the same shape, with character counts as the state. See String Two-Pointer Problems.

When the sliding window does not work

The template relies on monotonicity: extending the window must only move the condition in one direction (the sum only grows, the distinct count never drops), so that when a window becomes invalid, shrinking is the only fix.

• Negative numbers break this for sum problems. Adding an element can decrease the sum, so you can't decide which pointer to move. For "subarray sum equals k" with negatives, use prefix sums + a hash map instead (see Prefix Sums).
• Non-contiguous selections (subsequences) aren't windows at all. They usually need DP.

Counting subarrays with "exactly k"

Windows naturally answer "at most k". A useful identity turns that into "exactly k":

exactly(k) = atMost(k) − atMost(k − 1)

For example, the number of subarrays with exactly k distinct integers, where atMost(k) adds right − left + 1 (the number of valid subarrays ending at right) at each step.

How to recognise it

• The problem talks about contiguous subarrays or substrings.
• It asks for the longest, shortest, maximum, or count of windows meeting a condition.
• The condition can be tracked incrementally (a sum, counts, distinct count, a max via a deque).
• The brute force is "check every subarray".

Follow-up questions this topic invites — and their answers

Q: Why is the variable-size window O(n) when it has a nested loop? A: Both pointers only move forward. right advances n times in total, and left can advance at most n times in total across the entire run, not per iteration of the outer loop. So the combined work is O(n).

Q: Why doesn't the sliding window work for "subarray sum equals k" with negative numbers? A: Shrinking or growing the window no longer moves the sum predictably. A negative element can make a longer window's sum smaller. Without that monotonic behaviour, there's no rule for which pointer to move. Prefix sums with a hash map handle arbitrary integers in O(n).

Q: Longest vs shortest window: what changes in the template? A: For the longest valid window, you shrink while the window is invalid, then record after the loop. For the shortest valid window, you shrink while the window is valid, and record inside the loop before each shrink.

Q: How do you get the maximum of every window of size k in O(n)? A: Maintain a deque of indexes with decreasing values. Pop smaller values from the back before pushing a new index, pop the front when it leaves the window, and read the maximum from the front. Each index is pushed and popped once.

Q: How do you count subarrays with exactly k distinct elements? A: Compute the number with at most k distinct and subtract the number with at most k − 1. Each is a standard sliding window that adds right − left + 1 valid subarrays per step.