Sliding Window & Two Pointers
The problem
Many array and string problems ask about contiguous subranges (the longest substring without repeats, the smallest subarray summing to at least X), and re-scanning the whole range from scratch for every possible starting point is far more work than the problem actually requires.
Why now
Complexity analysis already established that a nested-loop approach to a range problem is O(n²); sliding window and two pointers are the concrete techniques that turn a large class of those O(n²) range problems into O(n) by exploiting arrays-and-lists' sequential structure — moving a boundary forward only when needed, and never re-examining an element the window has already passed.
Mental model
A sliding window keeps two pointers marking the current subrange's start and end, expanding the end to include more elements and contracting the start to drop ones no longer needed — each element is added to the window once and removed at most once, which is exactly why the total work stays O(n) instead of O(n²). Two-pointer techniques generalize this to any problem where moving one or two markers toward each other (or apart) monotonically narrows the search, without ever needing to look backward.
Requires
- Arrays & ListsProgramming Fundamentals
Sliding window and two pointers operate entirely on the sequential, indexed structure arrays-and-lists already established; the technique is meaningless without a sequence whose elements have a clear left-to-right order to slide across.
- Complexity Analysis in PracticeComputer Science Fundamentals
The entire motivation for this technique is turning an O(n²) nested-loop solution into O(n); you need to already recognize that cost difference for the pattern's value to register as more than a coding trick.
Used in
- The 'longest substring without repeating characters' and similar classic interview problems
- Network buffer and streaming data processing, examining a bounded recent window of data
- Two-sum-style problems on sorted arrays using pointers from both ends
- Rate limiting implementations that track events within a recent time window
Projects
- Solve 'longest substring without repeating characters' using a sliding window, tracing by hand exactly when the window's start pointer advances
- Solve 'find two numbers in a sorted array that sum to a target' using two pointers starting from both ends, and explain why the approach is correct without checking every pair
Examples
- Finding the smallest subarray with sum ≥ target expands the window's end until the sum is enough, then contracts the start as far as possible while still satisfying it — never re-examining a passed element
- A rate limiter allowing 100 requests per rolling 60-second window is a live sliding-window problem, continuously dropping timestamps older than 60 seconds from the front
Resources
Mastery checklist
- I can implement a variable-size sliding window solution and explain why it's O(n)
- I can implement a two-pointer solution for a sorted-array problem
- I can identify when a nested-loop range problem can be reduced to a single-pass sliding window
- I can explain why each element is processed a bounded number of times in a correct sliding window solution