Black Friday 50% off any plan, for life Ends Nov 30

Coding interview problems

3Sum

3Sum is Two Sum with a twist that breaks most first attempts: find every triplet that adds to zero, and never list the same one twice. Interviewers watch how you handle the duplicates, and whether you can say why the two pointers never skip an answer.

Nail the duplicate skips without a hint

Three weeks from now, they're the part you'll blank on. Write 3Sum yourself in the 14-day free trial, and the learning engine brings it back before you forget it.

14-day free trial. Cancel anytime with one click.

I have an account

The problem

You are given an array of integers nums. Return every triplet of values that adds up to zero, where the three values come from three different indices of nums. Return each triplet only once, even when a value appears at several indices and the triplet can be made more than one way. If no triplet adds up to zero, return an empty list.

The order of the result is checked. Write the three values of each triplet from smallest to largest, and list the triplets in ascending order: by first value, and by second value when the first values are equal.

Constraints

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Example

Input
nums = [3, -2, 1, 0, -1, 2, -1]
Output
[[-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]]

-1 appears twice, so [-2, -1, 3] and [-1, 0, 1] can each be built two ways, but each goes in the answer once.

  1. 0:003Sum
  2. 0:42The problem
  3. 1:02Brute force: every group
  4. 1:35Fix one, then Two Sum
  5. 3:03Walkthrough
  6. 4:45Why it's always right
  7. 5:18Complexity
  8. 5:59Code
  9. 7:23Follow-up: closest to a target
  10. 7:57Recap

How to solve it

Three nested loops check every group of three. That's O(n³), about 4.5 billion groups at the limit of 3,000 numbers, and you'd still need a set to drop the copies. Name it and its cost, then move to the faster idea.

Fix one number and the problem shrinks. If the first number is -2, the other two have to add up to 2, and that's Two Sum. So sort the array first. Then fix each number in turn and run two pointers on the numbers to its right: left just after it, right at the end. If the total is below zero, move left up to a bigger number. If it's above zero, move right down. If it's zero, record the triplet and move both.

Sorting is allowed here because you return values, not indices, and it lines copies up side by side. That gives you the two places to skip duplicates: when the next number to fix equals the one before it, skip it, because its triplets are already found; and after a match, move the pointers past copies of the values they just used.

3Sum([-2,-2,0,1,1,2])

The run starts on [-2,-2,0,1,1,2].

The pointers never jump over a triplet. When the total is too small, even the biggest remaining number can't rescue the number at left, so dropping it loses nothing. When it's too big, the number at right is too big even for the smallest remaining partner. Every triplet gets found, and the skips only pass over copies of ones already recorded.

This sorts the input in place, so sort a copy if the caller needs the original order. And if they ask for something faster, there's no known way to beat O(n²) by more than a log factor.

Python solution

from typing import List


class Solution:
    def three_sum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        n = len(nums)

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1

        return result

Time and space complexity

Time O(n²)
Sorting is O(n log n), then each fixed number gets one sweep of the two pointers.
Space O(n)
The sort can use up to O(n) extra space depending on the language. Beyond the output, the pointers need O(1).

Be ready for the next one

Walk into the coding round ready

Practice 1,500+ real interview questions, built by former Meta, X and LinkedIn engineers. 50,000+ engineers have prepared with Firecode.

14-day free trial. Cancel anytime with one click.

Built by former engineers at

I have an account
50,000+engineers preparing with Firecode
1500+real interview questions from top tech companies
14languages, from Python to Rust
FAANG+offers landed at Google, Meta, Netflix, and more
Google Meta Amazon Apple Microsoft Netflix OpenAI Anthropic Stripe Nvidia Airbnb Uber Coinbase DoorDash Spotify Shopify Snowflake Cloudflare Bloomberg Dropbox