#15 3Sum

Mediumsolve on LeetCode ↗

frequently reported atAdobe Bloomberg Walmart Amazon Microsoft ByteDance / TikTok

the problem

In plain words

Return all unique triplets [a, b, c] from nums with a + b + c = 0. The answer must not contain duplicate triplets.

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

out [[-1,-1,2],[-1,0,1]]

in nums = [0,1,1]

out []

No three numbers add up to 0.

in nums = [0,0,0]

out [[0,0,0]]

3 ≤ n ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (opposite ends)

Fix the first number, then the remaining problem is Two Sum II on the sorted suffix. Sorting also makes duplicates sit next to each other, so skipping them is easy.

solutions

From brute force to optimal

Try every triple; a set removes duplicates.

Sort so each triplet is generated in a canonical order.
Three nested loops.
Add zero-sum triplets to a LinkedHashSet.

timeO(n³)

n choose 3 triples.

spaceO(k)

k = number of unique triplets stored.

javajava.util.*

1class Solution {2    public List<List<Integer>> threeSum(int[] nums) {3        Arrays.sort(nums); // sorting makes each triplet come out in the same order4        Set<List<Integer>> seen = new LinkedHashSet<>();5        int n = nums.length;6        for (int i = 0; i < n; i++)7            for (int j = i + 1; j < n; j++)8                for (int k = j + 1; k < n; k++)9                    if (nums[i] + nums[j] + nums[k] == 0)10                        seen.add(List.of(nums[i], nums[j], nums[k]));11        return new ArrayList<>(seen);12    }13}

For each i, run hash-based Two Sum on the suffix.

Sort.
For each i, scan j and look up −nums[i]−nums[j] in a set of seen values.

timeO(n²)

n outer iterations × n inner.

spaceO(n)

The per-i hash set (plus output).

javajava.util.*

1class Solution {2    public List<List<Integer>> threeSum(int[] nums) {3        Arrays.sort(nums);4        Set<List<Integer>> result = new LinkedHashSet<>();5        for (int i = 0; i < nums.length; i++) {6            Set<Integer> seen = new HashSet<>();7            for (int j = i + 1; j < nums.length; j++) {8                int need = -nums[i] - nums[j];9                if (seen.contains(need)) result.add(List.of(nums[i], need, nums[j]));10                seen.add(nums[j]);11            }12        }13        return new ArrayList<>(result);14    }15}

Sort, fix nums[i], then converge left/right on the suffix; skip duplicates.

Sort.
For each i (skip if same as previous; stop if nums[i] > 0).
left = i+1, right = n−1: move by comparing the sum with 0.
On a hit, record it and skip equal values of left.

timeO(n²)

Sorting O(n log n) + n two-pointer scans of O(n).

spaceO(1) extra

Ignoring the output and the sort's O(log n) stack.

javajava.util.*

1class Solution {2    public List<List<Integer>> threeSum(int[] nums) {3        Arrays.sort(nums);4        List<List<Integer>> result = new ArrayList<>();5        for (int i = 0; i < nums.length - 2; i++) {6            if (nums[i] > 0) break;                          // smallest is positive → no zero sum7            if (i > 0 && nums[i] == nums[i - 1]) continue;   // skip duplicate anchors8            int left = i + 1, right = nums.length - 1;9            while (left < right) {10                int sum = nums[i] + nums[left] + nums[right];11                if (sum < 0) left++;12                else if (sum > 0) right--;13                else {14                    result.add(List.of(nums[i], nums[left], nums[right]));15                    left++;16                    right--;17                    while (left < right && nums[left] == nums[left - 1]) left++; // skip duplicates18                }19            }20        }21        return result;22    }23}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public List<List<Integer>> threeSum(int[] nums) {3        Arrays.sort(nums);4        List<List<Integer>> result = new ArrayList<>();5        for (int i = 0; i < nums.length - 2; i++) {6            if (nums[i] > 0) break;                          // smallest is positive → no zero sum7            if (i > 0 && nums[i] == nums[i - 1]) continue;   // skip duplicate anchors8            int left = i + 1, right = nums.length - 1;9            while (left < right) {10                int sum = nums[i] + nums[left] + nums[right];11                if (sum < 0) left++;12                else if (sum > 0) right--;13                else {14                    result.add(List.of(nums[i], nums[left], nums[right]));15                    left++;16                    right--;17                    while (left < right && nums[left] == nums[left - 1]) left++; // skip duplicates18                }19            }20        }21        return result;22    }23}

in the room

How to say it in the interview

talk track

Say: "3Sum reduces to n runs of Two Sum II after sorting."
Call out duplicate handling explicitly — it's the part most candidates get wrong.

traps

Skipping duplicates of i with nums[i] == nums[i+1] (wrong direction — you'd skip valid triplets like [-1,-1,2]).

what they ask next

Follow-ups

3Sum Closest (LC 16)?

Same scan, but track the sum with the smallest |sum − target|.

4Sum (LC 18)?

Two outer loops + two pointers → O(n³). Use long for sums to avoid overflow.

before you submit

Edge cases to test

All zeros [0, 0, 0, 0] → exactly one triplet [0, 0, 0].
No answer, e.g. [0, 1, 1] → an empty list, not null.
Many duplicates like [-1, -1, -1, 2, 2] → [-1, -1, 2] only once.
3,000 numbers: every triple is about 4.5·10⁹ checks — far too slow; sort + two pointers is about 4.5·10⁶ steps.

practise next