Two Pointers · 176Medium
4Sum
Given an array nums of n integers, return all UNIQUE quadruplets [nums[a], nums[b], nums[c], nums[d]] with distinct indices a, b, c, d whose sum equals target. The quadruplets and the numbers inside them may be in any order.
Constraints
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
Examples
fourSum([1, 0, -1, 0, -2, 2], 0) -> [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] fourSum([2, 2, 2, 2, 2], 8) -> [[2, 2, 2, 2]] fourSum([1, 2, 3], 6) -> [] // fewer than four elements fourSum([0, 0, 0, 0], 0) -> [[0, 0, 0, 0]] // exactly four, all zero fourSum([-3, -1, 0, 2, 4, 5], 2) -> [[-3, -1, 2, 4]] // negatives, one quadruplet fourSum([1, 1, 1, 1, 2, 2, 2], 6) -> [[1, 1, 2, 2]] // heavy duplicates, still one result
Edge cases
- Fewer than four elements returns [].
- Heavy duplicates must not produce repeated quadruplets.
Show the target complexity (spoiler)
- Naive
- O(n^4) time — every quadruple, deduplicated with a Set of sorted keys.
- Target
- O(n^3) time, O(1) extra space — sort; two nested loops fix a and b, then two pointers find c and d, skipping equal neighbours.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/02-two-pointers/176-four-sum.js ./practice c 176