3Sum

Mediumtwo pointersAmazonMetaGoogleBloomberg

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Examples

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

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

Explanation:nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].

Input:nums = [0,1,1]

Output:[]

Explanation:The only possible triplet does not sum up to 0.

Input:nums = [0,0,0]

Output:[[0,0,0]]

Explanation:The only possible triplet sums up to 0.

Constraints

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

💡 Hints

Hint 1

Sort the array first.

Hint 2

Fix one number and use Two Pointers for the remaining two.

Hint 3

Skip duplicate values to avoid duplicate triplets.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Quadratic

Algorithmic Approach

Sort the array. Fix one element, then use two pointers to find pairs that sum to -nums[i]. Skip duplicates at all three levels.

Time ComplexityO(n²)

Why:

Sorting takes O(n log n). For each fixed element i, the two-pointer scan over the remaining sub-array takes O(n), yielding O(n²) total time.

Space ComplexityO(1)

Why:

Auxiliary space is O(1) beyond pointers (excluding the output array and sorting space).

Big-O Growth CurveQuadratic (O(N²))

Execution time grows quadratically with nested iterations over the input.

🌍 Real-World Use Cases

FinanceNeutral portfolio construction

Finding combinations of long/short positions that net to zero exposure — the same 3Sum logic on sorted asset weights.

🔍 Dry Run

Solution⏱ O(n²) | 💾 O(1)

-4

-1

Line3

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

Sort: [-1,0,1,2,-1,-4] → [-4,-1,-1,0,1,2]