Pattern Blueprint: The Universal Sliding Window Template

The Mental Model

A sliding window is just a sub-segment of an array that expands and shrinks based on a condition. Instead of recalculating the whole segment, we only process the element entering and the element leaving.

1. The Variable Window Template (Most Common)

Use this for problems like "Longest substring with K distinct characters."

public int findMaxWindow(int[] nums) {
    int left = 0, right = 0;
    int maxLength = 0;
    // 1. Data structure to store window state (e.g., Map, Count, Sum)
    Map<Integer, Integer> state = new HashMap<>();

    while (right < nums.length) {
        // 2. Expand: Add nums[right] to window state
        int in = nums[right];
        state.put(in, state.getOrDefault(in, 0) + 1);

        // 3. Shrink: While condition is violated, move left pointer
        while (/* window_is_invalid */) {
            int out = nums[left];
            // Remove nums[left] from state
            state.put(out, state.get(out) - 1);
            if (state.get(out) == 0) state.remove(out);
            left++;
        }

        // 4. Update Result: Window is now valid
        maxLength = Math.max(maxLength, right - left + 1);
        right++;
    }
    return maxLength;
}

2. The Fixed Window Template

Use this for problems like "Max sum of subarray of size K."

public int fixedWindow(int[] nums, int k) {
    int currentSum = 0;
    int maxSum = 0;

    for (int i = 0; i < nums.length; i++) {
        // 1. Add element to window
        currentSum += nums[i];

        // 2. If window size exceeded, remove the tail
        if (i >= k) {
            currentSum -= nums[i - k];
        }

        // 3. Record result when window is full size
        if (i >= k - 1) {
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    return maxSum;
}

3. Interview Discussion: The "Aha!" Moment

When an interviewer asks how to optimize an $O(N^2)$ array problem, look for monotonicity: "If I expand the window and it stays valid, then any smaller window inside it was also valid." This is the green light for Sliding Window.