Sliding Window Technique

1. Introduction: Framing the Problem

Imagine you are looking out of a train window at a beautiful mountain range. Your window is a fixed size, say 3 meters wide. As the train moves forward, the scenery entering the right side of the window becomes visible, and the scenery leaving the left side of the window disappears.

In computer science, this is exactly what the Sliding Window pattern does. It operates over a sequential data structure (like an Array or String) to maintain a subset of data—a "window". Instead of recalculating data for every possible subset from scratch (which usually takes $O(N^2)$ or worse), we simply slide the window forward by doing two $O(1)$ operations: adding the new element on the right and removing the old element on the left.

This pattern is an absolute must-know for technical interviews. If a problem asks you to find the "longest", "shortest", or "maximum" contiguous subarray/substring, Sliding Window is almost always the answer.

2. Core Concept: Fixed vs. Variable Windows

There are two primary flavors of Sliding Window problems:

Fixed Window

The size of the window, $K$, is strictly defined in the problem description (e.g., "Find the maximum sum of a subarray of size exactly 3"). Mechanism:

1. Grow the window to size $K$.
2. Once the window hits size $K$, process the result.
3. Slide the window forward by exactly 1 step (add right element, remove left element).

Variable Window (Two Pointers)

The size of the window is unknown. Instead, the window must satisfy a condition (e.g., "Find the longest subarray whose sum is less than 10"). Mechanism:

1. Expand the window by moving the right pointer and adding elements.
2. If the window violates the condition, shrink it by moving the left pointer and removing elements until the condition is satisfied again.
3. Keep track of the optimal window size seen so far.

3. Beginner Code Example: Fixed Sliding Window

Problem Statement: Given an array of integers and an integer $K$, find the maximum sum of any contiguous subarray of size $K$.

Brute Force (Suboptimal)

Calculate the sum of every window of size $K$ from scratch.

public int maxSumBrute(int[] arr, int k) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i <= arr.length - k; i++) {
        int currentSum = 0;
        for (int j = i; j < i + k; j++) {
            currentSum += arr[j];
        }
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

Time: $O(N \times K)$. If $N=100,000$ and $K=50,000$, this takes 5 billion operations!

Optimal Sliding Window Approach

public class FixedWindow {
    public static int maxSumSliding(int[] arr, int k) {
        if (arr.length < k) return -1; // Edge case
        
        int maxSum = 0;
        int currentSum = 0;
        
        // 1. Build the initial window of size K
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;
        
        // 2. Slide the window from index K to the end
        for (int i = k; i < arr.length; i++) {
            // Add the new element entering the window
            // Subtract the old element leaving the window
            currentSum = currentSum + arr[i] - arr[i - k];
            
            // Update the maximum
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We look at each element a constant number of times.
• Space Complexity: $O(1)$. We only maintain a few integer variables.

4. Intermediate Code Example: Variable Sliding Window

Problem Statement: (LeetCode 209) Minimum Size Subarray Sum. Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0.

Because the window size is not given, this is a Variable Window.

public class VariableWindow {
    public static int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;
        int left = 0;
        
        // 'right' expands the window
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            
            // If condition is met, try to shrink the window from the left
            // to find the MINIMAL length!
            while (currentSum >= target) {
                // Update our optimal answer
                minLength = Math.min(minLength, right - left + 1);
                
                // Shrink window
                currentSum -= nums[left];
                left++; 
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. A common mistake is thinking the nested while loop makes it $O(N^2)$. It doesn't! The left pointer only moves forward and can move at most $N$ times across the entire algorithm. Thus, both left and right traverse the array exactly once, giving $2N$ operations $\rightarrow O(N)$.
• Space Complexity: $O(1)$.

5. Advanced Code Example: Longest Substring with Condition

Problem Statement: (LeetCode 3) Longest Substring Without Repeating Characters. Given a string s, find the length of the longest substring without repeating characters.

Here, the sliding window operates on a String (which is backed by a char array) and we must use a HashSet or frequency array to track the "violating condition" (repeating characters).

import java.util.HashSet;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> windowSet = new HashSet<>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            
            // If we see a duplicate, the window is INVALID.
            // Shrink from the left until the duplicate is removed.
            while (windowSet.contains(rightChar)) {
                windowSet.remove(s.charAt(left));
                left++;
            }
            
            // Window is now valid again. Add the new character.
            windowSet.add(rightChar);
            
            // Update the maximum length found so far
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the length of the string. The left and right pointers touch each character at most twice.
• Space Complexity: $O(\min(N, M))$ where $M$ is the size of the charset (e.g., 26 for lowercase English, 128 for ASCII). The HashSet stores at most $M$ characters.

6. Common Mistakes Beginners Make

1. Forgetting to subtract the outgoing element

   • The Mistake: In a fixed window, doing currentSum += arr[i] but forgetting currentSum -= arr[i - k]. The window just keeps growing instead of sliding.

2. Off-By-One Errors on Window Size

   • The Mistake: Calculating the length of the window as right - left.
   • The Fix: In 0-indexed arrays, the inclusive length between two pointers is right - left + 1. (e.g., pointers at index 2 and index 4. Length is $4 - 2 + 1 = 3$. Elements are 2, 3, 4).

3. Thinking Nested Loops always equal $O(N^2)$

   • The Mistake: Looking at the while loop inside the for loop in a Variable Window algorithm and confidently telling the interviewer the time complexity is $O(N^2)$.
   • The Fix: Trace the pointers. If the inner loop only moves a pointer strictly forward (never resetting to 0), the total inner iterations across the entire program execution is capped at $N$. $N + N = O(N)$.

4. Variable Window with Negative Numbers

   • The Mistake: Using a Sliding Window to find the shortest subarray summing to K when the array contains negative numbers.
   • Why it's wrong: Sliding window relies on a monotonic property: expanding the window increases the sum, shrinking it decreases the sum. Negative numbers destroy this property. (You must use Prefix Sum + HashMap for negative numbers!).

7. Interview Q&A

Q1: How do you identify a Sliding Window problem in an interview? Answer: The problem will usually mention an array or string and ask for a "contiguous" segment. Look for keywords like "longest", "shortest", "maximum", or "minimum" subarray or substring.

Q2: What is the difference between Sliding Window and Two Pointers? Answer: Sliding Window is a specific sub-type of Two Pointers. Two Pointers can start at opposite ends and move inwards (like reversing an array), or move at different speeds (Fast/Slow pointers). Sliding Window specifically uses two pointers moving in the same direction to define a continuous "chunk" of data.

Q3: (LeetCode 76) Minimum Window Substring. How do you track multiple conditions in a sliding window? Answer: When searching for a substring that contains all characters of another string, use two frequency maps (or arrays). One map tracks the target characters, the other tracks the current window's characters. You also maintain a matchCount variable so you don't have to compare the two maps on every iteration—you just compare matchCount to target.length().

Q4: Can Sliding Window be used on Trees or Graphs? Answer: Generally, no. Sliding Window inherently requires a linear, contiguous data structure where the concepts of "previous element" and "next element" are strictly linear.

8. Practice Problems

1. Maximum Average Subarray I (LeetCode 643)
   • Goal: Easiest Fixed Window problem. Find max average of size K.
2. Fruit Into Baskets (LeetCode 904)
   • Hint: This is just a disguise for "Longest Substring with At Most 2 Distinct Characters". Use a Variable Window with a HashMap!
3. Sliding Window Maximum (LeetCode 239)
   • Hint: This is a strictly Advanced/Hard problem. Standard sliding window is $O(N \times K)$. To get $O(N)$, you must use a Monotonic Deque to track the maximums inside the window.

9. Summary

• The Core Idea: Never recompute overlapping data. Maintain a running state and just factor in the single new element and factor out the single old element.
• Fixed Window: The pointers are locked exactly $K$ distance apart. They move in lockstep.
• Variable Window: The right pointer acts as an explorer, blindly expanding. The left pointer acts as a cleaner, following behind and shrinking the window whenever rules are broken.
• Performance: Transforms $O(N^2)$ naive subarray generation into elegant $O(N)$ single-pass algorithms.