LeetCode 15 - 3Sum

The problem gives us an integer array nums, and we need to find every unique triplet of numbers whose sum is exactly 0. A triplet consists of three different indices: - i != j - i != k - j != k The values themselves may be equal, but the indices must be different.

leetcodemediumarraytwo-pointerssorting

LeetCode Problem 15

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting

Solution

LeetCode 15 - 3Sum

Problem Understanding

The problem gives us an integer array nums, and we need to find every unique triplet of numbers whose sum is exactly 0.

A triplet consists of three different indices:

  • i != j
  • i != k
  • j != k

The values themselves may be equal, but the indices must be different. For example, [0,0,0] is valid if the array contains at least three zeros.

The output should contain all distinct triplets. Two triplets are considered duplicates if they contain the same values, regardless of order. For example:

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

represent the same triplet and only one of them should appear in the final answer.

The constraints are important:

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

A length of 3000 immediately tells us that cubic algorithms are probably too slow. An O(n^3) solution would require up to:

$$3000^3 = 27,000,000,000$$

operations in the worst case, which is far beyond acceptable limits.

The problem also contains several tricky edge cases:

  • Arrays with many duplicate values
  • Arrays containing only zeros
  • Arrays with no valid triplets
  • Negative and positive values mixed together
  • Multiple different triplets sharing some numbers

A naive implementation often fails because duplicate handling becomes complicated. Preventing duplicate triplets is one of the core challenges of this problem.

Approaches

Brute Force Approach

The brute force solution checks every possible combination of three elements.

We can use three nested loops:

  • The first loop chooses the first element.
  • The second loop chooses the second element.
  • The third loop chooses the third element.

For every triplet, we compute the sum. If the sum equals zero, we add the triplet to the answer.

Since the output cannot contain duplicates, we also need a way to avoid repeated triplets. One common approach is:

  • Sort each valid triplet before storing it.
  • Insert the triplet into a set.

This guarantees correctness because every possible combination is checked.

The major issue is performance. Three nested loops produce O(n^3) time complexity, which is too slow for n = 3000.

Optimal Approach, Sorting + Two Pointers

The key insight is that sorting allows us to search for pairs efficiently.

Suppose we fix one number nums[i]. Then the problem becomes:

Find two numbers after index i whose sum equals -nums[i].

After sorting the array:

  • If the current sum is too small, we move the left pointer rightward to increase the sum.
  • If the current sum is too large, we move the right pointer leftward to decrease the sum.

This transforms the inner search from O(n) pair enumeration into an efficient two pointer scan.

Sorting also makes duplicate handling much easier because equal values become adjacent.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(k) Checks every triplet, too slow for large inputs
Optimal O(n^2) O(1) excluding output Uses sorting and two pointers to efficiently find pairs

Here, k represents the number of stored triplets.

Algorithm Walkthrough

Optimal Algorithm

  1. Sort the array.

Sorting is essential because the two pointer technique only works on ordered data. It also allows us to skip duplicates efficiently. 2. Iterate through the array using index i.

At each step, nums[i] becomes the first element of the triplet. 3. Skip duplicate values for i.

If nums[i] == nums[i - 1], we skip this iteration because we would generate the same triplets again. 4. Initialize two pointers.

  • left = i + 1
  • right = len(nums) - 1

These pointers search for the remaining two values. 5. Compute the current sum.

total = nums[i] + nums[left] + nums[right]
  1. If the sum is too small, move left rightward.

Since the array is sorted, increasing left increases the total sum. 7. If the sum is too large, move right leftward.

Since the array is sorted, decreasing right decreases the total sum. 8. If the sum equals zero, record the triplet.

Add:

[nums[i], nums[left], nums[right]]

to the answer. 9. Move both pointers inward.

After finding a valid triplet, we continue searching for more combinations. 10. Skip duplicate values for left and right.

This prevents repeated triplets from entering the result. 11. Continue until left >= right.

At that point, all possible pairs for the current i have been checked.

Why it works

After sorting, every movement of the pointers changes the sum in a predictable direction.

  • Moving left increases the sum.
  • Moving right decreases the sum.

This guarantees that every possible pair is examined exactly once for each fixed i.

Skipping duplicates works because equal values are adjacent in the sorted array. Once we process one occurrence, processing the next identical value would generate identical triplets.

Together, these properties ensure:

  • Every valid triplet is found.
  • No duplicate triplets are produced.
  • The algorithm runs in O(n^2) time.

Python Solution

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

        n = len(nums)

        for i in range(n - 2):
            # Skip duplicate first elements
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = 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

                    # Skip duplicate second elements
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1

                    # Skip duplicate third elements
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return result

The implementation begins by sorting the array. This enables both efficient searching and duplicate elimination.

The outer loop fixes the first number of the triplet. Before processing each value, we check whether it matches the previous element. If it does, we skip it because it would generate duplicate triplets.

The two pointers then search the remaining subarray.

When the current sum is:

  • Less than zero, we increase the sum by moving left
  • Greater than zero, we decrease the sum by moving right
  • Equal to zero, we record the triplet

After finding a valid triplet, both pointers move inward. Duplicate values are skipped immediately afterward so the same triplet cannot be added multiple times.

The algorithm naturally explores all valid combinations without revisiting unnecessary states.

Go Solution

package main

import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)

	result := [][]int{}
	n := len(nums)

	for i := 0; i < n-2; i++ {
		// Skip duplicate first elements
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		left := i + 1
		right := n - 1

		for left < right {
			total := nums[i] + nums[left] + nums[right]

			if total < 0 {
				left++
			} else if total > 0 {
				right--
			} else {
				result = append(result, []int{
					nums[i],
					nums[left],
					nums[right],
				})

				left++
				right--

				// Skip duplicate second elements
				for left < right && nums[left] == nums[left-1] {
					left++
				}

				// Skip duplicate third elements
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			}
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version.

Go slices are used to store triplets dynamically. The sort.Ints function sorts the array in ascending order.

Unlike Python, Go does not have built in dynamic list literals with automatic resizing semantics identical to Python lists, so triplets are appended using append.

Integer overflow is not a concern here because the constraints are well within Go's int range.

Returning an empty slice is acceptable when no triplets exist.

Worked Examples

Example 1

Input:

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

Step 1: Sort the array

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

Iteration Details

i nums[i] left right Triplet Sum Action
0 -4 1 5 [-4,-1,2] -3 Move left
0 -4 2 5 [-4,-1,2] -3 Move left
0 -4 3 5 [-4,0,2] -2 Move left
0 -4 4 5 [-4,1,2] -1 Move left
1 -1 2 5 [-1,-1,2] 0 Record triplet
1 -1 3 4 [-1,0,1] 0 Record triplet

Result:

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

The next -1 at index 2 is skipped because it would create duplicate triplets.

Example 2

Input:

[0,1,1]

Sorted array:

[0,1,1]
i left right Sum Action
0 1 2 2 Move right

No valid triplets exist.

Result:

[]

Example 3

Input:

[0,0,0]

Sorted array:

[0,0,0]
i left right Sum Action
0 1 2 0 Record triplet

Result:

[[0,0,0]]

After recording the triplet, duplicate skipping prevents additional identical results.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Outer loop runs n times, two pointers scan linearly
Space O(1) excluding output Only pointer variables are used

Sorting costs O(n log n), but the dominant part of the algorithm is the nested two pointer traversal, which takes O(n^2) time.

The algorithm uses constant auxiliary space because it only stores a few indices and temporary variables. The output list itself is not counted in auxiliary space complexity.

Test Cases

def normalize(result):
    return sorted(sorted(triplet) for triplet in result)

sol = Solution()

# Example 1
assert normalize(sol.threeSum([-1,0,1,2,-1,-4])) == \
       normalize([[-1,-1,2],[-1,0,1]])  # standard mixed case

# Example 2
assert normalize(sol.threeSum([0,1,1])) == \
       normalize([])  # no valid triplets

# Example 3
assert normalize(sol.threeSum([0,0,0])) == \
       normalize([[0,0,0]])  # all zeros

# Minimum valid length
assert normalize(sol.threeSum([-1,0,1])) == \
       normalize([[-1,0,1]])  # exactly one triplet

# Multiple duplicates
assert normalize(sol.threeSum([-2,0,0,2,2])) == \
       normalize([[-2,0,2]])  # duplicate handling

# No solution with negatives only
assert normalize(sol.threeSum([-5,-4,-3,-2])) == \
       normalize([])  # impossible to sum to zero

# No solution with positives only
assert normalize(sol.threeSum([1,2,3,4])) == \
       normalize([])  # impossible to sum to zero

# Multiple valid triplets
assert normalize(sol.threeSum([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6])) == \
       normalize([
           [-4,-2,6],
           [-4,0,4],
           [-4,1,3],
           [-4,2,2],
           [-2,-2,4],
           [-2,0,2]
       ])  # stress duplicate skipping

# Large duplicate block
assert normalize(sol.threeSum([0,0,0,0,0])) == \
       normalize([[0,0,0]])  # many identical zeros

# Mixed negatives and positives
assert normalize(sol.threeSum([-3,-1,0,1,2,-1,-4])) == \
       normalize([
           [-3,1,2],
           [-1,-1,2],
           [-1,0,1]
       ])  # multiple distinct solutions

Test Summary

Test Why
[-1,0,1,2,-1,-4] Standard example with duplicates
[0,1,1] No valid triplets
[0,0,0] Single valid triplet with identical values
[-1,0,1] Minimum valid array size
[-2,0,0,2,2] Duplicate elimination correctness
[-5,-4,-3,-2] All negative values
[1,2,3,4] All positive values
Large mixed duplicate case Stress tests pointer movement and duplicate skipping
[0,0,0,0,0] Repeated zeros
[-3,-1,0,1,2,-1,-4] Multiple distinct triplets

Edge Cases

Arrays Containing Many Duplicates

Duplicate handling is the most common source of bugs in this problem.

Consider:

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

Without careful skipping logic, the algorithm might produce:

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

multiple times.

The implementation avoids this in two places:

  • The outer loop skips duplicate starting elements.
  • The inner loop skips duplicate left and right values after recording a valid triplet.

Together, these checks guarantee uniqueness.

Arrays Consisting Entirely of Zeros

An input like:

[0,0,0,0]

contains many possible index combinations, but only one distinct triplet:

[0,0,0]

A naive implementation often inserts the same triplet repeatedly.

After recording the first valid triplet, the algorithm advances both pointers and skips all adjacent duplicate zeros, preventing repeated output.

Arrays With No Possible Triplets

Examples include:

[1,2,3,4]

or

[-5,-4,-3]

Since all numbers have the same sign, no three values can sum to zero.

The algorithm handles this naturally. The two pointer search eventually terminates without finding any valid sums, and the result remains empty.

Minimum Length Arrays

The smallest allowed input size is 3.

For example:

[-1,0,1]

The implementation still works correctly because:

  • The outer loop runs once.
  • The two pointers examine exactly one pair.
  • The valid triplet is returned.

No special case logic is required.