Sliding window (Fixed length)

Sliding Window (Fixed) — Complete Topic Explanation

The Sliding Window (Fixed) pattern is an algorithmic technique used to efficiently process all contiguous subarrays or substrings of a fixed size k.

It avoids repeated computation by reusing results from overlapping windows.

---

Core Idea

You are given:

• A sequence (array or string)
• A fixed window size k

Your task:

• Perform a computation (sum, max, min, count, frequency, condition check, etc.)
• For every contiguous block of size k

Instead of recomputing the result for each block independently, you:

• Maintain a window of exactly k elements
• Slide the window one position at a time
• Update the result incrementally

---

Why the Naive Approach Is Inefficient

If:

• Total elements = n
• Window size = k

Then:

• Number of windows = (n - k + 1)
• Work per window = k operations

Total work:
(n - k + 1) * k

Asymptotically:
O((n - k + 1) * k) ≈ O(nk)

This becomes inefficient for large inputs.

---

Sliding Window Optimization Insight

When the window moves forward by one position:

• One element exits the window (left side)
• One element enters the window (right side)
• All other elements remain unchanged

Example:
Before: [a, b, c]
After : [b, c, d]

Instead of recomputing:
b + c + d

We update:
new_value = old_value - a + d

This update takes constant time.

---

Algorithm Flow

1. Initialize variables to track the window state
2. Traverse the sequence from left to right
3. Add the current element to the window
4. Once the window size reaches k:
   • Process or record the window result
   • Remove the leftmost element
5. Continue until the end of the sequence

---

Key Characteristics

• Window size is fixed
• Elements are contiguous
• Window slides one step at a time
• Computation is incrementally updated
• Eliminates nested loops

---

Time and Space Complexity

Metric	Complexity
Time	O(n)
Space	O(1)

---

When to Use Fixed Sliding Window

This pattern is applicable when:

• The problem mentions subarrays or substrings
• Elements must be contiguous
• A fixed window size k is given
• The same computation repeats over each window

---

Common Problem Types

• Maximum / minimum sum subarray of size k
• Average of all subarrays of size k
• Count of vowels or characters in substrings of size k
• Count of distinct elements in each window
• First element satisfying a condition in every window

---

Mental Model

Imagine a transparent window of width k sliding across the data:

• You only see k elements at a time
• Each move removes one element and adds one new element
• The result is updated instantly without recomputation

---

Summary

• Fixed Sliding Window is used for contiguous, fixed-size problems
• It reduces time complexity from O(nk) to O(n)
• It is simple, efficient, and widely applicable
• Mastering it unlocks many array and string interview problems