Difficulty: MediumTwo Pointers

3Sum

Problem in Plain English

Given an integer array nums, return all unique triplets of values that add up to zero, where the three values come from three different positions. No duplicate triplet may appear in the answer.

Problem Statement

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] with three different indices i, j and k such that nums[i] + nums[j] + nums[k] == 0.

The answer must not contain duplicate triplets: two triplets with the same three values in any order count as one, and the triplets may be returned in any order.

Constraints

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

Examples

Example 1

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

The index triplets (0, 1, 2) and (0, 3, 4) give (-1) + 0 + 1 = 0 and (-1) + 2 + (-1) = 0, which are the distinct triplets [-1, 0, 1] and [-1, -1, 2].

Example 2

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

The only triplet available is [0, 1, 1], which sums to 2, so no triplet qualifies.

Example 3

Input: nums = [0,0,0]
Output: [[0,0,0]]

The single available triplet [0, 0, 0] sums to 0, so it is the whole answer.

Example 4

Input: nums = [-2, 0, 0, 2, 2]
Output: [[-2, 0, 2]]

Several index choices use the repeated zero and two, but they all give the same value triplet. Return it only once.

Example 5

Input: nums = [-100000, 0, 100000]
Output: [[-100000, 0, 100000]]

The smallest and largest allowed values cancel with zero. Values may be far apart after sorting, so the pair scan starts at both ends.

Intuition

Three different positions must contribute to a sum of zero, but the answer identifies value combinations rather than positions. Example 1 finds [-1, 0, 1] at more than one index combination, yet it appears only once in the result. Fix one value and search for two others whose sum is its negative. Sorting lets a small pair sum be increased by moving the left pointer and a large pair sum be decreased by moving the right pointer.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Enumerate all combinations of three distinct indices. When a sum is zero, sort the three values into a canonical order and store that triplet in a set. This directly follows the definition but repeats a cubic amount of work.

Step-by-Step Logic

Create an empty set of unique triplets. Loop over indices with i < j < k, so no position is reused and each index combination is checked once.
For each combination, add its three values. If the sum is not zero, move to the next combination. Example 1 begins with (0, 1, 2) and values [-1, 0, 1], whose sum is zero.
For a match, sort just those three values and insert that canonical triplet into the set. (0, 3, 4) stores [-1, -1, 2].
Continue through every combination. (1, 2, 4) also sums to zero, but its canonical triplet [-1, 0, 1] is already present and adds nothing.
Convert the set to a list and return the two unique triplets in any order. The original array need not be sorted or modified.

Why It Works

Every legal three-index choice has exactly one ordering with i less than j less than k, so the loops inspect all choices without reusing positions. Keeping only sums of zero excludes invalid answers. Sorting each match gives the same representation for all permutations of its values; set membership removes repeated value combinations while retaining every distinct valid triplet.

Dry Run

Brute Force: variable states at each step
i,j,k	Values	Sum	Decision	Unique triplets so far
`0,1,2`	`[-1,0,1]`	`0`	insert sorted triplet	`[[-1,0,1]]`
`0,1,3`	`[-1,0,2]`	`1`	reject	`[[-1,0,1]]`
`0,1,4`	`[-1,0,-1]`	`-2`	reject	`[[-1,0,1]]`
`0,1,5`	`[-1,0,-4]`	`-5`	reject	`[[-1,0,1]]`
`0,2,3`	`[-1,1,2]`	`2`	reject	`[[-1,0,1]]`
`0,2,4`	`[-1,1,-1]`	`-1`	reject	`[[-1,0,1]]`
`0,2,5`	`[-1,1,-4]`	`-4`	reject	`[[-1,0,1]]`
`0,3,4`	`[-1,2,-1]`	`0`	insert sorted triplet	`[[-1,0,1],[-1,-1,2]]`
`0,3,5`	`[-1,2,-4]`	`-3`	reject	`[[-1,0,1],[-1,-1,2]]`
`0,4,5`	`[-1,-1,-4]`	`-6`	reject	`[[-1,0,1],[-1,-1,2]]`
`1,2,3`	`[0,1,2]`	`3`	reject	`[[-1,0,1],[-1,-1,2]]`
`1,2,4`	`[0,1,-1]`	`0`	duplicate; keep set	`[[-1,0,1],[-1,-1,2]]`
`1,2,5`	`[0,1,-4]`	`-3`	reject	`[[-1,0,1],[-1,-1,2]]`
`1,3,4`	`[0,2,-1]`	`1`	reject	`[[-1,0,1],[-1,-1,2]]`
`1,3,5`	`[0,2,-4]`	`-2`	reject	`[[-1,0,1],[-1,-1,2]]`
`1,4,5`	`[0,-1,-4]`	`-5`	reject	`[[-1,0,1],[-1,-1,2]]`
`2,3,4`	`[1,2,-1]`	`2`	reject	`[[-1,0,1],[-1,-1,2]]`
`2,3,5`	`[1,2,-4]`	`-1`	reject	`[[-1,0,1],[-1,-1,2]]`
`2,4,5`	`[1,-1,-4]`	`-4`	reject	`[[-1,0,1],[-1,-1,2]]`
`3,4,5`	`[2,-1,-4]`	`-3`	reject	`[[-1,0,1],[-1,-1,2]]`
Finish	all 20 combinations	none	return in any order	`[[-1,-1,2],[-1,0,1]]`

Complexity Analysis

Time Complexity

O(n^3)

Space Complexity

O(n^2)

Let n be the array length and t the number of returned unique triplets. The loops check n(n - 1)(n - 2)/6 combinations, giving O(n^3) expected time with set insertion. Each triplet contains only three values, so its sorting is constant work. The set and returned list use O(t) storage; t can be O(n^2), since two values determine the third. The space bound includes stored answers, not just loop counters.

Code

Solution.java

1import java.util.List;2import java.util.Set;3import java.util.HashSet;4import java.util.Arrays;5import java.util.Collections;6import java.util.ArrayList;7
8class Solution {9    public List<List<Integer>> threeSum(int[] nums) {10        Set<List<Integer>> seen = new HashSet<>();11        for (int i = 0; i < nums.length - 2; i++) {12            for (int j = i + 1; j < nums.length - 1; j++) {13                for (int k = j + 1; k < nums.length; k++) {14                    if (nums[i] + nums[j] + nums[k] == 0) {15                        List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);16                        Collections.sort(triplet);17                        seen.add(triplet);18                    }19                }20            }21        }22        return new ArrayList<>(seen);23    }24}

Hints

Hint 1

If the array were sorted, fixing one value would leave a familiar two-number search for the remaining sum.

Hint 2

With two pointers on a sorted range, when is it safe to move the left pointer, and when the right one?

Hint 3

Equal neighbours produce equal triplets, so each pointer must jump past values it has already used.

Edge Cases

Exactly three elements either produce one triplet or none. Arrays shorter than three are outside this problem's constraints.
All zeros such as [0, 0, 0, 0] produce just [[0, 0, 0]]; three distinct positions can still hold equal values.
Heavy duplicates such as [-2, 0, 0, 2, 2] produce only [[-2, 0, 2]]. Skipping repeated anchors alone is insufficient.
All-positive or all-negative arrays have no answer. No arbitrary position may be reused to cancel a value.
Under the stated bounds, a three-value sum lies within [-300000, 300000], safely represented by Java int and JavaScript Number. Reassess overflow if value bounds change.
The two-pointer implementation sorts nums in place. If preserving the original order is required by a caller, sort a copy and account for its O(n) allocation.

Common Mistakes and Interview Tips

Returning index combinations or repeated permutations answers a different question: return unique value triplets.
Using left equal to i, or accepting left equal to right, reuses a position. Start left at i + 1 and require left < right.
Moving pointers by the sum before sorting has no monotonic-order guarantee. In JavaScript, supply a numeric sort comparator rather than the default lexical sort.
Skipping duplicates only for the anchor can emit the same triplet multiple times. After a match, move both endpoints and skip both repeated values.
Interview tip: explain each safe discard with sorted order and distinguish scan variables, sort workspace, and result storage. The quadratic scan improves the cubic baseline; no claim of constant total storage applies when the output itself can be quadratic.

Key Takeaway

Sorting plus two pointers turns a K-sum search into a fixed-prefix loop around a linear two-sum scan, with duplicate-skipping keeping the output unique.