Problem Description

You are given an integer array nums. Your task is to find all unique triplets in the array where three numbers add up to zero.

Specifically, you need to return all triplets [nums[i], nums[j], nums[k]] that satisfy these conditions:

• The three indices must be different: i != j, i != k, and j != k
• The sum equals zero: nums[i] + nums[j] + nums[k] == 0
• The solution set must not contain duplicate triplets (even if the same values appear multiple times in the array)

For example, if nums = [-1, 0, 1, 2, -1, -4], the output would be [[-1, -1, 2], [-1, 0, 1]]. Notice that even though -1 appears twice in the array, we only include each unique triplet once in the result.

The key challenge is efficiently finding all such triplets while avoiding duplicates. The solution uses sorting combined with a two-pointer technique. After sorting the array, for each element nums[i], we use two pointers to find pairs in the remaining array that sum to -nums[i]. This reduces the problem from finding three numbers that sum to zero to finding two numbers that sum to a target value.

The algorithm carefully skips duplicate values during iteration to ensure the result contains only unique triplets. When nums[i] is positive, we can stop early since all remaining elements will also be positive (after sorting), making it impossible to achieve a sum of zero.

Intuition

The brute force approach would be to check all possible triplets using three nested loops, which would take O(n³) time. However, we can optimize this significantly by observing that once we fix one number, we're essentially looking for two other numbers that sum to the negative of the fixed number.

This insight transforms our problem: instead of finding three numbers that sum to zero, we can fix one number nums[i] and then find two numbers in the remaining array that sum to -nums[i]. This is essentially the classic Two Sum problem, which can be solved efficiently using two pointers on a sorted array.

Why does sorting help? When the array is sorted, we can use the two-pointer technique effectively. If the current sum is too small, we know we need a larger number, so we move the left pointer right. If the sum is too large, we need a smaller number, so we move the right pointer left. This way, we can find all valid pairs in linear time for each fixed element.

The duplicate handling becomes straightforward with a sorted array. Since identical elements are grouped together after sorting, we can easily skip duplicates by checking if the current element equals the previous one. For the first element nums[i], we skip it if it's the same as nums[i-1]. Similarly, after finding a valid triplet, we skip duplicate values for both pointers to avoid recording the same triplet multiple times.

An additional optimization comes from recognizing that if nums[i] > 0 in a sorted array, all elements to its right are also positive. Since we need three numbers to sum to zero, having all positive numbers makes this impossible, allowing us to terminate early.

This approach reduces the time complexity from O(n³) to O(n²) - we iterate through each element once (O(n)), and for each element, the two-pointer search takes O(n) time.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a systematic approach using sorting and two pointers:

Step 1: Sort the Array First, we sort the array in ascending order using nums.sort(). This enables us to use the two-pointer technique and makes duplicate handling straightforward.

Step 2: Iterate Through First Element We enumerate each element as the first element of a potential triplet. The loop runs from index 0 to n-2 (where n is the array length) because we need at least three elements for a valid triplet.

Step 3: Early Termination If nums[i] > 0, we break immediately. Since the array is sorted, all subsequent elements will also be positive, making it impossible to find three numbers that sum to zero.

Step 4: Skip Duplicates for First Element To avoid duplicate triplets, we check if i > 0 and nums[i] == nums[i-1]. If true, we skip this iteration using continue because we've already processed this value as the first element.

Step 5: Two-Pointer Search For each valid nums[i], we initialize two pointers:

• Left pointer j = i + 1 (starts right after the fixed element)
• Right pointer k = n - 1 (starts at the end of the array)

Step 6: Find Valid Triplets While j < k, we calculate the sum x = nums[i] + nums[j] + nums[k] and compare it with zero:

• If x < 0: The sum is too small, so we increment j to get a larger value
• If x > 0: The sum is too large, so we decrement k to get a smaller value
• If x == 0: We found a valid triplet! We add [nums[i], nums[j], nums[k]] to our answer list

Step 7: Handle Duplicates for Two Pointers After finding a valid triplet, we need to skip duplicate values for both pointers:

• Move j forward: j += 1, then continue incrementing while j < k and nums[j] == nums[j-1]
• Move k backward: k -= 1, then continue decrementing while j < k and nums[k] == nums[k+1]

This ensures we don't add the same triplet multiple times even when duplicate values exist in the array.

Step 8: Return Results After processing all possible first elements, we return the ans list containing all unique triplets.

The time complexity is O(n²): sorting takes O(n log n), and the main loop runs in O(n²) (outer loop O(n) × inner two-pointer search O(n)). The space complexity is O(1) if we don't count the output array, as we only use a constant amount of extra space for pointers.

Example Walkthrough

Let's walk through the algorithm with nums = [-1, 0, 1, 2, -1, -4].

Step 1: Sort the array After sorting: nums = [-4, -1, -1, 0, 1, 2]

Step 2-7: Iterate through each element as the first element

Iteration 1: i = 0, nums[i] = -4

• Not a duplicate (i = 0), not positive, so we proceed
• Set two pointers: j = 1 (nums[j] = -1), k = 5 (nums[k] = 2)
• Calculate sum: -4 + (-1) + 2 = -3 < 0
• Sum too small, move j right: j = 2 (nums[j] = -1)
• Calculate sum: -4 + (-1) + 2 = -3 < 0
• Sum too small, move j right: j = 3 (nums[j] = 0)
• Calculate sum: -4 + 0 + 2 = -2 < 0
• Sum too small, move j right: j = 4 (nums[j] = 1)
• Calculate sum: -4 + 1 + 2 = -1 < 0
• Sum too small, move j right: j = 5, but now j >= k, so stop

Iteration 2: i = 1, nums[i] = -1

• Not a duplicate (different from nums[0] = -4), not positive, so proceed
• Set two pointers: j = 2 (nums[j] = -1), k = 5 (nums[k] = 2)
• Calculate sum: -1 + (-1) + 2 = 0 ✓
• Found triplet! Add [-1, -1, 2] to answer
• Skip duplicates: j moves from 2 to 3 (nums[3] = 0, different from -1)
• k moves from 5 to 4 (nums[4] = 1, different from 2)
• Continue with j = 3, k = 4
• Calculate sum: -1 + 0 + 1 = 0 ✓
• Found triplet! Add [-1, 0, 1] to answer
• Skip duplicates: j moves from 3 to 4, but now j >= k, so stop

Iteration 3: i = 2, nums[i] = -1

• This is a duplicate (nums[2] = nums[1] = -1), so skip with continue

Iteration 4: i = 3, nums[i] = 0

• Not a duplicate, not positive, so proceed
• Set two pointers: j = 4 (nums[j] = 1), k = 5 (nums[k] = 2)
• Calculate sum: 0 + 1 + 2 = 3 > 0
• Sum too large, move k left: k = 4, but now j >= k, so stop

Iteration 5: i = 4, nums[i] = 1

• nums[i] > 0, so we break early (all remaining elements are positive)

Final Result: [[-1, -1, 2], [-1, 0, 1]]

The algorithm efficiently finds all unique triplets by:

1. Using sorting to enable the two-pointer technique
2. Skipping duplicate values at position i (like when i = 2)
3. Finding valid triplets using two pointers that converge
4. Skipping duplicate values at j and k after finding valid triplets
5. Terminating early when nums[i] > 0

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm sorts the array first, which takes O(n log n) time. Then it uses a fixed pointer i to iterate through the array from index 0 to n-2, which is O(n) iterations. For each fixed i, it uses two pointers j and k to traverse the remaining array with a two-pointer technique. In the worst case, the two pointers together traverse the remaining n-i-1 elements once, making it O(n) for each i. Therefore, the nested loop structure gives us O(n) × O(n) = O(n²). Since O(n²) dominates O(n log n), the overall time complexity is O(n²).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's built-in sort() method uses Timsort, which has a worst-case space complexity of O(n) but typically uses O(log n) space for the recursion stack in practice. The algorithm itself only uses a constant amount of extra space for variables like i, j, k, and x. The output array ans is not counted as part of the space complexity since it's the required output. Therefore, the space complexity is O(log n) where n is the length of the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Duplicate Handling After Finding a Valid Triplet

The Pitfall: A frequent mistake is forgetting to move both pointers after finding a valid triplet, or only moving one pointer. This causes an infinite loop because the same valid triplet keeps being found repeatedly.

Incorrect Code Example:

if current_sum == 0:
    result.append([nums[i], nums[left], nums[right]])
    # Forgot to move pointers! This creates an infinite loop
    # The while loop condition never changes

Correct Solution: Always move both pointers after finding a valid triplet, then skip duplicates:

if current_sum == 0:
    result.append([nums[i], nums[left], nums[right]])
    left += 1
    right -= 1
    # Then skip duplicates for both pointers
    while left < right and nums[left] == nums[left - 1]:
        left += 1
    while left < right and nums[right] == nums[right + 1]:
        right -= 1

2. Off-by-One Error in Duplicate Skipping Logic

The Pitfall: Using the wrong comparison indices when skipping duplicates, particularly comparing with the wrong neighboring element.

Incorrect Code Example:

# Wrong: comparing with nums[right - 1] instead of nums[right + 1]
while left < right and nums[right] == nums[right - 1]:
    right -= 1

This compares the current right pointer with the element we're moving toward, not the element we're moving away from. This can skip valid elements or fail to skip duplicates properly.

Correct Solution: After decrementing right, compare with nums[right + 1] (the value we just moved from):

while left < right and nums[right] == nums[right + 1]:
    right -= 1

3. Forgetting to Check Bounds Before Skipping Duplicates

The Pitfall: Not checking if pointers are still within valid bounds during duplicate skipping can cause index out of bounds errors.

Incorrect Code Example:

# Missing the left < right check in the while condition
while nums[left] == nums[left - 1]:  # Can cause index errors
    left += 1

Correct Solution: Always include bounds checking in the condition:

while left < right and nums[left] == nums[left - 1]:
    left += 1

4. Skipping Duplicates for the First Element Incorrectly

The Pitfall: Starting duplicate checking from index 0 instead of index 1, which would skip the first occurrence of each value entirely.

Incorrect Code Example:

for i in range(n - 2):
    if nums[i] == nums[i - 1]:  # Problem when i = 0, nums[-1] is accessed
        continue

Correct Solution: Add a condition to check i > 0 before comparing with the previous element:

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

5. Not Handling Edge Cases for Array Length

The Pitfall: Processing arrays with fewer than 3 elements without proper validation.

Incorrect Code Example:

def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    # Directly starting the loop without checking if n >= 3
    for i in range(n - 2):  # If n < 3, range could be negative or empty
        ...

Correct Solution: Either add an explicit check or ensure the loop range handles it naturally:

def threeSum(self, nums: List[int]) -> List[List[int]]:
    if len(nums) < 3:
        return []
    nums.sort()
    # Or just let range(n - 2) handle it naturally when n < 3