Skip to main content

15. 3Sum

mediumAsked at eBay

eBay's fraud detection team looks for triplets of transaction amounts that satisfy suspicious relationships — 3Sum is the algorithmic core. It's a medium-difficulty staple in eBay's onsite loop because it tests whether you can extend a known pattern (Two Sum) to handle duplicates and a sorted-array constraint cleanly.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Cited as a common eBay medium-difficulty problem in round 2 onsite interviews for SWE roles.
  • Blind (2025-11)— eBay SWE prep lists 3Sum as a high-probability interview question, especially for mid-level candidates.

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 −4: no pair sums to 4. Fix −1 (first): pair (−1, 2) works. Fix −1 (second): pair (0, 1) works. Skip duplicate −1 at outer loop.

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: The only unique triplet.

Approaches

1. Sort + Two Pointers

Sort the array. Fix the first element with an outer loop. Use two pointers (left, right) on the remaining suffix to find pairs summing to −nums[i]. Skip duplicates at each pointer 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 outer duplicate
    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++;  // skip inner dup
        while (left < right && nums[right] === nums[right - 1]) right--; // skip inner dup
        left++; right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

Tradeoff: O(n²) time — optimal for this problem. Sorting costs O(n log n) but that's dominated by the O(n²) loop. The duplicate-skipping logic is the key complexity that eBay interviewers probe.

eBay-specific tips

eBay interviewers specifically test the duplicate-skipping logic — candidates who get the two-pointer mechanics right but produce duplicate triplets fail silently. Explain the three skip points: outer loop (skip same i), left pointer (skip same left after recording), right pointer (skip same right after recording). Early exit: if nums[i] > 0, all elements to the right are positive so no triplet sums to 0; break the outer loop.

Common mistakes

  • Not skipping duplicate values at the outer loop (i > 0 && nums[i] === nums[i-1]) — causes duplicate triplets in output.
  • Skipping duplicates at the inner pointers before recording the triplet instead of after — misses valid results.
  • Moving both pointers after a match but forgetting to skip duplicates first — inserts duplicate triplets.
  • Not sorting first — the two-pointer technique requires a sorted array.

Follow-up questions

An interviewer at eBay may pivot to one of these next:

  • 3Sum Closest (LC 16) — find the triplet sum closest to a target instead of exactly zero.
  • 4Sum (LC 18) — fix two elements with nested loops, then apply two pointers; generalizes to k-Sum.
  • How would you handle this if the input stream is so large it doesn't fit in memory?

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 is O(n²) optimal and not O(n log n)?

The output alone can have O(n²) triplets (e.g., [-n,...,-1, 0, 1,...,n]), so you can't do better than O(n²) in the worst case.

Can I use a hash set instead of two pointers?

Yes — fix two elements with nested loops, compute the required third, and check a Set. Same O(n²) time but O(n) space and more complex duplicate handling. Two pointers is cleaner.

What early exits can speed up the algorithm?

If nums[i] > 0, no triplet sums to 0 (all remaining elements are positive). If nums[i] + nums[i+1] + nums[i+2] > 0, all remaining triplets are positive. If nums[i] + nums[n-2] + nums[n-1] < 0, this i can't contribute.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →