PPractick

The problem

A chemistry simulator models particles with integer charges and wants every group of three particles whose charges cancel to zero, reported as sets of values with no repeats. Checking all triples is O(n³), and even with a hash set it's awkward to avoid listing the same triplet several times. The standard answer sorts first, fixes one value, and solves a two-pointer two-sum on the rest, skipping duplicate values at every level. The result is O(n²) with no duplicate triplets.

Example: [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]].

Function signature

vector<vector<int>> threeSum(vector<int> nums);  // unique triplets (as sorted value lists) summing to 0

Test cases

Input nums	Output	Explanation
[-1, 0, 1, 2, -1, -4]	[[-1, -1, 2], [-1, 0, 1]]	The two -1s produce each triplet only once
[0, 1, 1]	[]
[0, 0, 0]	[[0, 0, 0]]
[-2, 0, 0, 2, 2]	[[-2, 0, 2]]	Duplicates skipped on both pointers
[1, 2, -2, -1]	[]

(Confirm: triplets use three different indices; each distinct triplet of values appears once; output sorted.)

How interviewers phrase it

• "Find all unique triplets that sum to zero" (LeetCode 15).
• Variants: a target other than 0, "3Sum closest" (LeetCode 16), "count triplets with sum below target".

Clarifying questions to ask

1. Should duplicate triplets be excluded?
2. Values or indices in the output?
3. How large is n? (O(n²) is the expected complexity.)

Follow-ups to expect

1. "Why sort?"
2. "How do you avoid duplicate triplets?"
3. "Can you stop early?"
4. "What about the hash-set approach?"
5. "Complexity?"

Related questions

• Sort an array of 0's 1's and 2's Medium
• 4 Sum Medium
• Rearrange array elements by sign Medium
• Next Permutation Medium
• Merge Overlapping Subintervals Medium
• Merge two sorted arrays without extra space Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in