3Sum – Solution & Complexity

Q: What is the time and space complexity of 3Sum?

The optimal 3Sum solution runs in `O(n^2)` time and `O(1) extra (excluding output)` space. Sort the array, fix one value, then two-pointer scan the rest while skipping duplicates.

Q: What is the most efficient way to solve 3Sum?

Sort the array, fix one value, then two-pointer scan the rest while skipping duplicates. This gives `O(n^2)` time complexity, and is a classic arrays, two pointers, hashmap, and sorting problem.

Q: How do you solve 3Sum in Python, JavaScript, Java, Go & Rust?

We provide a worked 3Sum solution in Python, JavaScript, Java, Go & Rust with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is 3Sum an easy or hard interview question?

3Sum is generally rated **Medium**. It tests arrays, two pointers, hashmap, and sorting, which are common coding-interview patterns.

Solution Walkthrough

1. Understanding the Problem

You need every unique triplet of values in nums that sums to zero.
"Unique" means by value, not by index — if the same three numbers can be picked in more than one way, only report them once.
A brute-force triple nested loop checking every (i, j, k) combination works but is O(n^3) and still needs a set to dedupe.

2. Reducing to Two Sum via Sorting

Sort nums first. Sorting does two things: it makes duplicate values adjacent (easy to skip), and it lets you solve the remaining two-value subproblem with two pointers instead of a nested loop.
Fix the first value nums[i] in a single pass. For each i, you now need two other numbers, l and r with l, r > i, such that nums[l] + nums[r] == -nums[i]. That's exactly the sorted-array two-pointer pattern from Two Sum II.
Skip repeated values of nums[i] (if i > 0 and nums[i] == nums[i-1]: continue) so the same first value isn't used to start two identical triplets.

3. Two-Pointer Scan for the Remaining Pair

For each i, start l = i + 1 and r = n - 1.
If nums[i] + nums[l] + nums[r] < 0, the sum is too small — move l right to increase it.
If it's > 0, the sum is too big — move r left to decrease it.
If it's exactly 0, record [nums[i], nums[l], nums[r]], then advance both pointers inward, skipping over any further duplicate values at the new l/r so the same pair isn't recorded twice.

4. Final Solution (all languages)

Sorting is O(n log n), and the fixed-index + two-pointer scan is O(n) per index, giving O(n^2) total — the standard optimal complexity for 3Sum.

def three_sum(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    res = []
    n = len(nums)
    for i in range(n):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, n - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1
    return res

5. Common mistakes & interviewer follow-ups

Forgetting to sort first — the two-pointer shrink/grow logic only works because the remaining subarray is ordered.
Skipping the duplicate-value check on i but forgetting it on l/r too (or vice versa) — both are needed to avoid duplicate triplets.
Advancing l and r inside the duplicate-skipping while loops without also checking l < r, which can walk past the valid window.
Follow-ups: how would you solve 4Sum with the same pattern (fix two indices, two-pointer the rest)? What changes if the array can't be sorted (e.g. you must preserve original indices)?

3Sum – Solution & Complexity

Solution Walkthrough

1. Understanding the Problem

2. Reducing to Two Sum via Sorting

3. Two-Pointer Scan for the Remaining Pair

4. Final Solution (all languages)

5. Common mistakes & interviewer follow-ups

FAQ

What is the time and space complexity of 3Sum?

What is the most efficient way to solve 3Sum?

How do you solve 3Sum in Python, JavaScript, Java, Go & Rust?

Is 3Sum an easy or hard interview question?

See also