Three Sum

Find all unique triplets in an array that sum to zero.

sorting two-pointer unique-triplets arrays

Write a function `three_sum(nums)` that takes a list of integers `nums` (length 0 to 3000). Return a list of all unique triplets `[a, b, c]` such that `a + b + c == 0` and the triplets are unique (no duplicate triplets). Each triplet itself should be sorted in non-decreasing order. The order of triplets in the output list does not matter. For example, for input `[-1, 0, 1, 2, -1, -4]`, the output should be `[[-1, -1, 2], [-1, 0, 1]]` (or any order).

Constraints

0 <= len(nums) <= 3000
-10^5 <= nums[i] <= 10^5
Time complexity: O(n^2) accepted. Space complexity: O(n) for storing results (excluding output).

Example

>>> three_sum([-1, 0, 1, 2, -1, -4])
[[-1, -1, 2], [-1, 0, 1]]
>>> three_sum([])
[]
>>> three_sum([0])
[]
>>> three_sum([0, 0, 0])
[[0, 0, 0]]

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the array first to make it easier to avoid duplicates and use two pointers.

For each index i, use two pointers left and right to find pairs that sum to -nums[i].

Skip duplicate values for i and after finding a valid triplet, move both pointers while skipping duplicates.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.