Coding interview problems › Two Pointers

↔️ Two Pointers Medium

3Sum

3Sum explained: sort, fix one number, then two-pointer the rest to find all unique zero-sum triplets in O(n²). Duplicate handling, tested Python, live visual.

Also searched as: three sum problem · find triplets that sum to zero · 3sum two pointers

↔️

Try it live Free

Two Pointers

Watch two pointers sweep one range in O(n). 3Sum runs that same sweep once for every fixed first number, which is why it is O(n²) instead of O(n³).

Also useful: Hash Tables

Open the playground →

The problem

Given a list of integers, return every unique triplet of values [a, b, c] taken from three different positions such that a + b + c = 0. The answer must not contain the same triplet twice.

Inputnums = [-1, 0, 1, 2, -1, -4]
Output[[-1, -1, 2], [-1, 0, 1]]
Inputnums = [0, 0, 0, 0]
Output[[0, 0, 0]]

Only one unique triplet despite many index choices.

The key insight

Sort the list. Fix the first number a = nums[i]; now you need two numbers to the right that sum to -a, which is Two Sum II on a sorted range, solved with two pointers in O(n). Sorting also makes duplicates sit next to each other, so you can skip them and never output the same triplet twice.

Brute force first: Trying all triples is O(n³), and you still need a set to remove duplicates.

Step-by-step approach

  1. Sort nums.
  2. For each index i, skip it if nums[i] == nums[i-1] (same first number as before). Stop early if nums[i] > 0.
  3. Set lo = i + 1, hi = n - 1 and move them like Two Sum II looking for sum 0.
  4. On a match, record the triplet, then move lo past equal values and hi past equal values.
  5. Return all recorded triplets.

Python solution

PYTHON 3tested
def three_sum(nums):
    nums = sorted(nums)
    n, res = len(nums), []
    for i in range(n - 2):
        if nums[i] > 0:
            break                          # smallest is positive: no more zeros
        if i > 0 and nums[i] == nums[i - 1]:
            continue                       # same first value already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1                # skip duplicate second values
    return res

Complexity

TimeO(n²)
SpaceO(1) extra (besides sorting and output)

Sorting is O(n log n), then for each of n first elements the two-pointer scan is O(n). The skip loops do not add work because pointers still only move inward.

Common mistakes

Frequently asked questions

What is the time and space complexity of 3Sum?

O(n²) time: O(n log n) to sort plus an O(n) two-pointer scan for each of n starting elements. Extra space is O(1) apart from the sort and the output.

Can 3Sum be done faster than O(n²)?

For general integers no meaningfully faster algorithm is expected in interviews. O(n²) with sorting and two pointers is the standard answer.

How do I solve 3Sum Closest?

Use the same sort plus two-pointer loop, but track the sum with the smallest absolute difference from the target instead of collecting exact matches.

Can I use a hash set instead of two pointers?

Yes, fixing i and using a set for the two-sum part is also O(n²), but deduplication becomes messier than with the sorted two-pointer version.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Two Pointers Two Pointers lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.