20. 3Sum
mediumAsked at PayPalFind 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 Sam K., Founder, InterviewChamp.AI · Last verified
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
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]Explanation: Two unique triplets sum to 0
Example 2
nums = [0,0,0][[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.
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.