Two pointers and sliding window patterns help students solve array and string problems efficiently. This cheat sheet covers when to move one pointer, when to move both, and how to track a changing window. These patterns are important because they often reduce slow nested-loop solutions from O(n^2) to O(n).
Students in grades 10-12 can use them for coding interviews, contests, and advanced programming classes.
The two pointers pattern usually uses left and right indexes to scan from opposite ends or move through a sorted structure. A fixed sliding window keeps a constant window size k and updates the answer as the window moves one step at a time. A variable sliding window grows and shrinks based on a condition, such as sum <= target or all characters are unique.
The key idea is to update counts, sums, or other state incrementally instead of recomputing from scratch.
Key Facts
- Two pointers often use left = 0 and right = n - 1, then move pointers based on a comparison or condition.
- A two-sum problem on a sorted array can be solved by checking sum = arr[left] + arr[right], then moving left up if sum < target or right down if sum > target.
- A fixed sliding window of size k starts with the sum of the first k items, then updates with windowSum = windowSum - arr[i - k] + arr[i].
- A variable sliding window usually expands with right = right + 1 and shrinks with left = left + 1 while a condition is broken.
- The length of a current window is windowLength = right - left + 1.
- Most correct two pointers and sliding window solutions run in O(n) time because each pointer moves across the data at most once.
- Sliding windows work best on contiguous subarrays or substrings, not on problems where selected elements can be separated.
- Use a frequency map when the window condition depends on character counts, duplicate values, or the number of distinct items.
Vocabulary
- Pointer
- An index or reference that marks a current position in an array, string, or list.
- Two pointers
- A pattern that uses two indexes moving through data to find pairs, ranges, or matches efficiently.
- Sliding window
- A contiguous section of an array or string that moves while preserving useful information about its contents.
- Fixed window
- A sliding window whose size stays constant, usually written as k.
- Variable window
- A sliding window whose size grows or shrinks until a required condition is satisfied.
- Frequency map
- A table that stores how many times each value or character appears in the current window.
Common Mistakes to Avoid
- Moving the wrong pointer in a sorted two-sum problem is wrong because increasing left raises the sum while decreasing right lowers the sum.
- Recomputing every window from scratch is inefficient because it turns an O(n) fixed window solution into O(nk) or worse.
- Forgetting to remove the outgoing element from the window is wrong because the stored sum or frequency map no longer matches the actual window.
- Using a sliding window on non-contiguous choices is wrong because a window always represents consecutive elements or characters.
- Calculating window length as right - left is wrong for inclusive indexes because the correct length is right - left + 1.
Practice Questions
- 1 Given arr = [1, 3, 4, 6, 8, 10] and target = 10, use two pointers to find one pair that sums to the target.
- 2 Given arr = [2, 1, 5, 1, 3, 2] and k = 3, find the maximum sum of any fixed sliding window of size 3.
- 3 Given s = "abcabcbb", find the length of the longest substring with no repeated characters using a variable sliding window.
- 4 Explain why a fixed sliding window is not the best pattern for finding the longest substring with at most two distinct characters.