Skip to main content

17. 3Sum

mediumAsked at SoFi

Find all unique triplets that sum to zero — SoFi uses this as a litmus test for de-duplication mechanics that appear in trade-allocation reconciliation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Constraints

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

Examples

Example 1

Input
[-1,0,1,2,-1,-4]
Output
[[-1,-1,2],[-1,0,1]]

Example 2

Input
[0,1,1]
Output
[]

Approaches

1. Brute force triples

Three nested loops with a Set for de-dup, sort each triple.

Time
O(n^3)
Space
O(n)
function threeSum(nums) {
  const set = new Set();
  for (let i = 0; i < nums.length; i++)
    for (let j = i+1; j < nums.length; j++)
      for (let k = j+1; k < nums.length; k++)
        if (nums[i]+nums[j]+nums[k] === 0)
          set.add([nums[i],nums[j],nums[k]].sort((a,b)=>a-b).join(','));
  return [...set].map(s => s.split(',').map(Number));
}

Tradeoff:

2. Sort + two pointers

Sort the array, fix the first element, and use two pointers from both ends to find pairs that sum to the negative of the first. Skip duplicates as you go.

Time
O(n^2)
Space
O(1)
function threeSum(nums) {
  nums.sort((a,b)=>a-b);
  const res = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue;
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const s = nums[i] + nums[l] + nums[r];
      if (s === 0) {
        res.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l+1]) l++;
        while (l < r && nums[r] === nums[r-1]) r--;
        l++; r--;
      } else if (s < 0) l++;
      else r--;
    }
  }
  return res;
}

Tradeoff:

SoFi-specific tips

SoFi rewards explicit dedup logic — duplicate-trade detection in a brokerage clearing pipeline uses the same sort-and-skip pattern to drop repeated trade IDs without false negatives.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →