Skip to main content

15. 3Sum

mediumAsked at Gusto

Find all unique triplets in the array that sum to zero. Gusto asks this to push beyond Two Sum — they want to see you sort first, lock one element, then use two pointers on the remainder while carefully skipping duplicates.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2026-Q1)— Cited in Gusto mid-level SWE onsite reports as a problem that surfaces after Two Sum to test duplicate handling and two-pointer technique.
  • Blind (2025-12)— Multiple Gusto interview threads list 3Sum as a high-frequency medium problem, particularly for senior roles.

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. 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: Both triplets sum to 0. Each appears once despite duplicate −1 values in the input.

Example 2

Input
nums = [0, 1, 1]
Output
[]

Explanation: No triplet sums to 0.

Example 3

Input
nums = [0, 0, 0]
Output
[[0,0,0]]

Explanation: One unique triplet: all zeroes.

Approaches

1. Sort + two pointers

Sort the array. Fix element i, then use left and right pointers to find pairs that sum to −nums[i]. Skip duplicate values for i, left, and right to avoid duplicate 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++) {
    // skip duplicate values for the fixed element
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // early exit: smallest possible triplet already > 0
    if (nums[i] > 0) break;
    let left = i + 1;
    let 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]]);
        // skip duplicates for both pointers
        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 an O(n log n) sort, O(1) extra space. Optimal for this problem. The duplicate-skipping logic is the tricky part — articulate it clearly before coding.

Gusto-specific tips

Gusto interviewers want to hear the strategy before the code: '1) Sort. 2) Fix i. 3) Two-pointer on the remainder. 4) Skip duplicates at each pointer.' The duplicate-skip logic trips most candidates — explain it as: after finding a valid triplet, advance both pointers past any repeated values. Also mention the early-break optimisation when nums[i] > 0, which shows awareness of the sorted property.

Common mistakes

  • Forgetting to sort first — the two-pointer approach only works on a sorted array.
  • Skipping duplicates for i but not for left/right — produces duplicate triplets in the output.
  • Checking if nums[left] === nums[left+1] after incrementing left — should be done before the final left++/right-- advancement.
  • Using a Set of stringified arrays to deduplicate instead of the pointer-skipping approach — works but is less efficient and less clean.

Follow-up questions

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

  • 4Sum (LC 18) — add one more fixed element, reducing to 3Sum.
  • 3Sum Closest (LC 16) — return the triplet with sum closest to target.
  • How would you test this for arrays with many duplicates (e.g., [0,0,0,0,0])?

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 the array first?

Sorting lets you use two pointers to find pairs in O(n) instead of O(n²), and makes duplicate-skipping straightforward by placing equal values adjacent.

Why break when nums[i] > 0?

The array is sorted, so nums[i] > 0 means all elements to the right are also positive. No three positive numbers can sum to 0.

What is the time complexity lower bound for this problem?

O(n²) in the worst case — you may have O(n²) valid triplets to output, so you can't do better than that.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →