15. 3sum

This problem challenges many candidates because it combines several concepts at once: avoiding duplicate triplets, managing multiple pointers, and maintaining efficiency. A brute-force solution is easy to write but quickly becomes too slow for larger inputs. What makes this problem a common interview favorite is the key insight of reducing a 3-element search into a 2Sum problem—by fixing one number and applying the two-pointer technique on a sorted array.

Problem statement

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] where i, j, and k are distinct indices, such that the sum of the three elements equals zero.

Your result must not include any duplicate triplets. Two triplets are considered duplicates if they contain the same set of values, regardless of the order in which they appear or the order of elements within the triplet.

Return the list of all such unique triplets. The output can be in any order.

Constraints

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

Examples

Why enumerating all possibilities doesn’t scale

The most direct approach is to examine every combination of three distinct indices. For an array of length n, there are roughly n * (n-1) * (n-2) / 6 such combinations, which is O(n^3). When n can be as large as 3000, this results in approximately 4.5 billion operations in the worst case, which is far too slow for typical time limits.

Beyond the sheer number of checks, the naive approach also requires extra bookkeeping to avoid reporting duplicate triplets. You would need to sort each triplet and store it in a set, adding overhead for hashing and comparison on every iteration. The combination of cubic time complexity and the deduplication overhead makes this approach impractical for the given constraints.

Optimized approach

The key insight is to reduce the 3Sum problem into a series of 2Sum problems. First, sort the array. Then, for each element nums[i], the problem becomes: find two elements in the remaining portion of the array that sum to -nums[i]. Since the array is sorted, this sub-problem can be solved efficiently using two pointers, one starting just after i and the other at the end of the array.

Sorting also provides a clean mechanism for skipping duplicates. If nums[i] equals the previous element, you skip it entirely because any triplets starting with that value have already been found. Similarly, after finding a valid triplet, you advance both pointers past any duplicate values before continuing the search.

Why the optimized approach works well

Sorting transforms the array into a structure where the two-pointer technique is valid. Because the elements are in non-decreasing order, moving the left pointer rightward always increases the sum, and moving the right pointer leftward always decreases it. This monotonic behavior guarantees that every potential pair is considered without redundant checks.

The duplicate-skipping logic is both simple and complete. By skipping repeated values at the outer loop level and at both inner pointer positions, the algorithm ensures each unique triplet is discovered exactly once without needing a hash set for deduplication. The result is a clean O(n^2) solution with minimal auxiliary space.

Step-by-step algorithm

1. Sort the input array nums in ascending order.
2. Initialize an empty list result to collect valid triplets.
3. Iterate through the array with index i from 0 to n - 3 (inclusive), treating nums[i] as the first element of the triplet.
4. If i > 0 and nums[i] equals nums[i - 1], skip this iteration to avoid duplicate first elements.
5. If nums[i] > 0, break out of the loop. Since the array is sorted, no three positive numbers can sum to zero.
6. Set left to i + 1 and right to n - 1.
7. While left < right, compute currentSum as nums[i] + nums[left] + nums[right].
8. If currentSum < 0, increment left to increase the sum.
9. If currentSum > 0, decrement right to decrease the sum.
10. If currentSum == 0, append [nums[i], nums[left], nums[right]] to result.
11. After finding a triplet, advance left past all consecutive duplicates of nums[left].
12. Advance right past all consecutive duplicates of nums[right].
13. Move left one step right and right one step left to continue searching.
14. After all iterations are complete, return result.

Python implementation

def three_sum(nums):
    # Sort to enable two-pointer traversal and duplicate skipping
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Skip duplicate values for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Early termination when smallest candidate is positive
        if nums[i] > 0:
            break

        left = i + 1
        right = n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum < 0:
                left += 1
            elif current_sum > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for the second element
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicates for the third element
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result


def main():
    test_cases = [
        [-2, 0, 1, 1, 2],
        [1, -1, -1, 0],
        [-4, -2, -1, 0, 1, 2, 3, 4],
        [3, -3, 0, -1, 1, 2, -2],
        [-5, -3, -1, 0, 1, 2, 3, 5],
    ]

    for idx, nums in enumerate(test_cases, 1):
        result = three_sum(nums[:])
        print(f"{idx}.\tInput array: {nums}")
        print(f"\tResult: {result}")
        print("-" * 100)


if __name__ == "__main__":
    main()

Time complexity

The sorting step takes O(n log n) time. The outer loop runs at most n times, and for each iteration the two-pointer scan processes the remaining elements in O(n) time. This gives an overall complexity of O(n^2) for the nested loop structure. Since O(n^2) dominates O(n log n), the total time complexity is O(n^2), where n is the length of nums.

Space complexity

The sorting algorithm in Python (Timsort) uses up to O(n) auxiliary space in the worst case. Beyond that, only a constant number of pointer variables are used during the search. The output list is not counted as auxiliary space since it is required by the problem. Therefore, the space complexity is O(n) due to the sort.

Edge cases

• All zeros: An array like [0, 0, 0, 0] should return exactly one triplet [0, 0, 0]. The duplicate-skipping logic handles this correctly.
• No valid triplet: When all elements are positive (e.g., [1, 2, 3]) or all negative (e.g., [-5, -3, -1]), the result should be an empty list. The early termination check catches the all-positive case immediately.
• Minimum length array: With exactly three elements, there is only one possible triplet to check. The algorithm handles this without any special casing.
• Heavy duplicates: Arrays like [-1, -1, -1, -1, 2, 2, 2, 2] should still produce only [[-1, -1, 2]]. The skip logic at both the outer and inner levels prevents redundant entries.

Common pitfalls

• Forgetting to skip duplicates at the outer loop level: This leads to repeated triplets in the output even though the inner logic is correct.
• Off-by-one errors in duplicate skipping: Advancing the pointer past duplicates without checking left < right can cause index-out-of-bounds errors.
• Not sorting the array first: Without sorting, the two-pointer technique does not work, and duplicate detection becomes significantly harder.
• Using a hash set for deduplication instead of pointer skipping: While functionally correct, this adds unnecessary overhead and is often seen as a less elegant solution in interviews.
• Missing the early termination when nums[i] > 0: The algorithm still produces correct results without this check, but interviewers appreciate candidates who identify this optimization.