35. 3Sum
mediumAsked at DatadogFind all unique triplets that sum to zero. Datadog uses this as the cornerstone two-pointer + dedup question — the same pattern needed for finding triple-correlations in cross-metric anomaly detection.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Datadog loops.
- Glassdoor (2026-Q1)— Datadog onsite — focal point of mid-tier rounds.
- Blind (2025-12)— Recurring at Datadog NYC.
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]]Example 2
nums = [0,1,1][]Example 3
nums = [0,0,0][[0,0,0]]Approaches
1. Brute force three loops + dedup
Check every (i, j, k); dedup via sorted-tuple Set.
- Time
- O(n^3)
- Space
- O(n^3)
// Three nested loops with set-based dedup of sorted tuples.
// Always too slow at Datadog scale.Tradeoff: Cubic — fails on 3000-element inputs and signals you missed the sort+two-pointer pattern.
2. Sort + two-pointer with dedup (optimal)
Sort. For each i, use two pointers j, k to find pairs summing to -nums[i]. Skip duplicates at all three levels.
- Time
- O(n^2)
- Space
- O(1) extra (output O(k))
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;
if (i > 0 && nums[i] === nums[i - 1]) continue;
let j = i + 1, k = nums.length - 1;
while (j < k) {
const sum = nums[i] + nums[j] + nums[k];
if (sum === 0) {
out.push([nums[i], nums[j], nums[k]]);
while (j < k && nums[j] === nums[j + 1]) j++;
while (j < k && nums[k] === nums[k - 1]) k--;
j++; k--;
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
return out;
}Tradeoff: O(n^2) time, O(1) extra space. The dedup logic at three levels (outer i, inner j, inner k) is what Datadog grades on.
Datadog-specific tips
Datadog interviewers grade on the three dedup checks: skip i when nums[i] === nums[i-1]; after finding a triplet, advance j past duplicates AND k past duplicates. Forgetting any one produces duplicates. Articulate all three before coding.
Common mistakes
- Using a Set of sorted tuples as a hack for dedup — works but signals you didn't think through the sort+skip logic.
- Only skipping duplicates at i, not j or k — produces [a, b, c] and [a, b, c] when there are repeats of b or c.
- Forgetting the nums[i] > 0 early-exit — wastes work in the all-positive tail.
Follow-up questions
An interviewer at Datadog may pivot to one of these next:
- 3Sum Closest (LC 16) — find triplet closest to target.
- 4Sum (LC 18) — two outer loops + two pointers.
- k-Sum — generalized recursive structure.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why sort first?
Sorting enables two-pointer (monotonic sweep) and makes adjacent-duplicate skip trivial. Without sort, dedup requires a hashset, blowing memory.
Why skip duplicates AFTER finding a match (j and k)?
Otherwise the same triplet can be found multiple times when there are repeats in the array.