8  Three Sum

Rank 6 · Pattern: sort, fix one value, scan with two pointers · Target: \(O(n^2)\) time

8.1 Problem definition

Given an integer array nums, return all unique triplets of values from the array whose sum is zero.

8.2 Clarifying questions

  1. Should the result contain values or original array indices?
  2. Must the three values come from three different array positions?
  3. What makes two triplets duplicates?
  4. Does the order of values within a triplet or the order of triplets in the result matter?
  5. May I reorder or modify the input array?
  6. What should I return for fewer than three values, and should I account for integer overflow?

8.3 Sample answers

  1. Return the values.
  2. Yes. Each triplet must use three distinct positions.
  3. Triplets with the same three values are duplicates, even if those values came from different positions; return each value combination once.
  4. No output order is required.
  5. Yes. Modifying and reordering nums are allowed.
  6. Return an empty list when no triplet can exist. Assume all three-value sums fit in a signed 32-bit int.

8.4 Data structures and APIs

Arrays.sort(int[]) sorts the input in place. An ArrayList collects immutable three-value List.of results.

sorted(nums) creates a sorted copy, and ordinary three-element lists are appended to the answer.

nums.to_vec() copies the borrowed slice, sort() orders it, and each result is a fixed-size [i32; 3] array.

8.5 Approach and invariant

Three nested loops cost \(O(n^3)\) and still require careful deduplication. Sorting exposes both a monotonic sum and adjacent duplicates.

For each sorted position i, fix nums[i], then search the suffix with left and right:

  • sum below zero → increment left to increase it;
  • sum above zero → decrement right to decrease it;
  • sum equals zero → record it, move both, and skip repeated values.

Skip a fixed value when it equals the previous fixed value. This prevents producing the same first value’s triplets twice.

sorted = [-4, -1, -1, 0, 1, 2]
               i   L        R

sum = -1 + -1 + 2 = 0  -> [-1,-1,2]
move both:         i       L R
sum = -1 +  0 + 1 = 0  -> [-1,0,1]

Invariant: for a fixed i, all pairs outside [left,right] have been either proved impossible or already emitted. Because the suffix is sorted, moving the appropriate pointer cannot skip a zero-sum pair.

8.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class ThreeSumSolution {
    static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    answer.add(List.of(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return answer;
    }

    @Test public void fewerThanThreeValuesHasNoTriplet() {
        assertTrue(threeSum(new int[] {1, -1}).isEmpty());
    }

    @Test public void findsSingleTriplet() {
        assertTriplets(
            List.of(List.of(-1, 0, 1)),
            threeSum(new int[] {-1, 0, 1})
        );
    }

    @Test public void handlesNoSolution() {
        assertTrue(threeSum(new int[] {1, 2, 3}).isEmpty());
    }

    @Test public void findsMultipleTripletsWithoutDuplicateInputs() {
        assertTriplets(
            List.of(
                List.of(-2, -1, 3),
                List.of(-2, 0, 2),
                List.of(-1, 0, 1)
            ),
            threeSum(new int[] {-2, -1, 0, 1, 2, 3})
        );
    }

    @Test public void skipsDuplicateFixedValues() {
        assertTriplets(
            List.of(List.of(-1, -1, 2), List.of(-1, 0, 1)),
            threeSum(new int[] {-1, 0, 1, 2, -1, -4})
        );
    }

    @Test public void deduplicatesZeros() {
        assertTriplets(
            List.of(List.of(0, 0, 0)),
            threeSum(new int[] {0, 0, 0, 0})
        );
    }

    @Test public void skipsDuplicatesAtBothPointers() {
        assertTriplets(
            List.of(List.of(-2, 0, 2)),
            threeSum(new int[] {-2, 0, 0, 2, 2})
        );
    }

    private static void assertTriplets(
            List<List<Integer>> expected, List<List<Integer>> actual) {
        assertEquals(expected.size(), actual.size());
        assertEquals(canonicalTriplets(expected), canonicalTriplets(actual));
    }

    private static Set<List<Integer>> canonicalTriplets(
            List<List<Integer>> triplets) {
        Set<List<Integer>> canonical = new HashSet<>();
        for (List<Integer> triplet : triplets) {
            List<Integer> sorted = new ArrayList<>(triplet);
            Collections.sort(sorted);
            canonical.add(sorted);
        }
        return canonical;
    }

    public static void main(String[] args) {
        JUnitCore.main("ThreeSumSolution");
    }
}
import unittest


def three_sum(nums):
    nums = sorted(nums)
    answer = []

    for index in range(len(nums) - 2):
        if index > 0 and nums[index] == nums[index - 1]:
            continue

        left = index + 1
        right = len(nums) - 1

        while left < right:
            total = nums[index] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                answer.append([nums[index], 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

    return answer


class ThreeSumTests(unittest.TestCase):
    def test_fewer_than_three_values(self):
        self.assertEqual([], three_sum([1, -1]))

    def test_finds_single_triplet(self):
        self.assertEqual([[-1, 0, 1]], three_sum([-1, 0, 1]))

    def test_handles_no_solution(self):
        self.assertEqual([], three_sum([1, 2, 3]))

    def test_finds_multiple_unique_triplets(self):
        self.assertEqual(
            [[-1, -1, 2], [-1, 0, 1]],
            three_sum([-1, 0, 1, 2, -1, -4]),
        )

    def test_deduplicates_zeros(self):
        self.assertEqual([[0, 0, 0]], three_sum([0, 0, 0, 0]))

    def test_does_not_modify_input(self):
        nums = [-1, 0, 1]
        original = nums.copy()
        three_sum(nums)
        self.assertEqual(original, nums)


if __name__ == "__main__":
    unittest.main()
pub fn three_sum(nums: &[i32]) -> Vec<[i32; 3]> {
    let mut nums = nums.to_vec();
    nums.sort();
    let mut answer = Vec::new();

    for index in 0..nums.len().saturating_sub(2) {
        if index > 0 && nums[index] == nums[index - 1] {
            continue;
        }

        let mut left = index + 1;
        let mut right = nums.len() - 1;

        while left < right {
            let total = nums[index] + nums[left] + nums[right];
            if total < 0 {
                left += 1;
            } else if total > 0 {
                right -= 1;
            } else {
                answer.push([nums[index], nums[left], nums[right]]);
                left += 1;
                right -= 1;
                while left < right && nums[left] == nums[left - 1] {
                    left += 1;
                }
                while left < right && nums[right] == nums[right + 1] {
                    right -= 1;
                }
            }
        }
    }

    answer
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn fewer_than_three_values() {
        assert_eq!(Vec::<[i32; 3]>::new(), three_sum(&[1, -1]));
    }

    #[test]
    fn finds_single_triplet() {
        assert_eq!(vec![[-1, 0, 1]], three_sum(&[-1, 0, 1]));
    }

    #[test]
    fn handles_no_solution() {
        assert!(three_sum(&[1, 2, 3]).is_empty());
    }

    #[test]
    fn finds_multiple_unique_triplets() {
        assert_eq!(
            vec![[-1, -1, 2], [-1, 0, 1]],
            three_sum(&[-1, 0, 1, 2, -1, -4])
        );
    }

    #[test]
    fn deduplicates_zeros() {
        assert_eq!(vec![[0, 0, 0]], three_sum(&[0, 0, 0, 0]));
    }
}

8.7 High-value tests

Input Expected Purpose
[-1,0,1,2,-1,-4] [[-1,-1,2],[-1,0,1]] normal + duplicates
[0,0,0,0] [[0,0,0]] one unique triplet
[1,2,3] [] no answer
[-2,0,0,2,2] [[-2,0,2]] skip both-side duplicates
fewer than 3 values [] loop boundary

8.8 Complexity and correctness

Sorting is \(O(n\log n)\). The outer loop runs \(O(n)\) times and each two-pointer scan is \(O(n)\), so total time is \(O(n^2)\). Java sorts the allowed mutable input in place; Python and Rust deliberately use a sorted copy and therefore use \(O(n)\) auxiliary space. Output space is separate.

For fixed i, sorted order justifies discarding the left value when the sum is too small and the right value when it is too large. Every emitted triple uses three ordered, distinct positions. The two duplicate-skipping rules give each value triple a unique fixed position and pointer combination.

8.9 If the interviewer pushes

  • Use long sum = (long) nums[i] + nums[left] + nums[right] if values can overflow int.
  • Stop the outer loop when nums[i] > 0; no later all-nonnegative triple can sum to zero.
  • Generalize to target t by comparing with t rather than zero.
  • Generalize to \(k\)-sum recursively; the usual time becomes roughly \(O(n^{k-1})\).
  • Copy the input before sorting if mutation is forbidden.

8.10 TDD interview script

Confirm that the method returns unique value triplets from three distinct positions, output order is irrelevant, input mutation is allowed, fewer than three values produce an empty result, and sums fit in int. Then write this test list:

  1. Too-short input
  2. One triplet
  3. No triplet
  4. Several triplets
  5. All zeros
  6. Duplicates at both pointers

Run one red–green–refactor cycle per behavior. The test helper canonicalizes both the order of values inside a triplet and the order of triplets, then separately checks result size so duplicate outputs cannot hide inside a set. That honors the contract without coupling tests to the traversal order.

From book/src, run:

./java/run.sh ThreeSumSolution
./python/run.sh three_sum_solution
./rust/run.sh three_sum_solution

Narrate the algorithmic transition: sorting turns the remaining two-value search into a monotonic problem. After a match, moving both pointers and skipping adjacent equal values prevents the same value triplet from being emitted again.

8.10.1 Pseudocode

sort nums
answer = empty list

for i from 0 through nums.length - 3:
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    left = i + 1
    right = nums.length - 1

    while left < right:
        sum = nums[i] + nums[left] + nums[right]
        if sum < 0:
            left++
        else if sum > 0:
            right--
        else:
            add [nums[i], nums[left], nums[right]]
            move both pointers
            skip repeated left and right values

return answer

For each fixed i, every pair outside [left, right] has been proved impossible or already emitted. Sorted order makes each pointer move safe.

8.10.2 TDD sequence

Step Test code added Production code added or changed
1. Too few values fewerThanThreeValuesHasNoTriplet Introduce the answer list and an outer-loop bound that performs no work for lengths below three.
2. One exact triplet findsSingleTriplet Sort, fix i, initialize two pointers, and emit when the sum is zero. Add the order-insensitive assertion helper.
3. Directional movement handlesNoSolution Move left for a negative sum and right for a positive sum until they cross.
4. Every solution findsMultipleTripletsWithoutDuplicateInputs Repeat the two-pointer search for each fixed position and accumulate all matches.
5. Duplicate fixed values skipsDuplicateFixedValues Skip an i value equal to its predecessor so the same first value is not processed twice.
6. Repeated zeros deduplicatesZeros After a match, move both pointers and skip adjacent duplicates so four zeros emit only one triplet.
7. Both-side duplicates skipsDuplicatesAtBothPointers Triangulate duplicate skipping independently on the left and right sides.

The sequence separates pointer direction from deduplication. Canonicalized assertions preserve the contract’s ordering freedom while still detecting duplicate or missing triplets.