Skip to main content

15. 3Sum

mediumAsked at Broadcom

Find all unique triplets that sum to zero. Broadcom asks 3Sum to test whether you handle duplicate-elimination correctly inside a sorted search — a skill that carries over to deduplication logic in ARP table management and MAC learning tables in switching software.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Reported in Broadcom SWE mid-level onsite reports as a two-pointer problem following Two Sum discussion.
  • Blind (2025-12)— Broadcom infrastructure threads list 3Sum as a medium-difficulty must-prep problem for onsite rounds.

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. 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: After sorting: [-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: Only one unique triplet.

Approaches

1. Sort + two-pointer

Sort the array. Fix each element nums[i] as the anchor. Use a two-pointer (left=i+1, right=end) to find pairs that sum to -nums[i]. Skip duplicate values for both the anchor and the inner pointers.

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 anchor
    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, O(1) extra space. Optimal — the O(n²) lower bound comes from the need to examine all pairs for each anchor. The duplicate-skip logic is the critical correctness detail.

Broadcom-specific tips

Walk Broadcom interviewers through the duplicate-skip logic explicitly — it's the most common place candidates fail. Say: 'After finding a valid triplet, I advance both pointers and skip any repeated values to avoid duplicate results.' Broadcom also values you naming the time complexity after sorting: O(n log n) sort + O(n²) scan = O(n²) overall. Don't forget to early-exit when nums[i] > 0 — no three positive numbers can sum to zero.

Common mistakes

  • Forgetting to skip duplicate anchors (nums[i] === nums[i-1]) — produces duplicate triplets.
  • Skipping duplicates before pushing the triplet instead of after — misses valid results.
  • Not sorting first — the two-pointer approach requires a sorted array.
  • Breaking the inner while loop incorrectly — after skipping duplicates, still increment/decrement the pointer once more.

Follow-up questions

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

  • 3Sum Closest (LC 16) — find the triplet whose sum is closest to a target.
  • 4Sum (LC 18) — generalise with an additional fixed pointer.
  • How would you handle this if the array doesn't fit in memory (external sort)?

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 sort first instead of using a hash set?

Sorting enables the two-pointer technique and makes duplicate elimination trivial by comparing adjacent elements. A hash-set approach requires complex deduplication logic.

What is the optimal time complexity?

O(n²) is optimal under comparison-based models — you need at least one pair check per anchor element.

Can I early-exit when nums[i] > 0?

Yes — the array is sorted, so if the smallest unfixed element is positive, no triplet can sum to zero. This is a good optimisation to mention.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →