☕ DSA Java Articles

Topics › Arrays › Hard

3 Sum

Medium TUF ID 27 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums. Return every distinct triplet of values [a, b, c] taken from three different positions such that a + b + c == 0. Two triplets are the same if they contain the same three values, regardless of order or of which indices produced them, so each triplet should appear once. Report each triplet in non-decreasing order; the order of the triplets themselves does not matter.

Constraints: 0 ≤ n ≤ 3000, values fit in a 32-bit signed integer.

Example 1

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

-1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. The triplet [0, 1, -1] is the same set of values as [-1, 0, 1], so it is not listed twice.

Example 2

nums = [0, 0, 0, 0]
answer = [[0, 0, 0]]

Four zeros give four different index triples, but all of them are the same value triplet.

Example 3

nums = [0, 1, 1]
answer = []

No three values add up to zero.

Approach 1: Brute force

Intuition. The statement is “some three elements sum to zero”, so enumerate every triple of indices i < j < k. The only wrinkle is uniqueness: the same value triplet can come from many index triples, so sort each found triplet and drop it into a Set, which silently discards repeats.

Algorithm.

  1. For every i, every j > i, every k > j: if nums[i] + nums[j] + nums[k] == 0, sort the three values and add them to a set.
  2. Return the set’s contents (sorted here only so tests can compare approaches).
static List<List<Integer>> bruteForce(int[] nums) {
    int n = nums.length;
    Set<List<Integer>> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((long) nums[i] + nums[j] + nums[k] == 0) {
                    int[] t = {nums[i], nums[j], nums[k]};
                    Arrays.sort(t);
                    set.add(List.of(t[0], t[1], t[2]));
                }
            }
        }
    }
    return sorted(set);
}

Complexity. Time O(n^3): about n^3 / 6 triples, each checked in constant time (the set insert is O(1) on average for 3-element lists). Space O(k) for the k distinct triplets in the set.

The (long) cast is not decoration: three values near 10^9 add up to 3 × 10^9, outside the int range, and a wrapped sum could accidentally become 0.

For n = 3000 this is 4.5 × 10^9 triple checks, far too slow. We need to stop paying for the third loop.

Approach 2: Better, hashing the third value

Intuition. Once two values nums[i] and nums[j] are fixed, the third one is forced: it must be -(nums[i] + nums[j]). Instead of searching for it with a loop, ask a hash set “have you seen this value?” This is exactly the trick from Two Sum, applied once per fixed i.

To avoid counting the same index triple three times, and to avoid pairing an element with itself, keep the set restricted to the values strictly between i and j. Fix i, start with an empty set, and as j moves right, check the set for the needed value and only then insert nums[j]. Every index triple i < k < j is then discovered exactly once, when the outer index is i and the scanning index is j.

Algorithm.

  1. For each i, create an empty set seen.
  2. For each j > i: compute need = -(nums[i] + nums[j]).
    • If need is in seen, sort {nums[i], nums[j], need} and add it to the result set.
    • Insert nums[j] into seen.
  3. Return the result set.
static List<List<Integer>> better(int[] nums) {
    int n = nums.length;
    Set<List<Integer>> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        Set<Integer> seen = new HashSet<>();           // values nums[i+1 .. j-1]
        for (int j = i + 1; j < n; j++) {
            long need = -(long) nums[i] - nums[j];     // third value that would complete the triplet
            if (need >= Integer.MIN_VALUE && need <= Integer.MAX_VALUE && seen.contains((int) need)) {
                int[] t = {nums[i], nums[j], (int) need};
                Arrays.sort(t);
                set.add(List.of(t[0], t[1], t[2]));
            }
            seen.add(nums[j]);
        }
    }
    return sorted(set);
}

Complexity. Time O(n^2): two nested loops with O(1) average hash operations inside. Space O(n) for seen, plus the output set.

need is computed as a long because -(nums[i] + nums[j]) can leave the int range; a value outside that range cannot be in the array, so we skip the lookup entirely.

The downside is constant factors and memory: two hash structures, boxing of every value, and hashing of every triplet. The optimal approach removes all of that.

Approach 3: Optimal, sort and two pointers

Intuition. Sort the array. Fix the smallest element of the triplet, a[i]. The remaining two must come from a[i+1 .. n-1] and sum to -a[i]. In a sorted range, a pair with a given sum is found by two pointers: lo at the left end, hi at the right end. If a[i] + a[lo] + a[hi] is too small, only moving lo right can increase it; if too large, only moving hi left can decrease it. Each step retires one element, so a fixed i costs O(n).

Sorting also makes de-duplication free. Equal values are adjacent, so after handling a[i] we skip to the next different value for i; and after recording a triplet we move lo and hi past any copies of the values just used. No set is needed, and the output comes out already in lexicographic order.

Algorithm.

  1. Sort a copy of the array.
  2. For each i from 0 to n - 3:
    • If a[i] == a[i-1], skip (this first value was processed already).
    • If a[i] > 0, stop: all remaining values are positive, their sum cannot be zero.
    • Set lo = i + 1, hi = n - 1. While lo < hi:
      • sum = a[i] + a[lo] + a[hi]. If sum < 0, lo++. If sum > 0, hi--.
      • Otherwise record [a[i], a[lo], a[hi]], move both pointers inward, and then skip over duplicates of a[lo-1] and a[hi+1].
  3. Return the list.
static List<List<Integer>> optimal(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && a[i] == a[i - 1]) continue;      // same first value was already handled
        if (a[i] > 0) break;                           // three positives can never sum to zero
        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            long sum = (long) a[i] + a[lo] + a[hi];
            if (sum < 0) lo++;
            else if (sum > 0) hi--;
            else {
                res.add(List.of(a[i], a[lo], a[hi]));
                lo++;
                hi--;
                while (lo < hi && a[lo] == a[lo - 1]) lo++;   // skip equal second values
                while (lo < hi && a[hi] == a[hi + 1]) hi--;   // skip equal third values
            }
        }
    }
    return res;
}

Dry run on nums = [-1, 0, 1, 2, -1, -4], sorted to a = [-4, -1, -1, 0, 1, 2]:

i a[i] lo, hi sum action
0 -4 1, 5 -3 lo++ (repeats until lo meets hi; nothing found)
1 -1 2, 5 0 record [-1, -1, 2]; lo=3, hi=4
1 -1 3, 4 0 record [-1, 0, 1]; lo=4, hi=3, stop
2 -1     a[2] == a[1], skip
3 0 4, 5 3 hi– then lo == hi, stop

Result: [[-1, -1, 2], [-1, 0, 1]].

Complexity. Time O(n^2): O(n log n) to sort, then n choices of i each with an O(n) two-pointer sweep. Space O(1) extra beyond the sorted copy and the output (sorting in place would make it truly O(1)).

Why does skipping duplicates not lose answers? Suppose a[lo] == a[lo+1] after a hit. Any triplet using a[lo+1] with the same a[i] would need a third value equal to the one just paired with a[lo], so it is the same value triplet. The same argument applies to i: if a[i] == a[i-1], every triplet starting at i was reachable from i - 1 with a strictly larger range.

Edge cases and pitfalls