FAANGPrep Sprint

3-Sum

Find every group of three values, taken from different positions in the integer array nums, that adds up to 0, listing each distinct triplet once.

Examples

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

Output:[[-1,-1,2],[-1,0,1]]

Explain:

Two different triplets reach 0: [-1,0,1] and [-1,-1,2]. They may come back in any order, and so may the numbers inside each one.

Input:nums = [0,1,1]

Output:[]

Explain:

With exactly three numbers there is one triplet to try, and its sum is 2, not 0.

Input:nums = [0,0,0]

Output:[[0,0,0]]

Explain:

The only possible triplet sums to 0.

Problem Understanding

The goal is to find all unique triplets that sum to zero. It's essentially an extension of the Two Sum problem.

Key Constraint: The solution set must not contain duplicate triplets. This implies we need to be careful about how we select numbers.

We can fix one number, say nums[i]. Then the problem becomes finding two other numbers in the rest of the array that sum to -nums[i].

Since we want to avoid duplicates and use the Two Pointer technique efficiently, our first step is to sort the array.

Algorithm:

Sort the array.
Iterate through the array with index i.
For each i, run the Two Sum (Sorted) logic on the remaining part of the array (i+1 to end) with target = -nums[i].

TRIPLETS SUMMING TO 0

SORT

-4

-1

Fixed

—

Sum

—

Found

result

No triplet yet

Sort: [-4, -1, -1, 0, 1, 2]. Equal values are now neighbours, which is what lets duplicates be skipped

Fix nums[0] = -4: look for two values after it summing to 4

Array

Sorted before the scan, as the code does

The figure fixes i and moves the L and R pointers to find pairs summing to -nums[i]; recorded triplets collect beside it.