15. 3Sum
mediumAsked at ElasticFind 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 Sam K., 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
nums = [-1,0,1,2,-1,-4][[-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
nums = [0,1,1][]Explanation: No triplet sums to zero.
Example 3
nums = [0,0,0][[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.
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.