Skip to main content

15. 3Sum

mediumAsked at Elastic

Find all unique triplets in an array that sum to zero. Elastic uses this to assess whether candidates can combine sorting and two-pointer techniques without double-counting — the same deduplication challenge that arises when Elasticsearch merges results from replicated shards.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2026-Q1)— Elastic onsite candidates report 3Sum or variants appearing in the algorithms round, often with deduplication emphasis.
  • Blind (2025-11)— Elastic SWE threads identify 3Sum as a mid-difficulty filter that separates hash-map-only candidates from those comfortable with two-pointer on sorted arrays.

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 -1 (index 1), two-pointer finds [-1,0,1]. Fix -1 (index 2), two-pointer finds [-1,-1,2] but we skip duplicate -1 as anchor.

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 valid triplet.

Approaches

1. Sort + two pointers

Sort the array. Fix a left anchor i and use two pointers (left = i+1, right = n-1) to find pairs summing to -nums[i]. Skip duplicate anchors and duplicate pointer values to ensure unique triplets.

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) auxiliary space. The canonical solution. The deduplication skips are the tricky part — walk through examples carefully.

Elastic-specific tips

Elastic interviewers focus on the deduplication logic — articulate it before coding: 'After sorting, I skip duplicate anchors to avoid processing the same starting value twice. After finding a valid triplet, I skip duplicate left and right values before advancing both pointers.' Mention that sorting once upfront for O(n²) beats a Set-based approach for large n due to better cache locality — this kind of constant-factor awareness resonates at Elastic.

Common mistakes

  • Not sorting the array first — two-pointer correctness depends on sorted order.
  • Skipping duplicate anchors with the wrong condition: use i > 0 && nums[i] === nums[i-1], not i >= 0.
  • Forgetting to skip duplicates on both left and right pointers after recording a result.
  • Breaking instead of continuing when nums[i] > 0 — once the anchor is positive, no three numbers can sum to zero, so you can break early.

Follow-up questions

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

  • 3Sum Closest (LC 16) — find the triplet whose sum is closest to a target.
  • 4Sum (LC 18) — extend to four numbers with an additional outer loop.
  • How would you find unique triplets in a stream where you cannot sort upfront?

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 lets two pointers converge correctly in O(n) per anchor. Without sorting, you need a hash set per inner pair, which is O(n²) with worse constants.

Can I use a Set instead of deduplication skips?

Yes, but inserting stringified triplets into a Set adds constant overhead and makes the deduplication logic implicit. Explicit skips are faster and clearer in an interview setting.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →