Why We Need Two Pointers & How to Think About It
In many array and string problems, a naive search requires checking all pairs of elements. This results in nested loops and an $O(n^2)$ time complexity. The Two Pointers pattern optimizes this to $O(n)$ by maintaining two independent indices (pointers) that traverse the data structure. Because we can prove that moving a pointer discards a set of invalid possibilities without checking them, we never need to re-scan.
Complexity Summary
| Variant | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Opposite Ends | O(n) | O(1) | Converging inward on sorted arrays (e.g., pairs, palindromes) |
| Fast & Slow | O(n) | O(1) | Runners at different speeds on lists/arrays (e.g., cycles, middle) |
| Partition | O(n) | O(1) | In-place filtering and filtering/shifting (e.g., Dutch Flag, Quickselect) |
Three Core Variants
1. Opposite Ends (Converging Pointers)
- How it works: Start one pointer at index
0and another atn - 1. Move them toward each other based on a condition until they meet. - Why it works: If the array is sorted, a comparison of the values at the two pointers tells us if we need to make our sum larger (move left pointer up) or smaller (move right pointer down). We safely discard the other options.
- When to use: Pair sum in sorted array, palindrome verification, container with most water.
- LeetCode Link: LeetCode 167: Two Sum II - Input Array Is Sorted
- LeetCode Link: LeetCode 11: Container With Most Water
2. Fast & Slow (Runner Technique)
- How it works: Two pointers start at the same position but move at different speeds (usually
slowmoves 1 step,fastmoves 2 steps). - Why it works: If there is a cycle (e.g. in a linked list), the fast pointer will eventually lap the slow pointer and they will meet. If there is no cycle, the fast pointer will hit the end of the list.
- When to use: Cycle detection, finding the middle node of a list, finding the k-th node from the end.
- LeetCode Link: LeetCode 141: Linked List Cycle
- LeetCode Link: LeetCode 876: Middle of the Linked List
3. Partition / Same-Direction (Reader/Writer)
- How it works: Both pointers start at the beginning and move in the same direction. A
readpointer scans elements, and awritepointer tracks where the next valid element should go. - When to use: In-place filtering, removing duplicates, partitioning arrays (like Dutch National Flag or Quicksort partition).
- LeetCode Link: LeetCode 27: Remove Element
- LeetCode Link: LeetCode 283: Move Zeroes
# Opposite ends: does a SORTED array contain two numbers summing to target?
# Python
def two_sum_sorted(a, target):
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target: return (lo, hi)
if s < target: lo += 1 # need bigger → move left pointer up
else: hi -= 1 # need smaller → move right pointer down
return None
// Java
public int[] twoSumSorted(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) {
return new int[] { lo, hi };
}
if (s < target) {
lo++; // need bigger sum -> move left pointer up
} else {
hi--; // need smaller sum -> move right pointer down
}
}
return new int[] {};
}
// C++
#include <vector>
std::pair<int, int> twoSumSorted(const std::vector<int>& a, int target) {
int lo = 0, hi = a.size() - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) {
return { lo, hi };
}
if (s < target) {
lo++; // need bigger sum
} else {
hi--; // need smaller sum
}
}
return { -1, -1 };
}
Why it's O(n): each pointer only moves one direction, so together they take ≤ n steps. The "sorted" precondition is what lets a single comparison decide which pointer to advance.
Watch it run
Converging pointers on a sorted array: every comparison moves exactly one pointer inward, so the whole scan is a single pass. Try a target with no valid pair and watch the pointers meet empty-handed.
1/6Sorted array. Does any pair sum to 34? Start with the widest pair.
Fast & slow — cycle detection (Floyd's)
# Python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # +1
fast = fast.next.next # +2
if slow is fast: return True # they meet ⇒ cycle
return False
// Java
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // +1
fast = fast.next.next; // +2
if (slow == fast) return true; // they meet
}
return false;
}
// C++
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // +1
fast = fast->next->next; // +2
if (slow == fast) return true;
}
return false;
}
A hash set also finds a pair-sum in O(n) time but O(n) space. Two pointers is O(1) space if the array is already sorted. If it isn't, sorting first is O(n log n) — then a hash-set pass at O(n) may win. State the trade-off out loud.
Think it through
The whole pattern lives or dies on one question: why is it safe to throw away a pointer's current position? Reason through the cleanest example of that argument before revealing anything.
PROBLEMHeights = [1,8,6,2,5,4,8,3,7]. Each value is a vertical wall. Pick two walls; the water they hold is min(left, right) × distance between them. Return the maximum. (Answer: 49, between the 8 at index 1 and the 7 at index 8.)
- 1
Restate & edges
“What exactly am I maximizing, and what bounds the area of any pair?”
- 2
Brute force first
“Dumbest correct answer and its cost?”
unlocks after the stage above - 3
The key move
“Start at both ends (widest base). The shorter wall limits the area — so which pointer is safe to move inward?”
unlocks after the stage above - 4
Code the template
“Converge from both ends; advance the shorter side. What about a tie?”
unlocks after the stage above - 5
Cost & edge check
“Cost, and what makes the discard argument airtight?”
unlocks after the stage above
// Java — Container With Most Water
public int maxArea(int[] h) {
int lo = 0, hi = h.length - 1;
int best = 0;
while (lo < hi) {
int area = Math.min(h[lo], h[hi]) * (hi - lo);
best = Math.max(best, area);
if (h[lo] < h[hi]) {
lo++; // move shorter wall
} else {
hi--;
}
}
return best;
}
// C++ — Container With Most Water
#include <vector>
#include <algorithm>
int maxArea(const std::vector<int>& h) {
int lo = 0, hi = h.size() - 1;
int best = 0;
while (lo < hi) {
int area = std::min(h[lo], h[hi]) * (hi - lo);
best = std::max(best, area);
if (h[lo] < h[hi]) {
lo++; // move shorter wall
} else {
hi--;
}
}
return best;
}
Check yourself
1. Container With Most Water: the two walls are equal height. Which pointer should you move?
2. Why is the opposite-ends two-pointer scan O(n) rather than O(n²)?
3. Two-sum on an UNSORTED array, and you want O(1) extra space. Can opposite-ends two pointers do it directly?
4. Floyd's fast/slow pointers return True on a linked list. What does that mean, and what did it cost?
Practice — climb the ladder
Two pointers earns its keep on SORTED data or paired ends: each step discards possibilities provably, which is where the O(n) comes from.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up
ends moving inward, slow/fast moving forward- Valid PalindromeEasy
Ends-inward with skip rules — the cleanest convergent-pointer drill.
- Reverse StringEasy
Swap-and-converge — in-place mutation with two indices.
- Move ZeroesEasy
Reader/writer pointers — stable partition in one pass.
Core
the discard argument, made explicitMove the SHORTER wall — articulate why that discard is safe; that argument IS the pattern.
- 3SumMedium
Sort + fix one + two-pointer the rest, with dedup discipline — the interview staple.
Writer pointer with a look-back condition — in-place with a twist.
Stretch
maximum discard sophistication- 4SumMedium
The 3Sum skeleton generalized — nested fixing without drowning in dedup.
Two pointers with running maxes from both ends — the famous finale.