Two Pointers and Sliding Window
Exploit one-way pointer movement to turn many quadratic scans into linear passes over arrays and strings.
Two Pointers and Sliding Window
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Two pointers is one of the simplest ways to save a factor of \(n\). The pattern is to maintain a window or a pair of positions and move each pointer only forward. If the state can be updated incrementally, the whole scan becomes linear.
When to Use It
Reach for this pattern when:
the answer depends on a contiguous subarray or substring,
the left and right boundaries only need to move forward,
adding one element and removing one element can be maintained cheaply,
a brute-force nested loop would revisit almost the same interval many times.
Classic tasks include longest valid subarray, shortest valid window, counting windows with some bound, or merging two sorted lists.
Core Idea
Maintain a current window \([l, r]\) and an invariant that describes when the window is valid. Expand \(r\) to add new information; shrink \(l\) only when the invariant is violated or when you want to make the window minimal.
Because each pointer moves at most \(n\) times, the total number of operations is linear apart from the work needed to maintain the window state.
Key Insight
The technique works only when the window reacts monotonically enough to one-way movement.
For nonnegative arrays, if a sum is too large, moving the left pointer right can only decrease it. That makes the state manageable. If negative numbers are allowed, the same trick often breaks and you need prefix sums or a different data structure.
Operations / Main Technique
Fixed-state sliding window.
Add \(\texttt{a[r]}\), update counts or sums, then shrink while invalid.
Two sorted arrays.
Use two indices to merge, count inversions in specialized settings, or match greedily.
Worked example.
For the longest subarray with sum at most \(S\) and nonnegative values, expand the right end until the sum becomes too large, then move the left end until the window is valid again. Every index enters once and leaves once.
Correctness Intuition
At every step, the maintained invariant tells me what the current window means: valid, minimal valid, or maximal valid ending at \(r\). Since the pointers never move backward, the algorithm never repeats a discarded state.
The one-way movement is the whole proof skeleton: each decision throws away configurations that will never become useful again.
Complexity Analysis
If both pointers only move forward, the total number of pointer updates is \(O(n)\). With \(O(1)\) amortized window maintenance, the entire method is \(O(n)\).
Implementation
The code includes:
a longest-window routine for nonnegative sums,
a counter for subarrays with at most \(k\) distinct values.
Those two patterns cover a large fraction of contest sliding-window problems.
Common Pitfalls
Applying the nonnegative-sum template when negative values are present.
Forgetting whether the window is inclusive or half-open.
Not updating the answer in the right place: before shrinking, after shrinking, or both.
Letting the frequency map keep zero-count keys and then miscounting distinct values.
Variants / Extensions
Count exactly \(k\) distinct by \(\texttt{at\_most(k) - at\_most(k - 1)}\).
Monotone deque when the window also needs min or max queries.
Two pointers on sorted arrays for pair sum, interval stabbing, or greedy matching.
Meet-in-the-middle or prefix tricks when the window state is not one-way monotone.
Practice Problems
Longest substring without repeated characters.
Number of subarrays with at most \(k\) distinct values.
Shortest subarray with sum at least \(S\) in the nonnegative setting.
Merge-like matching between two sorted sequences.
References
Code
Contest-ready reference implementation for the idea explained above.
int longest_window_sum_at_most(const vector<int>& a, long long limit) {
long long sum = 0;
int best = 0;
for (int l = 0, r = 0; r < (int)a.size(); ++r) {
sum += a[r];
while (sum > limit) {
sum -= a[l++];
}
best = max(best, r - l + 1);
}
return best;
}
long long count_subarrays_at_most_k_distinct(const vector<int>& a, int k) {
unordered_map<int, int> freq;
long long answer = 0;
for (int l = 0, r = 0; r < (int)a.size(); ++r) {
++freq[a[r]];
while ((int)freq.size() > k) {
if (--freq[a[l]] == 0) {
freq.erase(a[l]);
}
++l;
}
answer += r - l + 1;
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.