Algorithms
Sliding Window
Цели урока
- Understand the sliding window idea
- Solve fixed window size problems
- Apply variable window for optimization
- Combine sliding window with HashMap
- Solve string problems: anagrams, unique characters
Предварительные знания
- Two Pointers
- Hash Tables
Sliding Window is one of the most frequent interview patterns. LeetCode #3 (Longest Substring) is in the top 5 by popularity. By mastering this technique, you'll solve dozens of problems.
- Network protocols - TCP sliding window
- Data streaming - sliding aggregates
- Finance - moving average
- Monitoring - rate limiting
A name borrowed from network protocols
The sliding window pattern in algorithms is folklore, with no single inventor, but the name has a clear origin in networking. In the 1970s, as Vint Cerf and Robert Kahn designed TCP, they needed flow control so a fast sender would not overwhelm a slow receiver. The solution, formalized in RFC 793 in 1981, was the sliding window protocol: the receiver advertises how many bytes it can accept, and the sender keeps a window of unacknowledged bytes that slides forward as acknowledgements arrive. Algorithm courses borrowed the image directly. A contiguous range over an array or string is treated as a window whose two edges advance, so each element enters and leaves at most once and a naive O(n times k) scan becomes O(n). The networking metaphor stuck because it captures the idea exactly: a fixed or growing frame moving over a stream.
Sliding Window Idea
**Sliding Window** is a technique for subarray and substring problems. Instead of recomputing from scratch - only update the edges of the window.
**Two types of windows:** fixed size k and variable size (expands/shrinks).
Why is sliding window more efficient than the naive approach?
Fixed Size Window
**Problem: maximum sum subarray of length k**
**Moving average:**
arr = [2, 1, 5, 1, 3, 2], k = 3. Maximum sum subarray of length 3?
Variable Size Window
**Window size changes dynamically.** Expand while condition holds, shrink when it's violated.
**Maximum subarray with sum ≤ k:**
**Important:** variable window works when adding elements monotonically affects the condition (sum grows). For negative numbers - different approaches are needed.
When do we shrink a variable window?
String Problems
**Sliding window is perfect for substring problems!**
**Longest Substring Without Repeating Characters:**
s = "abcabcbb". Length of the longest substring without repeating characters?
Sliding Window + HashMap
**Combining sliding window with a hash table is a reliable pattern.**
**Minimum Window Substring - hard classic:**
**Pattern:** HashMap stores the window state, allowing O(1) condition checks.
Why is a HashMap needed in sliding window problems?
Sliding Window
- Fixed window: sum/average of subarray of length k
- Variable window: expand and shrink by condition
- Strings: substrings with character constraints
- HashMap stores window state
- O(n) instead of O(n×k) or O(n²)
Related Topics
Sliding Window is an extension of the two pointers idea.
- Two Pointers — Basic technique
- Hash Tables — Storing window state
- Monotonic Queue — Optimization for min/max in window
Связанные уроки
- alg-26-two-pointers — A window is two same-direction pointers
- ds-06-hash-intro — Variable windows track contents with a hash map
- ds-25-monotonic-stack — Monotonic queues give O(1) window maximum
- alg-36-prefix-sum — Both turn repeated range work into O(1) per step
- stat-13-time-series