Two pointers - DSA Learning Guide

Overview

The two pointers technique walks two indexes through a sequence, moving them according to a rule so that each step rules out candidates. It turns many O(n^2) pair-checking solutions into O(n) scans.

There are two common forms. Opposite-direction pointers start at both ends and move inward, which works on sorted data or symmetric checks such as palindromes. Same-direction pointers (slow and fast) move left to right, where one pointer writes or marks a boundary and the other reads ahead.

Two people shelving books from both ends

Two librarians start at opposite ends of a sorted shelf looking for two books whose page counts add to a target. If the total is too big, the person at the big end steps inward; if too small, the person at the small end steps inward. Nobody ever needs to walk back.

When to use it

Find a pair or triplet in a sorted array with a target sum or difference.
Check symmetry: palindromes, reversing arrays or strings in place.
Remove duplicates or filter elements in place with O(1) extra memory.
Merge two sorted arrays or lists.
Partition an array around a value (the core of quicksort and Dutch national flag).

Problem patterns it solves

Opposite ends on sorted input

Recognize it when: sorted array, find a pair / triplet / quadruplet with a target sum, or maximize something that depends on both ends.

167. Two Sum II
15. 3Sum
18. 4Sum
633. Sum of Square Numbers
11. Container With Most Water

Symmetry checks

Recognize it when: palindrome, reverse in place, compare from both ends.

125. Valid Palindrome
344. Reverse String
680. Valid Palindrome II
859. Buddy Strings

Read / write pointers (in-place)

Recognize it when: remove, compact, or deduplicate in place with O(1) extra space.

26. Remove Duplicates from Sorted Array
27. Remove Element
283. Move Zeroes

Partitioning

Recognize it when: group values into regions (less / equal / greater, even / odd) in one pass.

75. Sort Colors
905. Sort Array By Parity
2161. Partition Array According to Pivot

Walking two sequences together

Recognize it when: two sorted arrays or lists, merge, intersect, or match workers to jobs.

88. Merge Sorted Array
350. Intersection of Two Arrays II
826. Most Profit Assigning Work

Where it is used in real software

Merge join in databases

When both inputs are sorted on the join key, the query planner walks one pointer per table and emits matches in a single pass instead of a nested loop.

Quicksort partitioning

The partition step of quicksort, used inside many standard library sorts, is a two-pointer sweep that swaps elements across the pivot.

Diff and sync tools

Comparing two sorted file listings or ID lists to find additions and deletions walks both lists with one pointer each.

In-place compaction

Buffers and arrays drop deleted entries by keeping a write pointer behind a read pointer, avoiding a second allocation.

Key terms

Left / right pointer: Indexes starting at both ends that move toward each other.
Slow / fast pointer: Same-direction indexes: fast reads every element, slow marks where the next kept element is written.
Elimination argument: The proof that moving a pointer never skips a valid answer.

How it works, step by step

1
Choose the pointer layout
Opposite ends for sorted pair problems and symmetry. Same direction for in-place filtering and deduplication.
2
Define the movement rule
For a sorted pair sum: if sum < target, move left forward (need bigger); if sum > target, move right backward (need smaller).
3
Prove nothing is skipped
When sum > target with the current right value, pairing it with anything further right than left only grows the sum, so right can be discarded safely.
4
Stop when pointers cross
For opposite pointers, loop while left < right. For slow/fast, stop when fast reaches the end.

Find two numbers that sum to 15

STEP 11 + 15 = 16, which is too big. Every pair using 15 is at least 16, so 15 can be discarded.

Find two numbers that sum to 15

values = [1, 2, 4, 7, 11, 15] (sorted), target = 15

Step	left	right	Pair	Sum	Action
1	0	5	1 + 15	16	16 > 15, right--
2	0	4	1 + 11	12	12 < 15, left++
3	1	4	2 + 11	13	13 < 15, left++
4	2	4	4 + 11	15	Found indexes (2, 4)

Four checks instead of up to 15 pairs. Every step removes one element from consideration, so the scan is at most n - 1 steps.

Implementation

1// Opposite-direction pointers on a sorted array.2function pairWithSum(values: number[], target: number): [number, number] | null {3  let left = 0;4  let right = values.length - 1;5 6  while (left < right) {7    const sum = values[left] + values[right];8    if (sum === target) return [left, right];9    if (sum < target) left++;10    else right--;11  }12 13  return null;14}15 16// Same-direction pointers: remove duplicates in place, return new length.17function removeDuplicates(values: number[]): number {18  if (values.length === 0) return 0;19  let slow = 0;20  for (let fast = 1; fast < values.length; fast++) {21    if (values[fast] !== values[slow]) {22      slow++;23      values[slow] = values[fast];24    }25  }26  return slow + 1;27}

Complexity and performance

TimeO(n)

Each step moves at least one pointer, and each pointer moves at most n times.

SpaceO(1)

Only indexes are stored; in-place variants modify the input.

With sortingO(n log n)

If the input is unsorted, sorting dominates the cost.

Trade-offs

Two pointers vs hash set

An unsorted pair-sum problem can be solved in O(n) time with a hash set but O(n) space. Two pointers use O(1) space but need sorted input.

Index loss after sorting

Sorting changes positions. If the original indexes are required, sort pairs of (value, index) or use a hash map instead.

Variants and related techniques

3Sum and 4Sum

Fix one (or two) elements with an outer loop, then run two pointers on the rest: O(n^2) for 3Sum. Skip equal values to avoid duplicate triplets.

Container with most water

Move the pointer at the shorter line, because the area is limited by the shorter side and moving the taller one can never help.

Partitioning

Dutch national flag uses three pointers (low, mid, high) to sort 0s, 1s, and 2s in one pass.

Fast and slow pointers

On linked lists, a pointer moving twice as fast detects cycles and finds the middle node.

Common mistakes

Using opposite pointers on unsorted input.
Fix: The movement rule depends on ordering. Sort first or use a hash map.
Returning duplicate triplets in 3Sum.
Fix: After a match, advance both pointers past equal values; skip equal values for the fixed element too.
Using left <= right for pair problems.
Fix: That can pair an element with itself. Use left < right.

Interview questions

Why does moving the right pointer never skip an answer?

In a sorted array, if values[left] + values[right] > target, then values[right] plus any value at index >= left is also too large. So values[right] cannot be in any valid pair and can be discarded.

When would you choose a hash map instead?

When the input is unsorted and original indexes matter, or when sorting would be too costly. The hash map approach is O(n) time and O(n) space.

Practice problems

Problem	Difficulty	What it trains
Valid Palindrome	Easy	Opposite pointers with character filtering.
Two Sum II - Input Array Is Sorted	Medium	The classic movement rule.
Remove Duplicates from Sorted Array	Easy	Slow/fast in-place writing.
3Sum	Medium	Outer loop plus two pointers with dedupe.
Container With Most Water	Medium	Greedy elimination proof.
Trapping Rain Water	Hard	Track left and right maximums while moving inward.