Topic · Two PointersMedium
3Sum
Understand the problem
Given an integer array nums, find all triplets of elements at distinct indices [i, j, k] such that nums[i] + nums[j] + nums[k] === 0. The result must not contain duplicate triplets.
Example:
ts
nums = [-1, 0, 1, 2, -1, -4]
output = [[-1, -1, 2], [-1, 0, 1]]
// Two valid triplets — no duplicates
nums = [0, 1, 1]
output = [] // no triplet sums to 0
nums = [0, 0, 0]
output = [[0, 0, 0]]"Distinct indices" means the same value at two different positions can still be used — but the same triplet of values must not be returned twice.
Basic approach
O(n³) time, O(n²) space in the worst case — the seen set can hold up to O(n²) distinct tripletsts
function threeSum(nums: number[]): number[][] {
const result: number[][] = []
const seen = new Set<string>()
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b)
const key = triple.join(',')
if (!seen.has(key)) { seen.add(key); result.push(triple) }
}
}
}
}
return result
}Why this approach is slow:
Three nested loops check every triplet.
- With n=3000 → 27·10⁹ operations — far over the limit.
- You need to get down to at least O(n²).
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.