Learn Sliding Window – Algorithm Guide

01

Introduction to Sliding Window

The Sliding Window pattern is a subset of the two-pointer technique. It is used to convert nested loops into a single loop, reducing the time complexity from O(N²) to O(N). It is mainly used for finding subarrays or substrings that satisfy certain conditions.

What is a "Window"?

A window is a sublist formed over an array or string. By maintaining a left and right pointer, we "slide" this window forward to process continuous elements efficiently.

💡

If you see a problem asking for the "longest", "shortest", "maximum", or "minimum" contiguous subarray or substring, it's highly likely a sliding window problem!

02

Fixed Window Technique

In a fixed window problem, the length of the subarray or substring is predefined as a constant K. We need to find something (like the maximum sum) among all windows of size K.

The Algorithm

Compute the result for the first window of size K.
Slide the window by 1 element at a time.
To update the window's state, add the new element entering the window on the right, and subtract the element leaving the window on the left.

Python

def max_sum_subarray(arr, k):
    if len(arr) < k:
        return 0
        
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)
        
    return max_sum

03

Variable Window Technique

In a variable window problem, the window size changes dynamically. We expand the window from the right until a condition is violated, then shrink it from the left until the condition is satisfied again.

The Algorithm Template

Initialize left = 0, right = 0.
Expand the window by moving right and adding to the state.
If the window state violates the problem's constraint, use a while loop to shrink it by moving left and removing from the state.
Record the max/min window size that satisfies the constraint.

JavaScript

function minSubArrayLen(target, nums) {
  let minLen = Infinity;
  let left = 0;
  let sum = 0;

  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;
}

04

Common Use Cases

Sliding window optimization is highly versatile. Here are the most common patterns:

1. String Anagrams / Permutations

Finding all anagrams of a string P within a string S. You use a fixed window of size len(P) and compare frequency maps.

2. Longest Substring with K Distinct Characters

Using a hash map to track character frequencies, expand the window until you have > K distinct characters, then shrink until you are back to K.

3. Maximum Consecutive Ones (with Flips)

Given a binary array, find the maximum number of consecutive 1s you can get by flipping up to k zeros. Here, the "constraint" is that the window cannot contain more than k zeros.

05

Practice Problems

Test your understanding of the sliding window technique.

Exercise 1: Max Sum

Given arr = [2, 1, 5, 1, 3, 2] and K = 3, what is the maximum sum of any contiguous subarray of size K?

Answer: 9

Explanation: The subarrays of size 3 are: [2,1,5] (sum 8), [1,5,1] (sum 7), [5,1,3] (sum 9), [1,3,2] (sum 6). The maximum is 9.

Exercise 2: Identify Pattern

Is the problem "Find the longest substring without repeating characters" a Fixed or Variable window problem?

Answer: Variable Window

Explanation: We do not know the length of the longest substring beforehand. We must dynamically expand the window and shrink it whenever a duplicate character is encountered.

Algo Infinity Verse

Master the Sliding Window Pattern Optimize Array & String Problems