Sliding Window

Overview

Sliding Window is one of the most powerful techniques for solving array subarray problems efficiently. It transforms brute-force O(n²) or O(n³) solutions into elegant O(n) linear-time algorithms by maintaining a "window" of elements and sliding it across the array.

At its core, sliding window keeps two pointers (left and right) that define a contiguous subarray. You expand the window by moving right to include new elements, and shrink it by moving left when the window violates a condition. This ensures each element is processed at most twice—once when added and once when removed—resulting in O(n) time complexity.

Sliding window is particularly effective for:

• Finding maximum/minimum sum subarrays
• Subarrays with specific properties
• Longest/shortest subarrays satisfying conditions
• Fixed-size window problems

Fixed vs Variable Size

Sliding window problems fall into two main categories:

Fixed-Size Window

The window maintains a constant size k. You slide it one position at a time, updating your answer based on the current window.

Example: Maximum sum of K consecutive elements

function maxSumOfKConsecutive(nums: number[], k: number): number {
  let windowSum = 0;
  // Initialize window sum
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  let maxSum = windowSum;
  
  // Slide the window
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i]; // Remove left, add right
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Time: O(n), Space: O(1)

Average of Subarrays of Size K:

function findAverages(nums: number[], k: number): number[] {
  const result: number[] = [];
  let windowSum = 0;
  
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  result.push(windowSum / k);
  
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    result.push(windowSum / k);
  }
  
  return result;
}

Time: O(n), Space: O(1)

Variable-Size Window

The window size changes dynamically based on a condition. You expand until the window becomes invalid, then shrink from the left until it's valid again. You're typically looking for the longest or shortest valid window.

Example: Smallest subarray with sum >= target

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let sum = 0;
  let minLen = Infinity;
  
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    
    // Shrink window until sum < target
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  
  return minLen === Infinity ? 0 : minLen;
}

Time: O(n), Space: O(1)

Pattern 1: Maximum Sum Subarray of Size K

Find maximum sum of any subarray of fixed size K.

function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = 0;
  
  // Initialize window
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  
  let maxSum = windowSum;
  
  // Slide window
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

Time: O(n), Space: O(1)

Pattern 2: Longest Subarray with Sum ≤ K

Find longest subarray where sum is at most K.

function longestSubarraySumAtMostK(nums: number[], k: number): number {
  let left = 0;
  let sum = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    
    // Shrink window if sum exceeds K
    while (sum > k) {
      sum -= nums[left];
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(1)

Pattern 3: Subarray with At Most K Distinct Elements

Find longest subarray with at most K distinct elements.

function longestSubarrayKDistinct(nums: number[], k: number): number {
  const freq = new Map<number, number>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
    
    // Shrink window if distinct count exceeds K
    while (freq.size > k) {
      freq.set(nums[left], freq.get(nums[left])! - 1);
      if (freq.get(nums[left]) === 0) {
        freq.delete(nums[left]);
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(k)

Pattern 4: Minimum Window Subarray

Find minimum length subarray with sum >= target.

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let sum = 0;
  let minLen = Infinity;
  
  for (let 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 === Infinity ? 0 : minLen;
}

Time: O(n), Space: O(1)

Pattern 5: Maximum Average Subarray

Find subarray of length K with maximum average.

function findMaxAverage(nums: number[], k: number): number {
  let windowSum = 0;
  
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  
  let maxSum = windowSum;
  
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum / k;
}

Time: O(n), Space: O(1)

Pattern 6: Count Subarrays with Sum K

Count number of subarrays with sum exactly K.

function subarraySum(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1); // Empty subarray
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    
    // Check if (sum - k) exists in prefix sum
    if (prefixSum.has(sum - k)) {
      count += prefixSum.get(sum - k)!;
    }
    
    prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
  }
  
  return count;
}

Time: O(n), Space: O(n)

Pattern 7: Longest Subarray with Same Elements After K Replacements

Find longest subarray where you can replace at most K elements to make all same.

function longestSubarray(nums: number[], k: number): number {
  const freq = new Map<number, number>();
  let left = 0;
  let maxFreq = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
    maxFreq = Math.max(maxFreq, freq.get(nums[right])!);
    
    // Shrink if replacements needed > k
    while ((right - left + 1) - maxFreq > k) {
      freq.set(nums[left], freq.get(nums[left])! - 1);
      left++;
      // Recalculate maxFreq (simplified - in practice may need to track)
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(n)

Pattern 8: Sliding Window Maximum

Find maximum in each sliding window of size K.

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices with smaller values
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add maximum to result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time: O(n), Space: O(k)

Pattern 9: Subarray Product Less Than K

Count subarrays with product less than K.

function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k <= 1) return 0;
  
  let left = 0;
  let product = 1;
  let count = 0;
  
  for (let right = 0; right < nums.length; right++) {
    product *= nums[right];
    
    // Shrink window until product < k
    while (product >= k) {
      product /= nums[left];
      left++;
    }
    
    // All subarrays ending at right are valid
    count += right - left + 1;
  }
  
  return count;
}

Time: O(n), Space: O(1)

Pattern 10: Longest Subarray with At Most K Odd Numbers

Find longest subarray with at most K odd numbers.

function longestSubarrayKOdd(nums: number[], k: number): number {
  let left = 0;
  let oddCount = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] % 2 === 1) {
      oddCount++;
    }
    
    // Shrink if odd count exceeds K
    while (oddCount > k) {
      if (nums[left] % 2 === 1) {
        oddCount--;
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(1)

Pattern 11: Minimum Window Subarray with All Elements

Find minimum window containing all elements from another array.

function minWindow(nums: number[], target: number[]): number[] {
  const need = new Map<number, number>();
  for (const num of target) {
    need.set(num, (need.get(num) || 0) + 1);
  }
  
  const window = new Map<number, number>();
  let left = 0, right = 0;
  let valid = 0;
  let start = 0, len = Infinity;
  
  while (right < nums.length) {
    const num = nums[right];
    right++;
    
    if (need.has(num)) {
      window.set(num, (window.get(num) || 0) + 1);
      if (window.get(num) === need.get(num)) {
        valid++;
      }
    }
    
    while (valid === need.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      
      const d = nums[left];
      left++;
      
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--;
        }
        window.set(d, window.get(d)! - 1);
      }
    }
  }
  
  return len === Infinity ? [] : nums.slice(start, start + len);
}

Time: O(n), Space: O(m) where m is target size

Pattern 12: Maximum Points from Cards

Pick K cards from either end, maximize sum.

function maxScore(cardPoints: number[], k: number): number {
  const n = cardPoints.length;
  let windowSum = 0;
  
  // Sum of first k elements
  for (let i = 0; i < k; i++) {
    windowSum += cardPoints[i];
  }
  
  let maxSum = windowSum;
  
  // Slide window: remove from left, add from right
  for (let i = k - 1; i >= 0; i--) {
    windowSum = windowSum - cardPoints[i] + cardPoints[n - k + i];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

Time: O(k), Space: O(1)

When to Use Sliding Window

Use sliding window when:

• Problem asks for subarray (contiguous) with a condition
• Need maximum/minimum sum of subarray
• Longest/shortest subarray satisfying condition
• Fixed-size window problems
• At most/at least K elements with property
• Problem involves contiguous elements, not subsequence

Key distinction: If problem asks for subsequence (non-contiguous), sliding window doesn't apply—consider dynamic programming instead.

Template (Fixed-Size Window)

function fixedWindowTemplate(nums: number[], k: number): number {
  let windowSum = 0;
  
  // Initialize window
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  
  let result = windowSum;
  
  // Slide window
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    result = Math.max(result, windowSum); // or min, or other operation
  }
  
  return result;
}

Template (Variable-Size Window)

function variableWindowTemplate(nums: number[], condition: number): number {
  let left = 0;
  let windowSum = 0;
  let result = 0;
  
  for (let right = 0; right < nums.length; right++) {
    windowSum += nums[right];
    
    // Shrink window until condition is satisfied
    while (/* window is invalid */) {
      windowSum -= nums[left];
      left++;
    }
    
    // Update result (window is now valid)
    result = Math.max(result, right - left + 1);
  }
  
  return result;
}

Time and Space Complexity Summary

• Fixed-size window: O(n) time, O(1) space
• Variable-size window: O(n) time, O(1) space (or O(k) for frequency map)
• Sliding window maximum: O(n) time, O(k) space
• Count subarrays: O(n) time, O(n) space (prefix sum map)

Practice Tips

1. Identify window type - Fixed or variable size?
2. Choose tracking structure - Sum, frequency map, or deque
3. Decide shrink condition - When is window invalid?
4. Update result correctly - After window is valid
5. Handle edge cases - Empty array, K > array length, all negative

Common Mistakes

1. Wrong window initialization - Not initializing first window correctly
2. Incorrect shrink condition - Shrinking too much or too little
3. Off-by-one errors - Window size calculation
4. Not updating result - Forgetting to update after window becomes valid
5. Edge cases - K = 0, K > array length, empty array

Related Concepts

• Two Pointers - Similar but pointers move independently
• Prefix Sum - Alternative for range sum queries
• Kadane's Algorithm - Special case for maximum subarray
• Monotonic Queue - For sliding window maximum/minimum

Sliding window is essential for array subarray problems. Master these patterns, and you'll efficiently solve a large class of array problems in coding interviews.