Skip to main content

15. 3Sum

mediumAsked at Cohere

Find all unique triplets in an array that sum to zero. Cohere asks this to test systematic duplicate-elimination alongside the two-pointer technique — skills that transfer directly to deduplicating retrieved document clusters in a RAG pipeline.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Multiple Cohere onsite reports list 3Sum as a medium-level staple for SWE and MLE roles.
  • Blind (2025-12)— Cohere candidates identify 3Sum as a high-signal medium problem tested in virtual onsites.

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: Two unique triplets sum to zero.

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: Single triplet of all zeros.

Approaches

1. Sort + two pointers

Sort the array. Fix one element at index i, then use two pointers (left=i+1, right=end) to find pairs that sum to -nums[i]. Skip duplicates carefully at each level.

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 (nums[i] > 0) break; // sorted — no point continuing
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip dup i
    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 after O(n log n) sort, O(1) extra space. The canonical approach — duplicate skipping is the subtlest part and where most bugs arise.

Cohere-specific tips

Cohere interviewers pay close attention to duplicate-skipping logic. Walk through the skip conditions verbally before coding: 'After finding a valid triplet I advance both pointers past duplicates before incrementing once more.' Also mention that sorting is acceptable here but not always — if the input were a stream of embeddings you would need a hash-set approach instead. That awareness of trade-offs between sorted and hash-based deduplication resonates with retrieval-focused teams.

Common mistakes

  • Skipping duplicates for i but not for left/right after finding a triplet — produces duplicate triplets.
  • Not breaking early when nums[i] > 0 — all subsequent sums are positive, so no valid triplet exists.
  • Using a set of arrays to deduplicate — JS does not deeply compare arrays, so Set<number[]> does not work correctly.
  • Off-by-one in the loop bound — iterate only to nums.length - 2 to leave room for left and right.

Follow-up questions

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

  • 3Sum Closest — find the triplet whose sum is closest to a target.
  • 4Sum — generalise with an outer two-pointer loop; O(n³).
  • How would you find all unique triplets in a stream of integers without sorting?

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 allows two-pointer convergence and makes duplicate detection trivial via adjacent comparison. Without sorting you need an O(n) hash set per fixed element.

Why skip when nums[i] === nums[i-1] rather than nums[i] === nums[i+1]?

Comparing to the previous value skips duplicates after the first occurrence is processed. Comparing to the next would skip before processing the first — missing valid triplets.

Can this be done in O(n) time?

No known algorithm achieves O(n) for 3Sum. The O(n²) bound is believed to be optimal under common computational models.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →