Sliding Window

Process a window of elements that slides across an array or string.

What is this pattern?

The sliding window technique uses two pointers to define a window of elements. You expand the window by moving the right pointer and shrink it by moving the left pointer — avoiding nested loops and bringing O(n²) solutions down to O(n).

When to use it

Problem involves a contiguous subarray or substring
Looking for a maximum, minimum, or count within a window
Keywords: "longest", "shortest", "contains", "subarray", "substring"
Window size is either fixed or dynamic based on a condition

Key Insight

Instead of recomputing the entire window on every step, maintain a running state (sum, freq map, etc.) and update it incrementally as the window slides.

Java Template

Template.java

// Fixed-size window
int windowSum = 0, maxSum = 0;
for (int i = 0; i < nums.length; i++) {
    windowSum += nums[i];
    if (i >= k - 1) {
        maxSum = Math.max(maxSum, windowSum);
        windowSum -= nums[i - (k - 1)];
    }
}

// Variable-size window (two pointers)
int left = 0, result = 0;
Map<Character, Integer> freq = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
    freq.merge(s.charAt(right), 1, Integer::sum);
    // shrink window while condition violated
    while (freq.size() > k) {
        char c = s.charAt(left++);
        freq.merge(c, -1, Integer::sum);
        if (freq.get(c) == 0) freq.remove(c);
    }
    result = Math.max(result, right - left + 1);
}