20. 3Sum

Q: Why sort first?

Sorting lets two pointers deterministically converge: if the sum is too small, advance left to a larger value; if too large, retreat right to a smaller value. Without sorting, you cannot make this greedy choice.

Q: Why check `nums[i] === nums[i-1]` instead of `nums[i] === nums[i+1]`?

You want to skip all but the FIRST occurrence of a duplicate value in the outer loop. Comparing to the previous element ensures the first occurrence is processed and subsequent ones are skipped.

mediumAsked at PayPal

Find all unique triplets in an array that sum to zero. PayPal frequently asks this to test duplicate-skipping discipline and two-pointer mastery — skills that map to deduplication in reconciliation engines that match debits and credits across accounts.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in PayPal loops.

Glassdoor (2026)— PayPal SWE III reported 3Sum as the primary medium question in their final-round coding interview
Blind (2025)— PayPal interview loop thread cited 3Sum as the most common two-pointer problem asked

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i, j, and k are distinct indices and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Constraints

3 <= nums.length <= 3000
-100000 <= nums[i] <= 100000

Examples

Example 1

Input

nums = [-1,0,1,2,-1,-4]

Output

[[-1,-1,2],[-1,0,1]]

Explanation: Two unique triplets sum to 0

Example 2

Input

nums = [0,0,0]

Output

[[0,0,0]]

Approaches

1. Brute force with hash set deduplication

Three nested loops to check all triplets; use a Set to deduplicate sorted triplets.

Time: O(n^3)
Space: O(n)

function threeSum(nums) {
  const res = new Set();
  for (let i = 0; i < nums.length - 2; i++)
    for (let j = i+1; j < nums.length - 1; j++)
      for (let k = j+1; k < nums.length; k++)
        if (nums[i]+nums[j]+nums[k] === 0)
          res.add(JSON.stringify([nums[i],nums[j],nums[k]].sort((a,b)=>a-b)));
  return [...res].map(JSON.parse);
}

Tradeoff: O(n^3) — too slow for n=3000; mention briefly, then show sort + two-pointer.

2. Sort + two-pointer with duplicate skipping

Sort the array, then fix one element at a time with an outer loop and use two pointers to find complementary pairs in O(n). Skip duplicate values at every pointer position to avoid redundant triplets without needing a Set.

Time: O(n^2)
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 first element
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // Early exit: smallest possible sum > 0
    if (nums[i] > 0) break;

    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]]);
        // Skip duplicates for left and 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: The duplicate-skipping lines are the most error-prone part — practice them cold. At PayPal, describe this as a three-way ledger balance check: one debit fixed, scanning for two credits that net to zero.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

Forgetting to skip duplicates after finding a valid triplet — causes duplicate results even with sorted input
Skipping duplicates with `nums[i] === nums[i+1]` (forward check) instead of `nums[i] === nums[i-1]` (backward check) — causes the first occurrence to be skipped
Not sorting the array before applying two pointers — two-pointer correctness depends on sorted order

Follow-up questions

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

4Sum — find all unique quadruplets summing to a target (LC 18)
3Sum Closest — find the triplet sum closest to a target (LC 16)
Count the number of triplets summing to zero without returning them (can you do it in O(n^2)?).

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 lets two pointers deterministically converge: if the sum is too small, advance left to a larger value; if too large, retreat right to a smaller value. Without sorting, you cannot make this greedy choice.

Why check `nums[i] === nums[i-1]` instead of `nums[i] === nums[i+1]`?

You want to skip all but the FIRST occurrence of a duplicate value in the outer loop. Comparing to the previous element ensures the first occurrence is processed and subsequent ones are skipped.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →