15. 3Sum

Q: Why must we sort first?

Sorting lets us use two pointers to scan the remaining subarray in O(n) per fixed element, instead of O(n²) for a nested loop. It also makes duplicate skipping straightforward.

Q: Can I use a hash set instead of two pointers?

Yes — for each pair (i,j), check if -nums[i]-nums[j] is in a set. It's O(n²) time and O(n) space with more complex de-duplication. The two-pointer approach is cleaner.

Q: What is the minimum possible time complexity for this problem?

O(n²) — you must consider every pair at minimum, and any pair-output requires at least O(n²) work in the worst case.

mediumAsked at Hugging Face

Find all unique triplets in an array that sum to zero. Hugging Face uses 3Sum to test whether candidates can extend two-pointer reasoning — a skill that maps directly to efficiently scanning attention weight triplets or ranking triple-wise loss computations in metric-learning models.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

Glassdoor (2026-Q1)— Multiple Hugging Face SWE onsite reports cite 3Sum as a medium-round problem testing two-pointer and de-duplication skills.
Blind (2025-11)— Hugging Face interview threads highlight 3Sum as a common pivot question after Two Sum.

Problem

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.

Constraints

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

Examples

Example 1

Input

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

Output

[[-1,-1,2],[-1,0,1]]

Explanation: Sort first: [-4,-1,-1,0,1,2]. Fix -1 at index 1, two-pointer finds (-1,2) and (0,1).

Example 2

Input

nums = [0,1,1]

Output

[]

Explanation: No triplet sums to zero.

Example 3

Input

nums = [0,0,0]

Output

[[0,0,0]]

Explanation: One unique triplet.

Approaches

1. Sort + two pointers

Sort the array. For each index i, use a two-pointer search on the remaining subarray to find pairs summing to -nums[i]. Skip duplicates at each level.

Time: O(n²)
Space: O(1) excluding output

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate i
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++; right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

Tradeoff: O(n²) time — optimal for this problem. O(log n) space for the sort. The de-duplication skips are the tricky part; always trace through an example with repeated elements.

Hugging Face-specific tips

Hugging Face interviewers will probe your de-duplication logic: 'Walk me through what happens when nums has three -1s.' Explain each skip condition individually. Connect the sorted two-pointer pattern to its ML analog: 'In triplet loss training, you fix an anchor embedding and use a sorted similarity score list to efficiently find hard positives and hard negatives — the same O(n) scan on a pre-sorted array.' This shows you can reason about algorithmic patterns across domains.

Common mistakes

Forgetting to skip duplicates for the outer loop (i) — produces duplicate triplets in the output.
Skipping duplicates for left and right BEFORE advancing the pointers — skip after recording the triplet and then advance.
Not sorting first — the two-pointer approach requires sorted order.
Using a Set of stringified arrays to de-duplicate instead of the skip conditions — correct but slower and messier.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

4Sum (LC 18) — add one more pointer; same pattern, one more outer loop.
3Sum Closest (LC 16) — find the triplet whose sum is closest to a target.
How would you scale this to find all zero-sum triplets in a dataset of 10^8 values distributed across multiple machines?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why must we sort first?

Sorting lets us use two pointers to scan the remaining subarray in O(n) per fixed element, instead of O(n²) for a nested loop. It also makes duplicate skipping straightforward.

Can I use a hash set instead of two pointers?

Yes — for each pair (i,j), check if -nums[i]-nums[j] is in a set. It's O(n²) time and O(n) space with more complex de-duplication. The two-pointer approach is cleaner.

What is the minimum possible time complexity for this problem?

O(n²) — you must consider every pair at minimum, and any pair-output requires at least O(n²) work in the worst case.

Practice these live with InterviewChamp.AI

Drill 3Sum and other Hugging Face interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →