Two Pointers and Sliding Window
Use monotone indices and maintained window state to replace many quadratic scans with linear passes.
What you will learn
By the end, you can recognise when two indices can eliminate repeated work, state the invariant that makes pointer movement safe, and distinguish a fixed-size window from a variable-size window. We will build from sorted pair search to a maximum-sum window and then a minimum-length positive-sum window.
1. Two pointers: preserve an invariant
Two pointers are two indices that move through a sequence according to a rule. The useful question is not simply “can I use two indices?” but “what fact lets me discard all candidates between or beyond them?” A sorted array gives that fact: if the smallest remaining value plus the largest is too small, pairing the smallest with anything else cannot reach the target, so the left index can advance.
For values [1, 2, 4, 6, 10] and target 8, the first sum is 11, so discard 10. The next is 7, so discard 1. Then 2 + 6 is 8. Each move rules out at least one endpoint, so the scan is O(n) time and O(1) extra space. The cast widens the addition before it happens, guarding against overflow when two int values are added.
2. Opposite-direction and same-direction pointers
Opposite-direction pointers often start at both ends: palindrome checks, reversing in place, or two-sum on sorted data. Same-direction pointers include slow/fast scans and the left/right boundaries of a window. Pointer names should describe their role, not just their speed: left is the start of the active range and right is the newly included element.
This example compares bytes exactly; it does not ignore spaces, punctuation, or letter case. That is a deliberate contract. “Palindrome” requirements vary, so normalisation (lowercasing, filtering characters, or Unicode handling) must be specified and performed separately when required. For empty input, returning true is consistent with the usual definition that no pair contradicts the palindrome property.
3. Sliding windows: a range with maintained state
A sliding window is a contiguous range [left, right]. Instead of recomputing a property for every range, add the new right element and remove elements from the left as the rule requires. For a fixed window of size k, each shift removes one value and adds one. The total work after initialization is O(n), not O(nk).
The invariant is that immediately before evaluating a candidate, window_sum equals the sum of exactly k elements ending at right. Using long long for the running total avoids assuming that many valid int values still fit in an int sum. For k equal to n, the initialization is the only candidate; for k outside 1…n, the function reports invalid input.
4. Variable windows and the condition that matters
A variable window grows by advancing right and shrinks by advancing left. The common minimum-length-subarray pattern is correct when values are non-negative (strictly positive is a common simpler contract). Adding a new value can only increase the sum, and removing a value can only decrease it. That monotonicity means shrinking after the sum reaches the target cannot hide a shorter valid window.
Both indices only move forward. Although there is a nested while, each element enters once and leaves at most once, so total work is O(n). This API requires a positive target and a non-null output pointer. Negative values break the monotonicity: removing a negative number can increase a sum. For arbitrary signed values, use a different technique such as prefix sums with a monotonic deque; do not apply this window rule blindly.
5. Choose the pattern from the input constraints
| Signal | Technique | Invariant / requirement | Typical cost |
|---|---|---|---|
| Sorted input; pair from both ends | Opposite pointers | Every move rules out candidates using sorted order | O(n), O(1) extra |
| Contiguous range of exactly k | Fixed window | State describes the current k values | O(n), O(1) extra |
| Longest/shortest range with monotone constraint | Variable window | Expanding and shrinking changes validity predictably | Usually O(n), O(1) or O(k) |
| Need all pairs without sorted order | Hashing or sort + pointers | Choose based on output, duplicates, and mutation rules | Often O(n) or O(n log n) |
6. Common mistakes
- Using two pointers on unsorted data: pointer moves may discard valid answers. Sort only if reordering is allowed, or retain original indices; otherwise choose hashing or another method.
- Updating the answer before the window is valid: first establish the invariant and verify the constraints at each point where the result is recorded.
- Applying positive-window logic to negative values: the expand/shrink monotonicity disappears. Use prefix sums or another suitable structure.
- Off-by-one boundaries: decide whether your range is inclusive or half-open. Here it is inclusive, so length is
right - left + 1; empty input needs separate handling.
7. Practice
- Return the pair of indices (not values) for a sorted array. Explain how duplicate values affect whether there may be multiple answers.
- Given a string, determine whether it is a palindrome after ignoring ASCII whitespace and case. Separate normalisation from the two-pointer scan.
- Find the average of every contiguous window of size k in one pass. What is the running sum invariant?
- Find the longest substring with at most two distinct characters. Describe the frequency-map state and when to shrink.
- Test the minimum-length positive-window function with an impossible target, one element, target met exactly, and an invalid negative value.
Review checklist: Can you state why a pointer move is safe? Does every index advance only O(n) times? Are duplicates, empty input, overflow, and negative values covered by the problem contract?
🎯 Key Takeaways
- ✓Two pointers work because an invariant makes discarded candidates impossible.
- ✓A sliding window tracks a contiguous range and updates its state incrementally.
- ✓Fixed-size windows add one item and remove one item per step.
- ✓Variable windows need monotonicity; negative values often invalidate the simple shrink rule.
- ✓Inclusive window length is right − left + 1; boundary contracts must be explicit.
- ✓The Interview Problem-Solving Patterns unit provides separate interview drills for these techniques.
Next
Continue to binary-level operations, or revisit the sequence if you want to strengthen your range-query structures.
HELP US IMPROVE
How was this lesson?
Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
