Sliding Window Pattern

The Sliding Window pattern is a coordinate expansion technique that tracks a contiguous subarray (window) within a larger collection, shifting the window boundaries to find optimal ranges without re-evaluating shared elements.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks about a contiguous subarray, substring, or subsegment.
• You need to find a maximum, minimum, or target property of a contiguous block (e.g. “longest substring without repeating characters”).
• A naive nested-loop solution runs in O(n²) time by recalculating overlapping ranges.

How It Works

Instead of checking all possible contiguous subarrays using nested loops (O(n²)), you maintain a window defined by two pointers: left and right.

• Expand the window by moving the right pointer to include new elements.
• When the window violates constraints, shrink it by moving the left pointer until constraints are satisfied again.
• Record the optimal window size at each valid step.

For example, to find the longest subarray of positive numbers with a sum less than or equal to 6:

1. Initialize: nums = [2, 1, 5, 2], left = 0, right = 0, currentSum = 0.
2. Move right = 0 (val 2): currentSum = 2. Valid. Length = 1.
3. Move right = 1 (val 1): currentSum = 3. Valid. Length = 2.
4. Move right = 2 (val 5): currentSum = 8. Invalid.
5. Shrink: Move left to 1. currentSum = 8 - nums[0] = 6. Valid. Length = 2.
6. Continue until the end.

Complexity, With Caveats

• Time Complexity: O(n) where n is the length of the collection. Although there is a nested loop to shrink the window, the left and right pointers only move forward. Each pointer visits each index at most once, making the total steps at most 2n.
• Space Complexity: O(k) or O(1) space. If you need to track element frequencies inside the window, you use a hash table of size k, where k is the size of the alphabet or unique numbers.

Minimal Code Template

import java.util.HashMap;
import java.util.Map;

public class SlidingWindowTemplate {
    // Dynamic Window (Longest Subarray with Sum <= Target)
    public int findMaxWindow(int[] nums, int target) {
        int left = 0;
        int currentSum = 0;
        int maxLen = 0;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right]; // expand window

            // shrink window until constraint is satisfied
            while (currentSum > target) {
                currentSum -= nums[left];
                left++;
            }

            // update optimal result
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

# Dynamic Window (Longest Subarray with Sum <= Target)
def find_max_window(nums: list[int], target: int) -> int:
    left = 0
    current_sum = 0
    max_len = 0

    for right in range(len(nums)):
        current_sum += nums[right]  # expand window

        # shrink window until constraint is satisfied
        while current_sum > target:
            current_sum -= nums[left]
            left += 1

        # update optimal result
        max_len = max(max_len, right - left + 1)

    return max_len

#include <vector>
#include <algorithm>

class SlidingWindowTemplate {
public:
    // Dynamic Window (Longest Subarray with Sum <= Target)
    int findMaxWindow(const std::vector<int>& nums, int target) {
        int left = 0;
        int currentSum = 0;
        int maxLen = 0;

        for (int right = 0; right < nums.size(); right++) {
            currentSum += nums[right]; // expand window

            // shrink window until constraint is satisfied
            while (currentSum > target) {
                currentSum -= nums[left];
                left++;
            }

            // update optimal result
            maxLen = std::max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

Where This Pattern Falls Short

• Non-contiguous bounds: Sliding Window only works if the target elements must form a contiguous block. If elements can be chosen from arbitrary positions in the array, you must use other strategies (like Backtracking or Dynamic Programming).
• Negative values with sum constraints: If the array contains negative numbers, the sum relation is no longer monotonic (expanding the window can decrease the sum, and shrinking it can increase it). In these cases, sliding window fails, and you must use prefix sums with hash maps.

Related Patterns, Compared

• Two Pointers: choose this instead when you need to compare two distant elements in a sorted array, rather than tracking a contiguous range block.
• Prefix Sum: choose this instead when the array contains negative numbers and you need to find subarrays that sum to a target value.

Frequently Asked Questions

What is the difference between a fixed and dynamic sliding window? A fixed window maintains a constant size K throughout the iteration (e.g. finding the maximum sum of any subarray of size 3). A dynamic window expands and shrinks based on whether constraints are met.

How does sliding window avoid O(n²) complexity? It avoids O(n²) by reusing calculations from overlapping elements. When the window shifts, you subtract the element that fell out on the left and add the new element on the right, instead of summing all elements in the window again.

What does this pattern test in interviews? It tests your ability to optimize coordinate indices, write clean while loop constraints, and identify monotonic relationships in arrays.