Finding Triplets That Sum to Zero: A Deep Dive into threeSum

Hello everyone! Today, we're going to unravel a classic problem in computer science: finding all unique triplets in an array that sum up to zero. This is a common interview question and a great way to understand the power of sorting and the two-pointer technique. We'll be dissecting a Python implementation of the threeSum function and visualizing its steps.

Problem statement

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0. The solution set must not contain duplicate triplets.

Example:

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

• Output: [[-1, -1, 2], [-1, 0, 1]] (order of triplets and order within triplets may vary)

The threeSum function (Python)

Here is a common, clean, and efficient implementation that uses sorting + two-pointer approach:

def threeSum(nums):
    nums.sort()
    n = len(nums)
    result = []

    for i in range(n - 2):
        # If current value is greater than 0, we cannot find triplets summing to 0
        if nums[i] > 0:
            break

        # Skip duplicate values for the first element to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])

                # Move left and right to the next distinct elements
                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

            elif s < 0:
                left += 1
            else:
                right -= 1

    return result

Step-by-step breakdown

1. Sort the array

   • Sorting is crucial. It allows the two-pointer pattern and makes it easy to skip duplicates.

   • Time to sort: O(n log n).

2. Iterate over the array choosing the first element of the triplet

   • For index i from 0 to n-3, treat nums[i] as the first element.

   • If nums[i] > 0, break early — since the array is sorted, further elements are >= nums[i], so sums cannot be zero.

   • Skip duplicates for i (if nums[i] == nums[i - 1]) to avoid producing identical triplets multiple times.

3. Two-pointer search for the remaining two numbers

   • Set left = i + 1 and right = n - 1.

   • Compute sum s = nums[i] + nums[left] + nums[right].

     • If s == 0: you found a triplet — append it to results, then move left and right inward while skipping duplicates.

     • If s < 0: increase left to raise the sum.

     • If s > 0: decrease right to lower the sum.

4. Skip duplicates while moving pointers

   • After finding a valid triplet, you must skip over repeated values on both left and right sides to ensure uniqueness.

Complexity

• Time complexity: O(n^2)

  • Outer loop runs O(n) times; inner two-pointer scanning costs O(n) across each outer iteration.

• Space complexity: O(1) extra (excluding space for output)

  • Sorting may use O(n) extra depending on language, but algorithmic extra memory is constant.

Worked example (visualization)

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

1. Sort: [-4, -1, -1, 0, 1, 2]

2. i = 0 (nums[i] = -4)

   • left = 1 (-1), right = 5 (2) => sum = -3 -> left++

   • left = 2 (-1), right = 5 (2) => sum = -3 -> left++

   • left = 3 (0), right = 5 (2) => sum = -2 -> left++

   • left = 4 (1), right = 5 (2) => sum = -1 -> left++ -> left >= right, done

3. i = 1 (nums[i] = -1)

   • left = 2 (-1), right = 5 (2) => sum = 0 -> found [-1, -1, 2]

     • move left and right while skipping duplicates -> left = 3, right = 4

   • left = 3 (0), right = 4 (1) => sum = 0 -> found [-1, 0, 1]

     • move left and right -> left = 4, right = 3 -> end

4. i = 2 (nums[i] = -1) -> skip because same as previous i

5. i = 3 (nums[i] = 0)

   • left = 4 (1), right = 5 (2) => sum = 3 -> since nums[i] > 0? not > 0 but no triplet found and pointers move -> finish Final result: [[-1, -1, 2], [-1, 0, 1]]

Edge cases and pitfalls

• Duplicates: forgetting to skip duplicates for i, left, or right will produce repeated triplets.

• Early stopping: when nums[i] > 0 we can break because the sum of three non-negative numbers cannot be zero (optimization).

• Small arrays: arrays with fewer than 3 elements should return [].

• All zeros: e.g., [0, 0, 0, 0] should return [[0,0,0]] — duplicates must be handled.

Variants and extensions

• k-sum generalization: solve k-sum using recursion and two-pointer for the base case (2-sum). Complexity grows quickly.

• Hash-set approach: you can use hashing to find pairs for each i, but managing duplicates and worst-case complexity can be trickier than the sorted two-pointer method.

• Return count instead of triplets: sometimes the problem only asks for the number of unique triplets — the same technique applies but track count rather than storing arrays.

Test cases

• [] -> []

• [0] -> []

• [0,0,0] -> [[0,0,0]]

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

• [1,2,-2,-1] -> [] (no triplets)

Interview tips

• First explain the brute-force O(n^3) approach, then improve to O(n^2) using sorting + two pointers.

• Emphasize handling duplicates — many candidates lose points here.

• Mention early termination when the current number > 0.

• If asked about memory, note that aside from sorting and output, the extra memory is O(1).

Conclusion

The sorted two-pointer technique yields an elegant O(n^2) solution for 3-sum with straightforward duplicate handling. It’s a must-know pattern for array-sum problems and scales naturally to k-sum variants with careful recursion and pruning.