MEDIUM

3Sum

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] (distinct indices) whose values sum to zero. The result must not contain duplicate triplets.

Example

Input nums = [-1,0,1,2,-1,-4]

Output [[-1,-1,2],[-1,0,1]]

Key Pointers

Sort first — sorting turns duplicate-skipping into a simple adjacency check and enables a two-pointer sweep for the remaining pair.
Fix one number at a time, then solve "two numbers that sum to -fixed" on the rest of the sorted array with two pointers, just like Two Sum II.
Skip over duplicate values at every level — the outer loop and both inner pointers — to avoid emitting the same triplet twice, without needing a set.

Step-by-Step Analysis

Sort nums.
For each index i: skip it if nums[i] == nums[i-1] (duplicate fixed value); stop entirely if nums[i] > 0, since a sorted positive start can't sum to zero.
Set left = i + 1, right = len(nums) - 1, and run the two-pointer sweep from Two Sum II on the subarray.
On a zero sum, record the triplet and advance both pointers past any duplicate values; on a negative sum move left forward, on a positive sum move right backward.

Complexity

Time: O(n²) — Space: O(1) extra, not counting the sort or the output

Code

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        if nums[i] > 0:
            break

        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

    return result

Code Explanation

How the solution above works, piece by piece.

nums.sort(): sorting puts equal values next to each other (easy duplicate skipping) and lets two pointers decide which way to move. The example becomes [-4, -1, -1, 0, 1, 2].
for i in range(len(nums)): fix one number, nums[i]. Now we only need two more numbers that add up to -nums[i].
if i > 0 and nums[i] == nums[i - 1]: continue: the same fixed value would find the same triplets again, so skip it.
if nums[i] > 0: break: everything to the right is at least as big, so three positives can never sum to 0. Stop early.
left, right = i + 1, len(nums) - 1: search the part after i from both ends.
Compute total. If it is too small, left += 1 makes it bigger; if too big, right -= 1 makes it smaller. The array is sorted, so each move is the only one that can help.
total == 0: record the triplet, move both pointers inward, then skip any repeated values on each side so the same triplet isn't added twice.
Each i does one O(n) sweep, so O(n²) overall, and no extra set is needed for de-duplication.

Visual Walkthrough

Running the solution on nums = [-1, 0, 1, 2, -1, -4]:

Each row is one check. Amber = the fixed number nums[i]; blue = left and right. The sum decides which pointer moves: too small → move left right, too big → move right left. Two triplets are found, both while i = 1.

fixed nums[i]left / rightskipped / stop

Video Explanation

NeetCode — 3Sum, LeetCode 15