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.
Understanding Two Pointers & Sliding Window Patterns
The most important habit is to state what the current range represents. This is called an invariant. For example, a window might always contain no repeated letters, or its total might always stay at or below a limit.
Every line that moves a pointer must preserve that rule or deliberately repair it. When the right boundary moves, new data enters the range. Update the sum, count, or frequency before checking the rule.
When the left boundary moves, remove the outgoing data before advancing it. This order prevents a common error where a program counts an item that has already left the window.
Variable windows depend on a useful property of the condition. With nonnegative numbers, adding another value cannot make a total smaller. If a total becomes too large, moving the left boundary is a sensible repair because it removes value from the total.
This logic can fail when negative numbers are allowed. Adding a negative value may repair an oversized total without shrinking anything.
In those cases, a basic sliding window may miss valid ranges, and students may need prefix sums or another method. Before choosing a pattern, check whether the condition changes predictably as the window grows or shrinks.
Opposite-end pointers rely on ordering. In a sorted list, changing the left value raises the pair total, while changing the right value lowers it. That gives each move a reason.
Without sorted data, the same moves provide no reliable information. Sorting can be worthwhile, though it changes the original order and usually takes more time than one scan. If a task needs original positions, store each value with its index before sorting.
A different approach, such as a hash map, may fit better when order must remain unchanged. Good problem solving means knowing the assumptions behind a shortcut.
Frequency maps are useful because many string tasks are really counting tasks. A map records how many times each character occurs in the current range. Keep a separate count of distinct characters or duplicates when possible.
Rechecking every map entry after each move can quietly make a solution slow. For a longest substring with no repeats, increase a character count when it enters. If that count exceeds one, shrink from the left until the duplicate is removed.
Record the best length only when the window is valid. This same idea appears in text filters, DNA sequence analysis, log monitoring, and searching a stream of sensor readings for a short unusual period.
Students should trace pointer code on paper before trusting it. Use a tiny example with repeated values, a window of size one, an empty input, and a range that becomes invalid several times. Watch for off by one errors at both ends of the range.
Decide whether the answer is updated before shrinking, after shrinking, or at every valid step. That choice changes the result for maximum length, minimum length, and number of valid ranges. A loop can still be linear even when it contains another loop, provided each boundary only travels forward through the data once.