Pattern this teaches:Two Pointers
4Sum
A medium Two Pointers interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Two Pointers
- Sheets
- 2
- Core for
- 10 roles
The problem
Given an array of integers, find all unique quadruplets that sum to a target value.
Example 1
- Input
- nums = [2, -1, 0, 1, -2, 3], target = 1
- Output
- [[-2,-1,1,3],[-2,0,1,2]]
Example 2
- Input
- nums = [3, 3, 3, 3, 3], target = 12
- Output
- [[3,3,3,3]]
Constraints
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
How to think about it
Updated 2026-09-29Sorting turns finding combinations into a systematic ladder: fixing two outer values reduces the problem to an inward two-pointer search on the remainder. Because identical numbers group together, duplicate tuples can be skipped at every level before they are ever constructed.
Approaches, worst first
Four nested loops with set
time O(n^4) · space O(n)
Inspect every combination of four indices and insert sorted quadruplets into a hash set to deduplicate. The quartic runtime and set hashing overhead cause severe performance penalties on arrays near length 200.
Sort and two-pointer sweepWrite this one
time O(n^3) · space O(1)
Sort the array, then use two outer loops to fix indices i and j. An inward two-pointer pair scans the remaining interval [j+1, n-1] in linear time. Skipping adjacent identical values at all four positions eliminates duplicates in place.
Where people lose marks · 3
- 32-bit signed integer overflow when summing four elements. With individual values up to 10^9, the sum can reach ±4 × 10^9, requiring 64-bit integers for all intermediate additions.
- Skipping duplicates too early in outer loops. Moving past equal values must happen only after processing the first valid instance, or valid quadruplets like `[2,2,2,2]` will be ignored entirely.
- Omitting duplicate skipping after finding a matching quadruplet in the inner loop. Both left and right pointers must advance past identical adjacent values to avoid emitting duplicate results.
The theory behind it
Two Pointers — the ground this problem stands on. All Two Pointers problems
What Two Pointers is
Two pointers is a search coordinated by two fingers placed on different entries of an ordered row, stepping inward toward each other or advancing at different speeds. Instead of scanning with nested loops that re-examine identical pairs, each pointer moves unidirectionally based on comparisons. Because every movement permanently prunes bad candidate combinations, the search inspects the collection in a single joint pass.
When to reach for it
Reach for two pointers when problems require finding index pairs, reversing sequences, trapping rainwater, or filtering duplicates in sorted arrays. When an input is already sorted and an exhaustive search takes quadratic time, opposing pointers meeting in the center often solve it linearly. Fast and slow pointer variations also detect cycles or locate midpoint nodes across linked sequences.
How the pattern works
Initialize pointers at opposing edges for convergent searches, or start both at the beginning to move at different speeds. Under a convergent setup, calculate current pair metrics; if the sum falls short of your target, advance the lower pointer rightward to increase value, and if it exceeds your target, shift the upper pointer leftward to decrease value. Each pointer move throws away only pairs that were already known to be wrong, so the right answer is never missed.
More Two Pointers problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .