Sliding Window

What is Sliding Window?

Sliding window is a technique that maintains a window (subarray/substring) and slides it across the data structure.

Visual Example

Find max sum of 3 consecutive elements:
arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]
k = 3

Window 1: [1, 3, 2] 6 -1 4 1 8 2  sum = 6
          ↑-----↑

Window 2: 1 [3, 2, 6] -1 4 1 8 2  sum = 11
             ↑-----↑

Window 3: 1 3 [2, 6, -1] 4 1 8 2  sum = 7
                ↑-----↑

... and so on

Why It Works

Instead of recalculating from scratch for each window:

• Add the new element entering the window
• Remove the old element leaving the window

This gives O(1) update per window.

Two Types

1. Fixed-size window: Window size is constant (k)
2. Variable-size window: Window size changes based on condition

When to Use

• Subarray problems with contiguous elements
• Maximum/minimum sum of k elements
• Longest substring with condition
• Shortest substring with condition

Template

int fixedWindow(int[] arr, int k) {
    // 1. Initialize window
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    int maxSum = windowSum;
    
    // 2. Slide the window
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];  // add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

Example: Max Sum Subarray of Size K

public int maxSum(int[] arr, int k) {
    int n = arr.length;
    if (n < k) return -1;
    
    // Compute sum of first window
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    int maxSum = windowSum;
    
    // Slide the window
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}
// Time: O(n), Space: O(1)

Dry Run

arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 4

Initial window: [1, 4, 2, 10] → sum = 17

Slide 1: add 2, remove 1 → [4, 2, 10, 2] → sum = 18
Slide 2: add 3, remove 4 → [2, 10, 2, 3] → sum = 17
Slide 3: add 1, remove 2 → [10, 2, 3, 1] → sum = 16
Slide 4: add 0, remove 10 → [2, 3, 1, 0] → sum = 6
Slide 5: add 20, remove 2 → [3, 1, 0, 20] → sum = 24

Max sum = 24

Complexity

• Time: O(n) - single pass
• Space: O(1) - only variables

Template

int variableWindow(int[] arr, int target) {
    int left = 0;
    int windowSum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < arr.length; right++) {
        // 1. Expand: add element to window
        windowSum += arr[right];
        
        // 2. Contract: remove elements from left
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= arr[left];
            left++;
        }
    }
    
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Example: Minimum Size Subarray Sum (LeetCode 209)

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
// Time: O(n), Space: O(1)

Dry Run

nums = [2,3,1,2,4,3], target = 7

right=0: sum=2, < 7
right=1: sum=5, < 7
right=2: sum=6, < 7
right=3: sum=8, >= 7 → minLen=4, sum=6
right=4: sum=10, >= 7 → minLen=4, sum=6, sum=4
right=5: sum=7, >= 7 → minLen=3, sum=4

Output: 3

When to Use Variable Window

• "Longest substring with at most K distinct characters"
• "Minimum window containing target"
• "Subarray with sum >= target"
• "Longest substring without repeating characters"

Pattern 1: Maximum/Minimum of Size K

// Max of each window of size k
int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    
    for (int i = 0; i <= n - k; i++) {
        int max = nums[i];
        for (int j = i; j < i + k; j++) {
            max = Math.max(max, nums[j]);
        }
        result[i] = max;
    }
    return result;
}
// Time: O(n × k) - can optimize with deque to O(n)

Pattern 2: Longest Substring with K Distinct Characters

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        map.merge(s.charAt(right), 1, Integer::sum);
        
        while (map.size() > k) {
            char leftChar = s.charAt(left);
            map.merge(leftChar, -1, Integer::sum);
            if (map.get(leftChar) == 0) map.remove(leftChar);
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(k)

Pattern 3: Longest Substring Without Repeating Characters (LeetCode 3)

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right))) {
            left = Math.max(left, map.get(s.charAt(right)) + 1);
        }
        map.put(s.charAt(right), right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
// Time: O(n), Space: O(min(n, alphabet size))

Pattern 4: Permutation in String (LeetCode 567)

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    
    int[] s1Count = new int[26];
    int[] s2Count = new int[26];
    
    for (int i = 0; i < s1.length(); i++) {
        s1Count[s1.charAt(i) - 'a']++;
        s2Count[s2.charAt(i) - 'a']++;
    }
    
    if (Arrays.equals(s1Count, s2Count)) return true;
    
    for (int i = s1.length(); i < s2.length(); i++) {
        s2Count[s2.charAt(i) - 'a']++;
        s2Count[s2.charAt(i - s1.length()) - 'a']--;
        if (Arrays.equals(s1Count, s2Count)) return true;
    }
    return false;
}
// Time: O(n), Space: O(1)

When to Use Each Pattern