Problem Statement

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that:

  • nums[i] + nums[j] + nums[k] == 0
  • i, j, and k are distinct indices.
  • The result should not contain duplicate triplets.

Example

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

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

Approach 1: Brute Force

Intuition

The most straightforward approach is to try every possible combination of three numbers and check whether their sum equals zero.

Since every triplet is examined, we’ll definitely find all valid answers.

However, duplicate triplets can appear because the same values may exist at different indices. To eliminate duplicates, we can store the triplets inside a set.

Algorithm

  1. Sort the array.
  2. Use three nested loops to generate every triplet.
  3. If the sum equals zero:
    • Convert the triplet to a tuple.
    • Store it in a set.
  4. Convert the set back into a list.

Code

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = set()
        nums.sort()

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        res.add((nums[i], nums[j], nums[k]))

        return [list(i) for i in res]

Complexity Analysis

  • Time Complexity: O(n³)
  • Space Complexity: O(k)
    • where k is the number of unique triplets stored in the set.

Why is this slow?

For an array of length n, we’re checking:

n × n × n

possible combinations.

With n = 1000, this results in roughly:

1000³ = 1,000,000,000

checks, which is far too slow.

Optimized Approach: Sorting + Two Pointers

The brute force solution repeatedly searches for the third number.

Can we do better?

Yes.

After sorting the array, we can fix one number and use the Two Pointer technique to efficiently find the remaining two numbers.

Key Observation

After sorting:

[-4, -1, -1, 0, 1, 2]

Suppose we fix:

a = -1

Now we need two numbers whose sum equals:

1

Instead of checking every pair, we place two pointers:

l = i + 1
r = end

Then calculate:

sum = a + nums[l] + nums[r]

There are only three possibilities.

Case 1

If

sum < 0

we need a larger number.

Move the left pointer:

l += 1

Case 2

If

sum > 0

the sum is too large.

Move the right pointer:

r -= 1

Case 3

If

sum == 0

We’ve found a valid triplet.

Store it, then move both pointers inward.

Handling Duplicates

Duplicates are the trickiest part of this problem.

Duplicate first element

Suppose the array is

[-1, -1, -1, 0, 1]

If we start from every -1, we’ll generate identical triplets multiple times.

So we skip repeated starting elements:

if i > 0 and nums[i] == nums[i - 1]:
    continue

Duplicate left pointer

After finding a valid triplet:

l += 1
r -= 1

the next value on the left could still be identical.

Example:

[-2,0,0,0,2]

Without skipping duplicates we’d produce:

[-2,0,2]
[-2,0,2]
[-2,0,2]

So we skip duplicate values:

while l < r and nums[l] == nums[l - 1]:
    l += 1

This guarantees every triplet is unique.

Early Stopping

Because the array is sorted, once the fixed number becomes positive:

if a > 0:
    break

there is no point continuing.

Why?

Every remaining number is also positive, so the sum can never become zero.

This small optimization avoids unnecessary work.

Code

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):

            if a > 0:
                break

            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1

            while l < r:
                threesum = a + nums[l] + nums[r]

                if threesum > 0:
                    r -= 1

                elif threesum < 0:
                    l += 1

                else:
                    res.append([a, nums[l], nums[r]])

                    l += 1
                    r -= 1

                    while l < r and nums[l] == nums[l - 1]:
                        l += 1

        return res

Complexity Analysis

Time Complexity

Sorting:

O(n log n)

For every element, the two pointers scan the remaining array only once:

O(n)

Overall:

O(n²)

Space Complexity

O(1)

Ignoring the output array, we only use a few pointers and variables.

Final Thoughts

The key insight is realizing that after sorting the array, we don’t need three nested loops anymore.

Instead:

  • Fix one number.
  • Use two pointers to search for the other two.
  • Skip duplicates carefully.
  • Stop early once the fixed number becomes positive.

This reduces the solution from O(n³) to O(n²), making it efficient enough for the problem constraints and a common pattern that appears in many interview questions.