DSA Fundamentals
Arrays and Hashing
Stacks and Queues
Trees and Graphs
Dynamic Programming
Advanced Data Structures
Variable-Size Sliding Window
Fixed-size sliding windows work when you know the window length upfront - "find the maximum sum of any 3 consecutive elements." But many problems ask for the longest or shortest subarray that satisfies a condition, and the window size is not known in advance. Variable-size sliding windows handle exactly this class of problems.
The idea: maintain two pointers, left and right, both starting at index 0. Move right forward to expand the window and include more elements. When the window violates the condition, move left forward to shrink it until validity is restored. At every valid state, check whether the current window is the best answer so far.
Variable-size sliding window
Right expands the window until the condition breaks. Left contracts to restore validity. Both pointers only move forward, giving O(n) total.Why Two Pointers Beat Brute Force
The brute-force approach checks every possible subarray: for each starting index i, try every ending index j >= i and verify the condition. That produces O(n^2) subarrays, each potentially costing O(n) to verify - O(n^3) in the worst case. Even optimized brute force is O(n^2).
The sliding window avoids this redundancy through a key insight: if the window [left, right] already violates the condition, then every window starting at left with an endpoint beyond right also violates it (assuming a monotonic condition). Instead of trying those windows, you advance left to restore validity. This pruning collapses two nested loops into a single linear scan.
The O(n) Guarantee
The nested loop structure - an outer loop advancing right and an inner loop advancing left - looks like O(n^2). It is not. The reason is that both pointers only move forward, never backward. The right pointer moves from 0 to n-1, visiting each index exactly once. The left pointer also moves from 0 to at most n-1 across the entire execution, visiting each index at most once. Total pointer movements: at most 2n, which is O(n).
Amortized O(n): both pointers traverse at most n
Left and right each move forward only, never backward. Total moves across both pointers is at most 2n, so the algorithm is O(n) despite nested loops.Every element enters the window exactly once (when right passes it) and leaves the window at most once (when left passes it). Two passes over n elements is linear. The inner while loop may run many iterations for one outer iteration, but it borrows those iterations from future iterations where it runs zero times.
The sliding window is O(n) because of amortized analysis, not because each inner loop iteration is cheap. Both pointers only move forward, so the total work across all iterations is bounded by 2n - regardless of how individual iterations distribute that work. This is the same reasoning behind two-pointer techniques on sorted arrays.
When Variable Windows Apply
Variable-size sliding windows require two properties:
Monotonic condition - expanding the window can only make the condition harder to satisfy or keep it the same, never easier. Adding characters can only increase the distinct count, never decrease it. Adding positive integers can only increase a sum, never decrease it. This guarantees that once the condition is violated, further expansion cannot fix it - only shrinking from the left can.
Contiguous structure - the answer must be a contiguous subarray or substring. If the problem allows picking non-adjacent elements (a subsequence), sliding windows do not apply. You would need dynamic programming or a greedy approach instead.
Common patterns include: longest substring with at most K distinct characters, shortest subarray with sum at least K, longest substring without repeating characters, and minimum window containing all required characters.