Sliding Window pattern: types, examples, and LeetCode problems

The main idea of the Sliding Window pattern is that instead of recalculating information for every possible subarray or substring, we maintain a window represented by two boundaries: left and right. As the window moves, new elements are added from the right and unnecessary elements are removed from the left. This allows the algorithm to efficiently track information such as sums, frequencies, distinct elements, or other conditions while processing the input.

The main advantage of Sliding Window is that it often reduces a brute-force O(n²) solution to O(n).

If the problem description contains something like find the longest contiguous subarray or substring or other similar phrases:

• longest substring or shortest subarray
• maximum sum subarray of size k
• at most k, at least k, exactly k
• no repeating characters or contains all required characters
• maximum number of...
• minimum length...

we should consider the Sliding Window pattern as a possible approach.

There are two main types of the Sliding Window pattern:

• Fixed-size Sliding Window
• Variable-size Sliding Window

Let’s consider both approaches step by step.

Fixed-size Sliding Window

The window always contains exactly k elements.

Example: Find the maximum sum of any subarray of length k. (Something like LeetCode 643. Maximum Average Subarray I)

nums = [2, 1, 5, 1, 3, 2]
k = 3

Instead of calculating every sum independently, update it.

Generic template is:

int left = 0;

for(int right = 0; right < nums.size(); right++) {
  add(nums[right]);

  if(right - left + 1 > k) {
    remove(nums[left]);
    left++;
  }

  if(right - left + 1 == k)updateAnswer();
}

The typical complexity is:

Time: O(n)
Space: O(1) or O(k) if additional window data is stored.

Variable-size Sliding Window

The window size changes depending on some condition.
The right pointer normally expands the window.
The left pointer shrinks it when the current window violates the required condition.
This is probably the most important Sliding Window variation for interviews.

Generic template is:

int left = 0;

for(int right = 0; right < n; right++) {
  add(nums[right]);

  while(windowIsInvalid()) {
    remove(nums[left]);
    left++;
  }

  updateAnswer();
}

The typical complexity is:

Time: O(n) - because both left and right pointers move forward at most n times.
Space: O(1) - if only a few variables are maintained or O(k) or O(n) if the window uses a frequency map, set, or other additional data structure.

Very important question for interview:
A Sliding Window solution often contains:

for(...) {
    while(...) {
        ...
    }
}

Why two nested loops can still be O(n)?

At first glance, two nested loops may look like O(n²). But in reality, each pointer moves only forward:

right: 0 → 1 → 2 → ... → n-1
left:  0 → 1 → 2 → ... → n-1

Each element can:

• enter the window once
• leave the window once

So the total number of pointer movements is approximately 2n. Therefore O(2n) = O(n).

LeetCode problems for the Sliding Window pattern

3. Longest Substring Without Repeating Characters
30. Substring with Concatenation of All Words
76. Minimum Window Substring
209. Minimum Size Subarray Sum
424. Longest Repeating Character Replacement
438. Find All Anagrams in a String
567. Permutation in String
643. Maximum Average Subarray I
904. Fruit Into Baskets
1004. Max Consecutive Ones III
1456. Maximum Number of Vowels in a Substring of Given Length
1493. Longest Subarray of 1's After Deleting One Element
2024. Maximize the Confusion of an Exam
2958. Length of Longest Subarray With at Most K Frequency
3090. Maximum Length Substring With Two Occurrences