Two Pointers Technique
The Two Pointers technique uses two indices moving monotonically across a sorted array or sequence to solve pair-sum, partitioning, deduplication, and container problems in O(n) time and O(1) space.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Two Pointers Technique
The Two Pointers technique replaces nested $O(n^2)$ loops with two indices (left and right, or slow and fast) that move monotonically across an array or linked list. Because each pointer advances at most $n$ times, the total work drops to $O(n)$ time and $O(1)$ auxiliary space!
At a Glance
| Pattern | Pointer Movement | Classic Uses |
| :--- | :--- | :--- |
| Opposite Ends | l = 0, r = n - 1 moving inward | Two Sum (sorted), Container With Most Water, Trapping Rain Water, Palindrome check |
| Fast / Slow (Same Direction) | slow writes/lags, fast scans ahead | In-place deduplication, moving zeros, linked-list cycle detection (Floyd) |
| Two Arrays | i in A, j in B | Merging sorted arrays, intersection of sorted arrays |
---
How It Works (Opposite-Ends Pattern)
On a sorted array, suppose we want a pair (l, r) with A[l] + A[r] == target:
1. Start at l = 0, r = n - 1.
2. While l < r:
- If
A[l] + A[r] == target, return{l, r}. - If
A[l] + A[r] < target, we need a larger sum →++l. - Else we need a smaller sum →
--r.
Step-by-Step Trace (A = [1, 2, 4, 7, 11, 15], target = 15)
l=0 (1), r=5 (15)→16 > 15→--rl=0 (1), r=4 (11)→12 < 15→++ll=1 (2), r=4 (11)→13 < 15→++ll=2 (4), r=4 (11)→15 == 15→ return(2, 4)!
---
Complexity & Key Insights
- Why It's $O(n)$: Every iteration either increments
lor decrementsr, so the distancer - lstrictly decreases by 1 per step—at most $n - 1$ iterations total. - When Two Pointers Applies: You need a monotonicity invariant—discarding an index (
++lor--r) must be mathematically guaranteed never to discard the optimal answer.
---
Practice Problems
Easy
1. Two Sum II — Sorted Array (LeetCode 167)
Find 0-based indices (i, j) in a sorted array summing to target.
Approach: Opposite-end pointers l = 0, r = n - 1. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
std::pair<int, int> twoSumSorted(const std::vector<int>& a, int target) {
int l = 0, r = static_cast<int>(a.size()) - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return {l, r};
if (s < target) ++l;
else --r;
}
return {-1, -1};
}
int main() {
auto [i, j] = twoSumSorted({1, 2, 4, 7, 11, 15}, 15);
std::cout << i << " " << j << "\n"; // 2 4
return 0;
}
</details>
2. Remove Duplicates from Sorted Array In-Place (LeetCode 26)
Remove duplicates in-place and return the new length k.
Approach: Fast/slow pointers: slow marks the last unique written slot; whenever nums[fast] != nums[slow], advance slow and copy nums[fast]. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
int removeDuplicates(std::vector<int>& nums) {
if (nums.empty()) return 0;
int slow = 0;
for (int fast = 1; fast < static_cast<int>(nums.size()); ++fast) {
if (nums[fast] != nums[slow]) nums[++slow] = nums[fast];
}
return slow + 1;
}
int main() {
std::vector<int> a = {1, 1, 2, 2, 3, 4, 4};
int k = removeDuplicates(a);
for (int i = 0; i < k; ++i) std::cout << a[i] << " ";
std::cout << "\n";
return 0;
}
</details>
---
Intermediate
3. Container With Most Water (LeetCode 11)
Given vertical line heights h[0..n-1], find two lines forming a container holding the maximum water min(h[l], h[r]) * (r - l).
Approach: Start at l = 0, r = n - 1. Always move the shorter wall inward—moving the taller wall can only decrease width without ever increasing the limiting height! Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int maxArea(const std::vector<int>& h) {
int l = 0, r = static_cast<int>(h.size()) - 1, best = 0;
while (l < r) {
best = std::max(best, std::min(h[l], h[r]) * (r - l));
if (h[l] < h[r]) ++l;
else --r;
}
return best;
}
int main() {
std::cout << maxArea({1, 8, 6, 2, 5, 4, 8, 3, 7}) << "\n"; // 49
return 0;
}
</details>
4. 3Sum (Unique Triplets Summing to Zero, LeetCode 15)
Find all unique triplets (a, b, c) in nums that sum to 0.
Approach: Sort nums, fix i (skipping duplicates), and run opposite-end Two Pointers on [i + 1, n - 1] for -nums[i] (skipping duplicate l and r). Time: $O(n^2)$. Space: $O(1)$ extra.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
std::vector<std::vector<int>> threeSum(std::vector<int> nums) {
std::sort(nums.begin(), nums.end());
int n = static_cast<int>(nums.size());
std::vector<std::vector<int>> res;
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = n - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
res.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1]) ++l;
while (l < r && nums[r] == nums[r - 1]) --r;
++l; --r;
} else if (s < 0) ++l;
else --r;
}
}
return res;
}
int main() {
auto trips = threeSum({-1, 0, 1, 2, -1, -4});
std::cout << "Triplets: " << trips.size() << "\n"; // 2
return 0;
}
</details>
---
Hard
5. Trapping Rain Water in $O(1)$ Space (LeetCode 42)
Given an elevation map height[], compute how much water it traps after raining in $O(n)$ time and $O(1)$ space.
Approach: Maintain l, r and running leftMax, rightMax. Whichever side has the smaller max (leftMax <= rightMax) determines the exact water level at that pointer (leftMax - height[l]), so advance that side! Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int trapWater(const std::vector<int>& h) {
int l = 0, r = static_cast<int>(h.size()) - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (l < r) {
if (h[l] <= h[r]) {
leftMax = std::max(leftMax, h[l]);
water += leftMax - h[l++];
} else {
rightMax = std::max(rightMax, h[r]);
water += rightMax - h[r--];
}
}
return water;
}
int main() {
std::cout << trapWater({0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}) << "\n"; // 6
return 0;
}
</details>
---
Related Algorithms
- Sliding Window — contiguous subarray variant of Two Pointers.
- Binary Search — $O(\log n)$ sorted-array search.