3Sum: definition
Find all unique groups of three values that sum to zero, using three different positions in an array.
Task example: 3Sum
Return every unique triplet whose sum is zero. Values may repeat if they come from different indices. Do not return the same value triplet twice. The order of triplets and the order within each triplet do not matter.
Both approaches preserve the original input. The optimized approach searches a sorted copy. We need all answers, so finding one match does not end the search.
Brute force: video explanation
nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
Prefer reading? Follow the steps below.
- Use indices i < j < k to visit every group of three positions exactly once. Add the three values and compare the sum with zero.
- For a match, sort only those three values and store their tuple in a set. The set keeps one copy even when different positions produce the same values.
- Indices 0, 1, 2 give [-1, 0, 1]. Indices 0, 3, 4 give [-1, -1, 2] after normalization. Indices 1, 2, 4 repeat the first answer. Finish all checks, then return the stored triplets as lists.
Time complexity · O(n³)
There are n(n - 1)(n - 2) / 6 triples. Each check, including sorting just three values, takes constant time. Expected time is O(n³), using average constant-time set insertion.
Space complexity · O(k)
The set stores k unique triplets, and the returned lists also use O(k) space. Auxiliary space is O(k), plus O(k) output space. The loop variables use O(1) space.
Two pointers: video explanation
nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
Prefer reading? Follow the steps below.
- Sort a copy of nums. Fix a[i], then place left at i + 1 and right at the last index. Skip a repeated fixed value. Stop when a[i] > 0, since all remaining values are positive.
- Compute a[i] + a[left] + a[right]. If it is below zero, move left inward; if above zero, move right inward. At zero, record the triplet, move both pointers, and skip repeated partner values.
- With sorted [-4, -1, -1, 0, 1, 2], fixing -4 finds nothing. Fixing the first -1 finds [-1, -1, 2] and [-1, 0, 1]. Skip the next fixed -1. Fixing 0 adds nothing. Return both unique triplets.
Why it works: if the total is too small, keeping left and reducing right cannot help. If it is too large, keeping right and increasing left cannot help. Sorted order lets us safely discard those choices instead of checking every triple.
Time complexity · O(n²)
Sorting costs O(n log n). Each fixed value uses an O(n) pointer scan, for O(n²) total time. This improves on the brute-force O(n³) search.
Space complexity · O(n + k)
This Python implementation uses O(n) auxiliary space for the sorted copy and sorting workspace. The returned k triplets use O(k) more, so total space is O(n + k). The pointer scan itself uses O(1) extra space.