3Sum

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

Time O(n²), space O(1) or O(n) for the sort.

Medium

Two Pointers

Fix one number, then two-pointer the rest for its negation.

Pointer Trace

Sort the numbers: [-4, -1, -1, 0, 1, 2]. Equal values are now neighbours.

StopTwo pointersExport

nums

Problem

Given an integer array, return all distinct triples of values whose sum is exactly zero. A triple may use three different positions, and the answer must not contain duplicate combinations even when the input contains repeated values. The order of triples and the order of values inside a triple do not matter.

Examples

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

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

The two unique triples that sum to zero are (-1, -1, 2) and (-1, 0, 1).

Input: nums = [0, 0, 0, 1, -1]

Output: [[-1, 0, 1], [0, 0, 0]]

Repeated zero values can form one unique triple, while -1, 0, and 1 form the other.

The Goal

Find every set of three numbers that adds up to 0, with no triple listed twice. The answer is the values, not their positions.

Checking every triple takes O(n³). Instead, sort the array, fix one number, and look for two more that add up to its negative. That's Two Sum II, run once for each fixed number.

Run two pointers over the numbers after i.

0 + 1 = 1 completes [-1, 0, 1].

Why Sorting Helps

Once the array is sorted, moving left right makes the pair bigger, and moving right left makes it smaller.

For a fixed nums[i], you need nums[left] + nums[right] = -nums[i]. Too small: move left. Too big: move right. Exactly right: record the triple and move both.

Fix -4 and the pair has to sum to 4. The first pair, -1 and 2, sums to 1, so left moves.

Sorted order does the work

Each comparison rules out every pair that uses the number a pointer leaves behind.

The Algorithm

Sorting puts equal values side by side, so you can skip repeats as you go instead of collecting results in a set.

python

nums.sort()
for i in range(len(nums) - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    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:
            answer.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

Skip repeats in three places: the fixed value, and both pointers after a match. Miss one and a triple comes out twice.

Approach	Time	Extra space	Tradeoff
Three nested loops	O(n^3)	O(1)	Checks every triple
Fix + hash set	O(n^2)	O(n)	Repeats need extra work
Sort + two pointers	O(n^2)	O(1) or O(n)	Sorting handles search and repeats

Walkthrough

Run it on [-1, 0, 1, 2, -1, -4]. Sorted, that's [-4, -1, -1, 0, 1, 2].

Fix -4. Every pair is too small, and left walks into right.
Fix -1. The pair has to sum to 1, and the scan finds [-1, -1, 2], then [-1, 0, 1].
The second -1 is skipped. It would repeat both triples.
Fix 0. 0 + 1 + 2 = 3 is too big. right moves left, the pointers meet, and the search ends.

Checkpoint · predict the next step

Step 5 of 16 on the stage: -4 + 0 + 2 = -2, below 0. Move left right, to a larger number.

i on -4 (index 0) · left on 0 (index 3) · right on 2 (index 5) · need 4 · sum -2 · found none

What does step 6 show?left on 2 (index 5)left on 1 (index 4) · sum -1left on 0 (index 3) · sum -2left on -1 (index 2) · sum -3

Step through it on the stage

Pitfalls

Skipping repeats of the fixed value isn't enough. After a match, an equal value at left or right rebuilds the same triple.
Skip only equal values next to each other, and only after sorting.
Fewer than three numbers gives no triples. All zeros gives exactly [[0, 0, 0]].
Once the fixed value is positive, everything after it is too, so you can stop early.

After sorting, which repeats do you skip?

Complexity

Sorting costs O(n log n). Each fixed value then gets one O(n) two-pointer scan, so the search is O(n²), and that dominates.

Extra space is O(1) with an in-place sort, or O(n) if your language's sort makes a copy. The output doesn't count.

Sort, then one scan per fixed value

Time

O(n^2)

Space

O(1) or O(n)

Where the time goes

Sort the arrayPuts equal values side by side.O(n log n)
Fix each first valueOne outer pass.O(n)
Two-pointer scansOne O(n) scan per fixed value.dominantO(n^2)

How it grows

Roughly what that costs

n	10	100	1,000	10,000
O(n²)	100	10K	1M	100M
O(n)	10	100	1K	10K

Quadratic, and sorting makes the repeats easy to skip.

In short

Sort the array. For each index i, use two pointers on the subarray to its right to find pairs summing to −nums[i]. Skip duplicate values for both the fixed element and the pointers to avoid repeated triples. Sorting makes both the search and dedupe straightforward.

TimeO(n²)SpaceO(1) or O(n) for the sort

Common mistake

Producing duplicate triples — you must skip equal adjacent values at every level, not just the outer loop.

NextTwo Sum II - Input Array Is Sorted →Sorted input lets two pointers steer toward the target.

Two Sum II - Input Array Is SortedMedium Container With Most WaterMedium