35. 3Sum

mediumAsked at Datadog

Find 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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

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

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

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →