Two Pointers · 008Medium
3Sum
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] with distinct indices such that they sum to zero. The solution set must not contain duplicate triplets.
Constraints
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
Examples
threeSum([-1, 0, 1, 2, -1, -4]) -> [[-1, -1, 2], [-1, 0, 1]] threeSum([0, 1, 1]) -> [] threeSum([0, 0, 0]) -> [[0, 0, 0]] threeSum([1, 2, 3]) -> [] // smallest input, no triplet sums to 0 threeSum([-1, -1, 2, 2, 0, 0]) -> [[-1, -1, 2]] // duplicates collapse to one triplet threeSum([3, 0, -2, -1, 1, 2]) -> [[-2, -1, 3], [-2, 0, 2], [-1, 0, 1]] // order-agnostic
Edge cases
- Duplicate triplets must be filtered out — this is the hard part.
- Fewer than three elements.
- All zeros.
Show the target complexity (spoiler)
- Naive
- O(n^3) time — three nested loops plus a de-duplication pass.
- Target
- O(n^2) time, O(1) extra space — sort, then for each index run a two-pointer scan, skipping repeated values at every level.
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/008-three-sum.js ./practice c 008