Skip to main content
DSA patterns

3Sum

mediumTwo pointers Must-doMetaAmazonUber

Problem statement

You are given an integer array nums. Find every group of three different positions i, j and k whose values add up to 0, and return each group of values as a triplet [nums[i], nums[j], nums[k]].

The same triplet of values should not appear twice in the answer, even if it can be built from different positions in the array — think of de-duplicating three metrics (say, a CPU delta, a memory delta and a network delta) that happen to cancel out to zero, where you only want to report each distinct combination once, not once per matching host.

Examples

Example 1

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

Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: -1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. Other sets of positions also add to zero, but they reuse the same three values as one of these two triplets, so they aren't counted again.

Example 2

Input: nums = [0, 0, 0]

Output: [[0, 0, 0]]

Explanation: The only possible triplet uses all three zeros, and it sums to zero.

Hints

Hint 1: Sorting the array first makes duplicate values sit next to each other, so they're easy to skip, and it opens the door to scanning with two pointers instead of nested loops.

Approach

Optimal: Two pointers

Intuition

Sorting turns "find two numbers matching a target" into something two fingers can do together: put one at the start of the remaining range and one at the end. If the pair sums too low, the left finger moves right (toward bigger numbers); if it sums too high, the right finger moves left (toward smaller numbers). Because the array is sorted, every move is guaranteed to get you closer, so neither finger ever needs to backtrack. That's what makes this faster in practice than the hash-set version — no extra set to build or hash, just index arithmetic.

Steps

  1. Sort nums.
  2. Loop i from the start up to (but not including) the last two positions, treating nums[i] as the fixed first number.
  3. Skip i if it repeats the previous value, and stop the whole loop once nums[i] > 0.
  4. Set left = i + 1 and right = n - 1.
  5. While left < right, look at total = nums[i] + nums[left] + nums[right].
    • If total < 0, move left right (needs a bigger number).
    • If total > 0, move right left (needs a smaller number).
    • If total == 0, record the triplet, move both pointers inward, and skip past any repeated values at the new left and right so the same triplet isn't recorded twice.

Dry run

nums = [-4, -1, -1, 0, 1, 2] (sorted), fixing i = 1 (nums[i] = -1), so left = 2, right = 5:

left right nums[left] nums[right] total action
2 5 -1 2 0 match (-1, -1, 2) → left=3, right=4
3 4 0 1 0 match (-1, 0, 1) → left=4, right=3, loop ends

Both example triplets are found in two steps once i is fixed on the first -1.

Edge cases: an array with fewer than 3 elements never enters the outer loop, so it returns an empty list; when every value is 0, the total == 0 branch fires once and the duplicate-skipping while loops immediately close the window, so [0, 0, 0] is reported exactly once.

Complexity

Time O(n²) - sorting costs O(n log n). Then, for each of the n choices of the fixed number, the two pointers walk toward each other, giving O(n) work per fixed number and O(n²) overall.

Space O(1) - extra, not counting the space the sort itself uses or the output — no hash set is needed once the array is sorted, only a constant number of pointers are needed.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n - 2):
            if nums[i] > 0:
                break
            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]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
        return result


if __name__ == "__main__":
    print(Solution().threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
    print(Solution().threeSum([0, 0, 0]))  # [[0, 0, 0]]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "find triplets/groups of numbers that sum to a target" in an unsorted array
  • Idea: sort first, then fix one number and use two pointers on the rest to find the other two
  • Cost: O(n²) time, O(1) extra space (not counting the sort or the output)
  • Trap: forgetting to skip repeated values for the fixed number *and* for both pointers — this is what causes duplicate triplets in the output

Interview follow-ups

  • What if the problem were 4Sum instead of 3Sum?

    Add one more level of fixed-number looping before falling back to the same two-pointer scan: fix nums[i], then fix nums[j] for j > i, then run the two-pointer walk on the remaining range to find pairs summing to target - nums[i] - nums[j]. This generalizes to k-sum by recursing down to a 2-pointer base case once only two numbers are left, at a cost of O(n^(k-1)) time for k-sum.

  • The array is too large to sort in memory — how would you find zero-sum triplets across a dataset that doesn't fit?

    Since the two-pointer approach depends on random access into a sorted array, an external merge sort (sorting on-disk chunks, then merging) would produce a sorted stream you can still scan with two pointers reading from disk or a memory-mapped file. Alternatively, if approximate results are acceptable, values could be bucketed by range across machines so that any triplet summing to zero is guaranteed to have its three values land in a small, related set of buckets, letting each bucket group be solved independently in memory.

Frequently asked questions

Sorting is what makes the two-pointer scan possible: once the array is ordered, moving the left pointer right always increases the sum and moving the right pointer left always decreases it, so you know exactly which direction to move without checking every pair. Sorting also puts equal values next to each other, which is what lets you skip duplicates with a simple neighbor check instead of a separate lookup structure.

The underlying pattern — combine three signals from a batch of readings to see which combinations cancel out or hit a target — shows up in capacity and cost reconciliation, such as finding three resource deltas (say, CPU, memory and network headroom changes across a migration) that sum to zero. It's also a standard way interviewers check whether a candidate can turn an O(n³) brute force into an O(n²) solution using sorting and two pointers, a skill that generalizes to a lot of "scan sorted data efficiently" tasks in infra tooling.

Almost nothing — replace every 0 in the two-pointer approach with k: fix nums[i], then look for two remaining numbers whose sum is k - nums[i] using the same left/right pointer walk. The sorting, the duplicate-skipping and the O(n²) time complexity all stay the same.

Each pointer can independently land on a repeated value from a previous match. Skipping only i would still let the same pair of left/right values be recorded twice when nums[i] is fixed; skipping only left/right would still let the same fixed number nums[i] be processed twice, doing the same inner work again. All three checks together are what keeps each distinct value-triplet in the output exactly once.