3Sum Solution | SkillFlow

Problem

Given an integer array, find all unique triplets of elements that sum to zero. Each index may only be used once, and the result must not contain duplicate triplets — even when the same value appears at multiple indices.

Example:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: Both triplets sum to zero; [-1, -1, 2] uses the two separate -1 entries at different positions.

Counter-example: [-2, 0, 0, 2, 2] → [[-2, 0, 2]] only, not [[-2, 0, 2], [-2, 0, 2]] — duplicate triplets are excluded regardless of which indices produced them.

Intuition

The problem asks: for every element, find two others that cancel it out. A three-loop scan is the obvious baseline but runs O(n³). Sorting first unlocks a two-pointer sweep that reduces the inner two-element search from O(n²) to O(n) — once the array is sorted, if the current sum is too small you advance the left pointer to a larger value, and if it's too large you retreat the right pointer to a smaller one. Sorting also makes duplicate-skipping trivial: equal adjacent elements can be stepped over with a single comparison rather than a hash lookup.

Approach 1 — Brute Force

Try every combination of three distinct indices and record those that sum to zero; use a set of sorted tuples to suppress duplicates.

Use three nested loops over indices i < j < k.
Check whether nums[i] + nums[j] + nums[k] == 0.
Sort the three values and add the resulting tuple to a set.
Convert the set to a list of lists before returning.

1def threeSum(nums):
2    seen_triplets = set()
3    n = len(nums)
4    for i in range(n - 2):
5        for j in range(i + 1, n - 1):
6            for k in range(j + 1, n):
7                if nums[i] + nums[j] + nums[k] == 0:
8                    triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
9                    seen_triplets.add(triplet)
10    return [list(t) for t in seen_triplets]

Time: O(n³) — three nested loops each up to n iterations, plus O(k log k) set operations on k output triplets.
Space: O(k) — the set stores up to k unique triplets.

Approach 2 — Sort + Two Pointers

Sort the array, then fix one element as an anchor and use two pointers converging from both ends of the remaining subarray. Skip over duplicate values at each pointer position to avoid emitting the same triplet twice.

Sort nums in ascending order.
Iterate i from 0 to n − 3; if nums[i] equals nums[i − 1], skip to avoid a duplicate anchor.
Set left = i + 1 and right = n − 1.
While left < right, compute the three-element sum:
- Sum is zero: record the triplet; advance both pointers past any duplicates; then move each one step inward.
- Sum is negative: increment left to raise the total.
- Sum is positive: decrement right to lower the total.

1def threeSum(nums):
2    nums.sort()
3    result = []
4
5    for i in range(len(nums) - 2):
6        if i > 0 and nums[i] == nums[i - 1]:  # skip duplicate anchor values
7            continue
8
9        left, right = i + 1, len(nums) - 1
10
11        while left < right:
12            total = nums[i] + nums[left] + nums[right]
13
14            if total == 0:
15                result.append([nums[i], nums[left], nums[right]])
16                while left < right and nums[left] == nums[left + 1]:  # skip left duplicates before moving
17                    left += 1
18                while left < right and nums[right] == nums[right - 1]:  # skip right duplicates before moving
19                    right -= 1
20                left += 1
21                right -= 1
22            elif total < 0:
23                left += 1  # current sum too small; move left toward a larger value
24            else:
25                right -= 1  # current sum too large; move right toward a smaller value
26
27    return result

Time: O(n²) — sorting is O(n log n); the outer loop runs n times with an O(n) two-pointer sweep inside, dominating at O(n²).
Space: O(1) extra, excluding the output list and the O(log n) sort stack.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n³)	O(k)	Never in practice — establishes the naive baseline
Sort + Two Pointers	O(n²)	O(1)	Always — the canonical solution expected in interviews

Common Mistakes

Forgetting the anchor duplicate check: Without if i > 0 and nums[i] == nums[i - 1]: continue, the same anchor value gets processed multiple times, producing duplicate triplets in the output.
Skipping duplicates before recording the triplet: The inner skip loops must run after appending the result. If you advance the pointers first, you skip the value you just matched.
Starting inner pointers at the wrong position: left must begin at i + 1, not 0 or i. Starting at i reuses the anchor element; starting at 0 revisits elements before i that have already been exhausted as anchors.
Wrong outer loop bound: The loop must stop at len(nums) - 2 (exclusive) so that left and right always have at least one position each. A bound of len(nums) lets i run into territory where no valid pair can exist.
Using a hash set for deduplication instead of pointer skipping: Storing sorted tuples in a set works but hides the two-pointer insight interviewers want to see demonstrated, and adds O(k log k) extra work.

3Sum — Solution