Sliding Window

Concept

The Sliding Window is an extension of the Two Pointers technique.
Whenever a problem asks you to find a “contiguous subarray” or “substring” that satisfies a specific condition (e.g., maximum sum, longest string without repeating characters), it is almost always a Sliding Window problem.

Instead of pointing at two discrete items, the two pointers (Left and Right) define the boundaries of a “Window”. You expand the window by moving Right, and shrink the window by moving Left.

Mental Model

Problem: Find the maximum sum of any contiguous subarray of size 3.
Array: [2, 1, 5, 1, 3, 2]

Naive $O(N \times K)$ Approach:

• Check [2, 1, 5] -> Sum 8
• Check [1, 5, 1] -> Sum 7
• Check [5, 1, 3] -> Sum 9
  Notice the duplicated work? We added 1 and 5 three separate times.

Sliding Window $O(N)$ Approach:

• Start window: [2, 1, 5]. Sum = 8.
• To slide the window right, we subtract the number falling out (2) and add the new number coming in (1).
• New Sum = 8 - 2 + 1 = 7.
• We slid the window in exactly $O(1)$ constant math operations, rather than recalculating the entire chunk!

1. Fixed Window Size

Used when the problem explicitly gives you the size of the window (e.g., “size K”).

// Find the max sum of a subarray of exactly size K
function maxSumSubarray(arr: number[], k: number): number {
    let windowSum = 0;
    let maxSum = 0;

    // 1. Build the initial window of size K
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // 2. Slide the window through the rest of the array
    for (let i = k; i < arr.length; i++) {
        // Add new right element, subtract old left element
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

2. Dynamic Window Size

Used when the problem asks for the “longest” or “shortest” subarray that meets a condition. The window expands and contracts dynamically.

Problem: Smallest subarray with a sum greater than or equal to Target (e.g., 7).
Array: [2, 1, 5, 2, 8]

1. Right pointer expands the window until the sum reaches 7. (e.g., [2, 1, 5], Sum = 8).
2. We found a valid window! Save its length (3).
3. Now, the Left pointer aggressively shrinks the window from behind to see if we can make it shorter.
4. Remove 2. Window is [1, 5], Sum = 6. Condition broken!
5. Stop shrinking. Go back to expanding Right.

function minSubArrayLen(target: number, arr: number[]): number {
    let minLength = Infinity;
    let windowSum = 0;
    let left = 0;

    // Expand the window with Right pointer
    for (let right = 0; right < arr.length; right++) {
        windowSum += arr[right];

        // While the condition is met, try to shrink it with Left pointer
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            
            windowSum -= arr[left]; // Remove left element
            left++;                 // Shrink window
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

Interview Questions

Q: Why does the Dynamic Sliding Window have an $O(N)$ time complexity if there is a while loop nested inside a for loop? Shouldn’t nested loops be $O(N^2)$?
A: This is a classic trick question.
It is $O(N)$ because the Left pointer and the Right pointer only ever move forward. The Left pointer is never reset back to 0.
In the absolute worst-case scenario, the Right pointer touches every element exactly once, and the Left pointer touches every element exactly once. Therefore, the maximum number of operations is $2N$. We drop the constant, making it strictly $O(N)$.

Q: You are asked to find the longest substring with exactly K distinct characters. What data structure should you pair with the Sliding Window to track the “distinct characters”?
A: A Hash Map (or Frequency Map).
As the Right pointer expands, you add characters to the Hash Map. The size of the Hash Map’s keys tells you exactly how many distinct characters are currently in the window. If the keys exceed K, you start advancing the Left pointer, decrementing frequencies in the Hash Map. When a character’s frequency hits 0, you physically delete it from the Hash Map, shrinking your distinct count back down to K.