Fixed Size Sliding Window - Complete Guide with Visualization

Overview

The Sliding Window pattern is a fundamental technique in algorithmic problem solving. It involves creating a “window” over a portion of data (like an array or string) and moving that window to process the data efficiently.

This is Part 1 of our Sliding Window series:

Fixed Size Window (this article): The window size k is constant. We slide it one step at a time.
Variable Size Window: The window grows or shrinks based on certain conditions (often used for “longest/shortest subarray” problems).

In this guide, we’ll focus on the Fixed Size Sliding Window using classic problems.

💡 Key Concept

Instead of recalculating the properties of the entire window every time it moves, we only update the changes:

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

This optimization transforms O(n·k) algorithms into O(n).

Problem 1: Maximum Vowels (LC 1456)

We’ll use LeetCode 1456: Maximum Number of Vowels in a Substring of Given Length as our example.

Description: Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Example:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Interactive Visualization

Let’s walk through how the algorithm processes the string. Watch how the window (blue frame) slides and how we maintain the count without re-scanning.

Initializing...

Observation: Notice that in each step, we only look at two elements: the one entering (index i) and the one leaving (index i - k + 1).

Optimized Solution

A naive solution would extract every substring of length k and count its vowels. That would be O(n·k), which is too slow for large inputs.

The sliding window approach allows us to solve this in O(n) time.

Optimization Tips

Avoid Set for small character sets: Checking c == 'a' || c == 'e' ... is faster and uses less memory than Set<Character>.
Early Exit: If we find a window where count == k, we can return immediately because we can’t find more than k vowels in a window of size k.

Complexity Analysis

	Complexity
Time	O(n), where n is the length of the string. Each character is visited once, and all operations (vowel check, add, remove) are O(1).
Space	O(1). Only a few variables are used regardless of input size.

Problem 2: Sliding Subarray Beauty (LC 2653)

This is a more advanced sliding window problem that combines the fixed-size window technique with counting sort.

Description: Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Example:

Input: nums = [1, -1, -3, -2, 3], k = 3, x = 2
Output: [-1, -2, -2]
Explanation:
- Subarray [1, -1, -3]: negatives sorted = [-3, -1], 2nd smallest = -1
- Subarray [-1, -3, -2]: negatives sorted = [-3, -2, -1], 2nd smallest = -2
- Subarray [-3, -2, 3]: negatives sorted = [-3, -2], 2nd smallest = -2

💡 Key Insight: Counting Sort Optimization

Since the constraints state -50 ≤ nums[i] ≤ 50, we can use a counting array of size 50 to track the frequency of negative numbers. Instead of sorting each window, we iterate through the counting array to find the x-th smallest negative in O(50) = O(1) time.

Beauty Visualization

Watch how the algorithm maintains a counting array for negative numbers and finds the x-th smallest in each window.

Initializing...

Observation: The counting array tracks negative numbers (-50 to -1). To find the x-th smallest, we scan from the smallest (index 0 = -50) and accumulate counts until we reach x.

Subarray Beauty Solution

Complexity Analysis

	Complexity
Time	O(n × 50) = O(n), where n is the length of nums. For each window, we scan the counting array of fixed size 50 to find the x-th smallest.
Space	O(50) = O(1). The counting array has a fixed size of 50 regardless of input size.

Template & Pattern

Here is a general template you can use for almost any Fixed Size Sliding Window problem.

How to use it:

Initialize your state (sum, count, hash map, etc.).
Loop through the array/string with index i.
Add the element arr[i] to your state.
Skip logic until the window reaches size k (if (i < k - 1) continue).
Update your answer (max, min, etc.).
Remove the element arr[i - k + 1] from your state to prepare for the next iteration.

Complexity Summary

⏱️ Time Complexity

Problem	Time	Notes
LC 1456 (Max Vowels)	O(n)	Each character visited once, O(1) per operation
LC 2653 (Subarray Beauty)	O(n)	O(50) = O(1) to find x-th smallest per window

💾 Space Complexity

Problem	Space	Notes
LC 1456 (Max Vowels)	O(1)	Only a few variables
LC 2653 (Subarray Beauty)	O(1)	Fixed-size counting array (size 50)

Key Insight: Fixed-size sliding window problems typically achieve O(n) time by updating state incrementally instead of recalculating for each window.

Next in Series

Ready to tackle more challenging sliding window problems? Continue to Part 2: Variable Size Sliding Window, where you’ll learn:

How to solve “longest/shortest subarray” problems
The critical difference between “longest” and “shortest” patterns
Classic interview problems: LC 76 (Minimum Window Substring), LC 487, and more