Skip to main content

14. 3Sum

mediumAsked at Swiggy

Find every unique triplet in the array that sums to zero.

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

Problem

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0 and the indices are distinct. The output 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]]

Example 2

Input
nums=[0,1,1]
Output
[]

Approaches

1. Brute triple loop

Try every triplet then dedup using a sorted-key set.

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

Tradeoff:

2. Sort plus two pointers

Sort the array. Fix one element, then use two pointers from each side to find pairs that complete the zero sum. Skip equal neighbors to avoid duplicate triplets.

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:

Swiggy-specific tips

Swiggy looks at the dedup logic — interviewers fail candidates who pass the test but skip the neighbor-skip lines because their dispatch matching needs zero duplicate offers.

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 Swiggy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →