Skip to main content

15. 3Sum

mediumAsked at IBM

3Sum is IBM's two-pointer-on-sorted-array screener. The interviewer is grading whether you sort first to enable the two-pointer pattern, whether you skip duplicates cleanly at all three pointer positions, and whether you arrive at O(n^2) instead of the naive O(n^3).

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 onsite recurring problem (two-pointer track).
  • LeetCode (2026-Q1)— Top-20 IBM-tagged problem (medium tier).
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive.

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]]

Example 2

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

Example 3

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

Approaches

1. Brute force — all triples

Triple-nested loop; deduplicate via stringified-sorted-triple Set.

Time
O(n^3)
Space
O(n^3) worst case for the dedupe Set
function threeSumBrute(nums) {
  const seen = new Set();
  const out = [];
  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) {
          const triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = triple.join(',');
          if (!seen.has(key)) {
            seen.add(key);
            out.push(triple);
          }
        }
      }
    }
  }
  return out;
}

Tradeoff: Cubic time and O(n^3) extra space worst case. Times out at n=3000 (27 billion operations). Useful only to dismiss as the starting point.

2. Sort + two-pointer (optimal)

Sort. Fix each i; use left/right pointers to find pairs summing to -nums[i]. Skip duplicates at all three positions.

Time
O(n^2)
Space
O(1) extra (output not counted; in-place sort)
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const out = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break; // smallest is positive, no triplet sums to 0
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate first element
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        out.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 out;
}

Tradeoff: O(n^2) time, O(1) extra space. The duplicate-skip logic at all THREE pointer positions is the line that catches candidates. The early break (`nums[i] > 0`) saves a constant factor on inputs with many positives.

IBM-specific tips

IBM specifically tests the duplicate-skip discipline on this problem. Three duplicate skips are required: (1) skip duplicate i at the outer loop, (2) skip duplicate left after finding a match, (3) skip duplicate right after finding a match. Missing any one of these produces duplicate triplets in the output and fails the rubric. Always state aloud 'I need to skip duplicates at all three pointer positions' before coding.

Common mistakes

  • Forgetting to skip duplicate first-element values (`nums[i] === nums[i-1]`) — produces duplicate triplets.
  • Skipping duplicates BEFORE finding a match instead of AFTER — misses valid triplets where the pair starts equal but moves apart.
  • Using i > 0 for the dedupe check but starting i from 0 inside an `if` — off-by-one.
  • Forgetting to advance left and right after a match — infinite loop.
  • Sorting with the default lexicographic compare (without `(a, b) => a - b`) on integer arrays — produces wrong order for negative numbers.

Follow-up questions

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

  • 4Sum (LeetCode 18) — generalize the pattern.
  • 3Sum Closest (LeetCode 16) — find triplet closest to a target.
  • What if the input could be too large to fit in memory? (Stream-friendly variant not possible without random access.)
  • Count the number of distinct triples summing to 0 — same algorithm, return only the count.

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?

Sorting enables the two-pointer pattern that drops a factor of n from the search. With a sorted array, when sum < 0 you can only increase by moving left right; when sum > 0 you can only decrease by moving right left. This invariant is what makes O(n^2) possible.

Can I avoid the sort and use a hash map?

Yes — fix i, then use a hash map for the 2Sum-on-the-rest problem. But the dedupe logic becomes harder, and the worst-case complexity is the same. Sort-and-two-pointer is the canonical IBM answer because the dedupe is cleaner.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →