LeetCode #15 Medium

3Sum

Return all unique triplets [a, b, c] from nums that sum to 0. The solution set must not contain duplicate triplets.

arraytwo-pointerssorting

Open on LeetCode ↗

02

Intuition

💡

Sorting unlocks two tricks: it lets a left/right pointer pair converge by sum, and it groups duplicates together so we can skip them. Fix one number, then two-pointer the rest of the array for a pair completing zero.

03

Approach

1

Brute force, and the two problems it has

The obvious approach is three nested loops testing every triplet for a zero sum — O(n³). It has two pains: it's slow, and it produces the same triplet in many orders ([-1,0,1], [0,1,-1], …), so you'd need a set to dedupe. Both pains have the same root cause: the array has no order, so we can neither search efficiently nor recognize duplicates. That points at the fix — impose order by sorting.

2

Sorting unlocks a directional two-pointer search

Once the array is sorted, fix one number as an anchor at index i, and reduce the problem to “find a pair in the suffix that sums to −nums[i].” In a sorted array you can do that with two pointers, l just after the anchor and r at the end: compute the three-sum and let its sign steer you. Too small? The only way to grow it is to move l right to a larger value. Too big? Move r left to a smaller value. Exactly zero? Record it. This works because sorting guarantees moving l right never decreases the sum and moving r left never increases it — the search is monotonic, so each anchor costs only O(n).

3

Killing duplicates, and one early exit

Sorting also clusters equal values, which makes deduping cheap. Skip an anchor if it equals the previous anchor (nums[i] == nums[i−1]), since it would regenerate the same triplets. After recording a hit, advance l and r past any values equal to the ones just used, so each distinct pair is emitted once. Finally, because the array is sorted, the moment nums[i] > 0 the anchor and everything after it are positive and can't sum to zero — so we break. Total: O(n log n) sort plus O(n²) scanning.

04

Solution & live demo

python

▶1class Solution:
▶2    def threeSum(self, nums):
▶3        nums.sort()
▶4        res = []
▶5        n = len(nums)
▶6        for i in range(n - 2):
▶7            if i > 0 and nums[i] == nums[i - 1]:
▶8                continue
▶9            if nums[i] > 0:
▶10                break
▶11            l, r = i + 1, n - 1
▶12            while l < r:
▶13                s = nums[i] + nums[l] + nums[r]
▶14                if s < 0:
▶15                    l += 1
▶16                elif s > 0:
▶17                    r -= 1
▶18                else:
▶19                    res.append([nums[i], nums[l], nums[r]])
▶20                    l += 1
▶21                    r -= 1
▶22                    while l < r and nums[l] == nums[l - 1]:
▶23                        l += 1
▶24                    while l < r and nums[r] == nums[r + 1]:
▶25                        r -= 1
▶26        return res

05

Edge cases

Many duplicates, e.g. [0,0,0,0]

Anchor- and pointer-level skips ensure [0,0,0] is emitted exactly once.

No triplet sums to zero

The pointers exhaust every anchor without a hit and the result stays empty.

All positives or all negatives

The nums[i] > 0 early break and pointer logic quickly conclude no triplet is possible.

06

Complexity

Time

O(n²)

Space

O(1)

Sort is O(n log n); the two-pointer sweep per anchor is O(n), giving O(n²) overall (excluding output).