Two pointers and sliding window are the patterns that turn many O(n^2) brute-force solutions on arrays and strings into a single O(n) pass. They are among the most frequently asked techniques in coding interviews, and once you can recognise them, dozens of "medium" problems become routine.
This is Part 4 of the Learn DSA series. We cover how to spot these patterns, the three pointer layouts, a reusable template for variable-size windows, and the cases where the technique does not work. Code is in C++ and Java.
1. How to recognise the pattern
Reach for two pointers or a sliding window when you see clues like these:
- The array is sorted (or can be sorted) and you need a pair or triplet with some sum.
- You must work in place with O(1) extra space: remove duplicates, move zeroes, partition by value.
- The question is about a contiguous subarray or substring: "longest", "shortest" or "count" with a condition such as at most k distinct characters or sum at least target.
- You need to compare from both ends, as in palindromes or reversing.
The common idea is that each pointer only ever moves forward (or only inward), so together they make at most about 2n moves: O(n) total, even though there are two of them.
2. Pattern 1: pointers moving towards each other
Start one pointer at each end and move them inward. On a sorted array this finds a pair with a given sum: if the sum is too small, move the left pointer right to increase it; if too large, move the right pointer left.
// Sorted array: return 0-based indices of two values summing to target
pair<int,int> pairSum(const vector<int>& a, int target) {
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return {l, r};
if (s < target) l++; // need a bigger sum
else r--; // need a smaller sum
}
return {-1, -1};
}// Sorted array: return 0-based indices of two values summing to target
static int[] pairSum(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return new int[]{l, r};
if (s < target) l++; // need a bigger sum
else r--; // need a smaller sum
}
return new int[]{-1, -1};
}The same layout checks palindromes, reverses arrays, and solves Container With Most Water (always move the shorter wall, because moving the taller one can never help). 3Sum is "sort, then fix one element and run this two-pointer search on the rest", giving O(n^2) instead of O(n^3).
3. Pattern 2: slow and fast pointers in the same direction
A fast pointer scans every element while a slow pointer marks where the next element to keep should be written. This rewrites the array in place with O(1) extra space.
// Remove duplicates from a sorted array in place; return new length
int removeDuplicates(vector<int>& a) {
if (a.empty()) return 0;
int slow = 1; // next write position
for (int fast = 1; fast < (int)a.size(); fast++)
if (a[fast] != a[slow - 1]) a[slow++] = a[fast];
return slow;
}// Remove duplicates from a sorted array in place; return new length
static int removeDuplicates(int[] a) {
if (a.length == 0) return 0;
int slow = 1; // next write position
for (int fast = 1; fast < a.length; fast++)
if (a[fast] != a[slow - 1]) a[slow++] = a[fast];
return slow;
}Move Zeroes, Remove Element and partitioning work the same way. The Dutch National Flag problem (sort 0s, 1s and 2s in one pass) uses three pointers: low, mid and high. On linked lists, slow and fast pointers find the middle node and detect cycles (Part 5).
4. Pattern 3: fixed-size sliding window
When the window length k is fixed, such as "maximum sum of any k consecutive elements", do not recompute each window from scratch. Slide it: add the element entering on the right and subtract the one leaving on the left. Each slide is O(1), so the whole scan is O(n) instead of O(n x k).
For "maximum in every window of size k", keep a monotonic deque of indices whose values are decreasing; the front is always the current maximum. That is the Sliding Window Maximum problem, and it is covered with stacks and queues in Part 6.
5. Pattern 4: variable-size sliding window template
Most window problems use the same template: expand the right edge one step at a time, and while the window breaks the rule, shrink it from the left. After the shrinking, the window is valid, so update the answer.
// Longest substring without repeating characters. O(n) time
int lengthOfLongestSubstring(const string& s) {
vector<int> count(256, 0);
int best = 0;
for (int l = 0, r = 0; r < (int)s.size(); r++) {
count[(unsigned char)s[r]]++; // expand
while (count[(unsigned char)s[r]] > 1) // rule broken
count[(unsigned char)s[l++]]--; // shrink
best = max(best, r - l + 1); // window is valid
}
return best;
}// Longest substring without repeating characters. O(n) time
static int lengthOfLongestSubstring(String s) {
int[] count = new int[256];
int best = 0;
for (int l = 0, r = 0; r < s.length(); r++) {
count[s.charAt(r)]++; // expand
while (count[s.charAt(r)] > 1) // rule broken
count[s.charAt(l++)]--; // shrink
best = Math.max(best, r - l + 1); // window is valid
}
return best;
}Change only the rule and the answer update and the template solves many problems: longest substring with at most k distinct characters, minimum size subarray with sum at least target (shrink while the sum is still at least target and record the minimum), longest repeating character replacement, and permutation-in-string checks with a count array.
6. When sliding window does not work
- Negative numbers in sum problems. The window relies on "adding an element moves the sum one way". With negatives that is no longer true, so shrinking can skip valid answers. Use prefix sums with a hash map instead (Part 3).
- Non-contiguous selections (subsequences or arbitrary subsets) are not windows; they usually need dynamic programming (Part 13).
- Unsorted pair search: the opposite-ends trick needs sorted data. Either sort first (O(n log n)) or use a hash set for O(n).
- Two pointers and sliding windows replace nested loops with one O(n) pass because each pointer only moves forward or inward.
- Opposite-end pointers need sorted data and solve pair sums, palindromes and container problems.
- Slow/fast pointers rewrite arrays in place with O(1) extra space.
- Variable windows follow one template: expand right, shrink left while invalid, then update the answer.
- With negative numbers or non-contiguous selections, switch to prefix sums + hashing or dynamic programming.
Practice problems
These are classic LeetCode-style problems, listed roughly from easy to hard. Try to name the pattern before you start coding each one.
- Valid Palindrome (easy)
- Two Sum II - Input Array Is Sorted (medium)
- Move Zeroes (easy)
- Remove Duplicates from Sorted Array (easy)
- Maximum Average Subarray I (easy, fixed window)
- Container With Most Water (medium)
- 3Sum (medium)
- Sort Colors (medium, Dutch National Flag)
- Longest Substring Without Repeating Characters (medium)
- Minimum Size Subarray Sum (medium)
- Longest Repeating Character Replacement (medium)
- Permutation in String (medium)
- Minimum Window Substring (hard)
- Sliding Window Maximum (hard, monotonic deque)
Interview questions and FAQ
Why is the two-pointer technique O(n) when there are two loops?
Neither pointer ever moves backwards. Across the whole run, the left pointer moves at most n times and the right pointer at most n times, so the total work is O(2n) = O(n), even if the code has a while loop inside a for loop.
What is the difference between two pointers and sliding window?
A sliding window is a special case of two pointers where the elements between the pointers form the window you care about. General two-pointer problems, like pair sum on a sorted array, only look at the two pointed-to elements.
How do I know when to shrink the window?
Define the rule the window must satisfy (for example "no character repeats" or "sum is less than target"). Shrink from the left while the rule is broken; as soon as it holds again, the window is valid and you can update the answer.
Why does the sliding window fail with negative numbers?
The method assumes that growing the window always moves the sum in one direction and shrinking moves it back. Negative values break that, so you cannot safely discard left elements. Prefix sums with a hash map handle these cases in O(n).
What is the time complexity of 3Sum?
Sorting is O(n log n), and for each of the n fixed elements the two-pointer scan is O(n), so the total is O(n^2), which is the best known approach for the general problem.
Comments
Post a Comment