3Sum

MEDIUM✓ CHIP-TIMEDLC #15 — FULL STATEMENT ↗

The drill: Find every unique triple of values that sums to zero — value-triples, not index-triples, so the same numbers in a different order never count twice.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives, and the task is to surface every combination of three distinct positions whose values add up to zero.

What matters is the triple of values, not which positions produced them — two triples with the same three numbers, even from different index combinations, count as one and only one answer.

The order of numbers within a triple, and the order triples appear in the result, doesn't matter for correctness; only the set of distinct value-triples found matters.

EX 01

nums = [-3, 1, 2, -2, 0, 3]

→ [[-3, 0, 3], [-3, 1, 2], [-2, 0, 2]]

EX 02

nums = [0, 0, 0]

→ [[0, 0, 0]]

EX 03

nums = [1, 2, 3]

→ []

array length runs from zero up to a few thousand elements
values can be negative, zero, or positive, with duplicates common
each triple must use three different positions in the array
duplicate value-triples must be collapsed to one entry each

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Cubic tries every triple and then fights duplicates on top. Sorting first makes both problems easier at once.

HINT 2 THE STRUCTURE

Fix the smallest element of the triple; what remains is two-sum on a sorted array — two pointers walking inward.

HINT 3 ONE STEP FROM THE ANSWER

Skip equal neighbours when advancing the anchor AND after each found pair — that is where the dedup lives. Sum too small → left pointer right; too big → right pointer left.

COACH'S BOARD — THE PATTERN, STEP BY STEP

ANCHOR AND CLOSEPATTERN · SORT + TWO POINTERSnums = [-4, -1, -1, 0, 1, 2] (sorted for the walk)

-4

-1

STEP 1

Sorted the array: [-4, -1, -1, 0, 1, 2]. Fix the smallest value as anchor, close the rest with two pointers.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/3sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        out = []
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            lo, hi = i + 1, n - 1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0:
                    lo += 1
                elif s > 0:
                    hi -= 1
                else:
                    out.append([nums[i], nums[lo], nums[hi]])
                    lo += 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
                    hi -= 1
        return out

TIME O(N²)SPACE O(1)PYTHON · RACE PACE · 22 LN

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        found = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
        return [list(t) for t in found]

TIME O(N³)SPACE O(N)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1;
            int hi = nums.length - 1;
            while (lo < hi) {
                int s = nums[i] + nums[lo] + nums[hi];
                if (s < 0) {
                    lo++;
                } else if (s > 0) {
                    hi--;
                } else {
                    out.add(List.of(nums[i], nums[lo], nums[hi]));
                    lo++;
                    while (lo < hi && nums[lo] == nums[lo - 1]) {
                        lo++;
                    }
                    hi--;
                }
            }
        }
        return out;
    }
}

TIME O(N²)SPACE O(1)JAVA · RACE PACE · 29 LN

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> found = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> t = new ArrayList<>(List.of(nums[i], nums[j], nums[k]));
                        Collections.sort(t);
                        found.add(t);
                    }
                }
            }
        }
        return new ArrayList<>(found);
    }
}

TIME O(N³)SPACE O(N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED