Sliding Window Algorithm: Fixed & Dynamic Window Strategies0%
Prefix Sums & Difference Arrays for Constant-Time Range Queries

Sliding Window Algorithm: Fixed & Dynamic Window Strategies

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Sliding Window Algorithm: Fixed & Dynamic Window Strategies

The Sliding Window Algorithm is a sub-array and sub-string optimization technique. Instead of recalculating contiguous segments from scratch using nested loops ($O(n^2)$), the algorithm maintains a moving "window" that slides across the sequence, updating the internal state incrementally in $O(n)$ linear time.

1. Real-World Analogy: The Train Window

Imagine you are riding a train through the countryside, looking out through a small rectangular window:

  • As the train moves forward 1 meter, you do not need to rediscover the entire landscape.
  • One tree enters your field of view from the right, and one tree leaves your field of view from the left.
  • The remaining scenery inside the window stays identical! This is the essence of sliding window: Add incoming element on the right, subtract outgoing element on the left.

2. The Two Window Paradigms

Type 1: Fixed-Size Window ($K$)

The size of the window is strictly constant (e.g. "Find maximum sum of any contiguous subarray of length $K$").

  • Advance right pointer until window size equals $K$.
  • At each subsequent step: add arr[right], subtract arr[left], and increment both pointers (left++, right++).

Type 2: Dynamic (Variable-Size) Window

The window size expands and shrinks dynamically to satisfy a constraint (e.g. "Find the longest substring without repeating characters", "Smallest subarray with sum $\ge S$").

  • Expand right pointer to include elements and update state.
  • While the window constraint is violated, shrink the window from the left (left++) until valid again.
  • Record the maximum/minimum window length at valid states.

3. Fixed Window Implementation: Max Subarray Sum of Size $K$

Python 3:

Python
def max_sub_array_sum(nums: list[int], k: int) -> int:
if len(nums) < k:
return 0
# 1. Compute initial sum of first k elements
window_sum = sum(nums[:k])
max_sum = window_sum
# 2. Slide the window from index k to end
for right in range(k, len(nums)):
# Add new right element, subtract old left element (right - k)
window_sum += nums[right] - nums[right - k]
max_sum = max(max_sum, window_sum)
return max_sum

Modern JavaScript / TypeScript:

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

4. Dynamic Window: Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without duplicate characters:

Python 3:

Python
def length_of_longest_substring(s: str) -> int:
char_index_map = {} # Tracks last seen index of each character
max_len = 0
left = 0
for right, char in enumerate(s):
# If character is already in window, jump left pointer past it!
if char in char_index_map and char_index_map[char] >= left:
left = char_index_map[char] + 1
char_index_map[char] = right
max_len = max(max_len, right - left + 1)
return max_len

5. Trace Table: s = "abcabcbb"

rightcharleftWindow SubstringActionmax_len
0'a'0"a"Map: {a:0}1
1'b'0"ab"Map: {a:0, b:1}2
2'c'0"abc"Map: {a:0, b:1, c:2}3
3'a'1"bca"Duplicate 'a' seen at 0 $\to$ left = 0 + 1 = 13
4'b'2"cab"Duplicate 'b' seen at 1 $\to$ left = 1 + 1 = 23
5'c'3"abc"Duplicate 'c' seen at 2 $\to$ left = 2 + 1 = 33
6'b'5"b"Duplicate 'b' seen at 4 $\to$ left = 4 + 1 = 53
7'b'7"b"Duplicate 'b' seen at 6 $\to$ left = 6 + 1 = 73

Result: Maximum length is 3 ("abc"), achieved in single-pass $O(n)$ time!

Interactive Quiz

Multiple Choice Questions

Question 1
How does a Sliding Window reduce the time complexity of finding the maximum sum subarray of size $K$ from $O(n \times K)$ to $O(n)$?
Question 2
When solving "Longest Substring with At Most K Distinct Characters", when should the left pointer advance?
Question 3
What is the space complexity of the Sliding Window technique when applied to an array of numbers with a fixed size $K$?
Question 4
Which of the following problems is NOT suitable for the Sliding Window pattern?
Question 5
In a dynamic sliding window where both left and right pointers only move forward from 0 to $n$, why is the total time complexity $O(n)$ even if there is a while loop nested inside a for loop?
Next Lesson

Prefix Sums & Difference Arrays for Constant-Time Range Queries

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Two-Pointer Technique: Opposite-Direction & Fast-Slow PatternsPrefix Sums & Difference Arrays for Constant-Time Range Queries

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext