Sliding Window
sliding-window
Algorithms
Sliding Window (Intro)
To find the longest substring of `s` with no repeated characters, the brute-force approach checks every substring in `O(n^3)` time. The sliding-window solution touches each character at most twice and runs in `O(n)`: extend a right pointer until a duplicate appears, then advance a left pointer until the duplicate is gone, repeating until the right pointer falls off the end. **Sliding Window (Intro)** turns that idea into two reusable templates. The fixed-size window slides a range of length `k` across the array and updates the running sum or count by adding the new right element and removing the old left element, never recomputing from scratch. The variable-size window expands the right edge while a condition holds and shrinks the left edge to restore that condition, tracking the window's contents with a hash map or counter. You will apply both to maximum-sum subarray of size `k`, longest substring without repeating characters, minimum window substring, and longest substring with at most `k` distinct characters. In **Two Pointers (Intro)**, you used coordinated indices to walk an array linearly. **Hash Map (Dictionary) Basics** gave you the `O(1)` lookup and update that lets a window track its own contents efficiently. Sliding window combines both: two indices and one hash map. From here you turn to **Recursion Fundamentals**, which trades sequential index movement for self-similar subproblems.
Not Started
0%
Practice Problems
Best Time to Buy and Sell Stock
Find the maximum profit from buying and selling a stock once, given daily prices.
Contains Duplicate II
Check if an array contains two distinct indices with the same value whose absolute difference is at most k.
Maximum Average Subarray I
Find the contiguous subarray of a given length k that has the maximum average value.
Minimum Window Substring
Find the smallest substring of s that contains all characters of t, including duplicates.
Sliding Window Maximum
Find the maximum value in each sliding window of size k as it moves across the array.
Substring with Concatenation of All Words
Find all starting indices where a concatenation of all given words (each of equal length) forms a substring.
Find All Anagrams in a String
Find all start indices where an anagram of pattern p occurs in string s.
Longest Repeating Character Replacement
Find the length of the longest substring containing the same letter after performing at most k character replacements.
Longest Substring Without Repeating Characters
Find the length of the longest substring without repeating characters using the sliding window technique.
Minimum Size Subarray Sum
Find the minimal length subarray whose sum is greater than or equal to the target.
Permutation in String
Given two strings, determine if one string's permutation is a substring of the other.
Code Snippets
Sliding Window Template
Sliding window is the linear-time alternative to nested loops for substring-and-subarray problems. This snippet covers the fixed-size window for max-sum-of-k, the variable-size window for longest-substring-with-condition, and the at-most-K shrinkable form that handles 'at most / exactly K distinct' problems with one trick.
Pairwise Iteration
`itertools.pairwise` (Python 3.10+) yields successive overlapping pairs from any iterable. It replaces the classic `zip(seq, seq[1:])` and the `tee` recipe with a single, lazy, memory-flat call. This entry covers the basic pattern, the manual fallback for older Python, and a tiny example: detecting monotonic runs.
Python Sliding Window Template
The sliding-window pattern walks two indices forward through a sequence, maintaining an aggregate (sum, count, set, dict) of the current window. It turns 'best subarray of length K' and 'longest subarray with property P' problems into single O(n) sweeps. This entry covers the fixed-size variant, the variable-size shrink-when-invalid variant, and the longest-substring-without-repeats classic.
Question Banks
Deque and Sliding Window Max
Five prompts on the monotonic deque pattern: implementing sliding window maximum, the invariant that makes it O(n), and adjacent online-statistics applications.
Sliding Window Essentials
Five mid-level prompts on fixed and variable sliding windows: max sum, longest substring without repeats, and a window-shrink invariant. Mixes implementation and trace.
JavaScript Longest and Shortest Unique Substring: Two Approaches Quiz
Two seeded approaches to find the longest and shortest unique substrings (restart-on-conflict and instrumented restart), plus two companions on a real sliding window and complexity analysis.
Community
Sliding Window Technique
What sliding window actually optimises (state reuse, not just same-direction pointers), the fixed vs variable templates, four canonical problems, and when the technique is the wrong tool.
Subarrays with K Different Integers
Count subarrays containing exactly K distinct integers using the at-most-K window trick.
Subarray Product Less Than K
Count contiguous subarrays whose product is strictly less than k, in linear time using a sliding window.
Rate Limiting: Token Bucket vs Sliding Window
Token bucket is the right default. Sliding window log is correct but expensive. Fixed window is the algorithm I would not ship.
Design Hit Counter
Build a counter that returns the number of hits in the past 5 minutes (300 seconds), with monotonically non-decreasing timestamps.
Max Consecutive Ones III
Find the longest contiguous subarray of 1s achievable when you can flip at most K zeros.
Fruit Into Baskets
Find the longest contiguous subarray that contains at most two distinct values.