MediumArrayTwo PointersSorting

3Sum

1 approach, code in every language

Given an integer array, find every group of three distinct positions whose values add up to zero. Each valid group is reported as a triplet of the actual numbers.

The collection you return must not contain the same triplet more than once, even if it can be formed from different index combinations. The order of the triplets in the output does not matter.

Example 1

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

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

Both triplets sum to zero, and duplicate arrangements of the same values are filtered out.

Example 2

Input: nums = [0, 0, 0, 0]

Output: [[0, 0, 0]]

The only combination adds to zero and is listed a single time despite the repeated zeros.

Constraints

3 ≤ nums.length ≤ 3 * 10^3
-10^5 ≤ nums[i] ≤ 10^5

Sort + Two Pointers

Sort the array, fix one element, then sweep the remaining range from both ends to find pairs that complete the triplet.

Loading animation…

Intuition

Once the values are sorted, a pair that sums to a needed target can be located by moving two pointers inward: if the running sum is too small we advance the left pointer to gain value, and if it is too large we pull the right pointer back to lose value. Fixing the first number turns the three-number search into many two-number searches, and sorting also makes it trivial to skip repeated values so no duplicate triplet is ever emitted.

Algorithm walkthrough

1Sort the array in ascending order so pointer movement predictably increases or decreases the sum.
2Iterate an index i as the first element, skipping it when it equals the previous element to avoid repeats.
3Set left = i + 1 and right = end, then compute the three-way sum at each step.
4If the sum is negative move left rightward, if positive move right leftward, and if zero record the triplet.
5After recording, advance both pointers past any equal neighbors to keep the results unique.

Implementation

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > 0:
                break
            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:
                    res.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 res

Time

O(n^2)

Space

O(1)

Sorting costs O(n log n); the nested pointer scan dominates at O(n^2). Extra space excludes the output list.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Charge Neutral Triples is our own problem on the technique behind 3Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free