Solving 3Sum Problem in Python: Step-by-Step Guide

Introduction to the 3Sum Problem

The 3Sum problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. At its core, the problem asks you to find all unique triplets in an array that sum up to a target value (usually zero). While the problem statement sounds deceptively simple, solving it efficiently requires a solid understanding of sorting, two-pointer techniques, and careful handling of duplicates.

Formally, given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Why the 3Sum Problem Matters

The 3Sum problem matters for several reasons beyond just passing interviews. First, it is a natural extension of the 2Sum problem and introduces the concept of reducing a higher-dimensional problem to a lower one. The technique of fixing one element and then solving a 2Sum on the remainder is a recurring pattern in algorithm design.

Second, the problem forces you to think about time complexity tradeoffs. A naive solution runs in O(n³) time, which is unacceptable for large inputs. The optimal solution runs in O(n²), and understanding how to make that leap is a foundational skill. Finally, the duplicate-handling logic teaches defensive programming and careful index management, skills that translate directly to real-world data processing tasks.

Understanding the Problem With an Example

Consider the input array [-1, 0, 1, 2, -1, -4]. The unique triplets that sum to zero are [-1, -1, 2] and [-1, 0, 1]. Notice that even though -1 appears twice in the array, the triplet [-1, 0, 1] should only appear once in the result. This duplicate avoidance is what trips up many developers.

Key Observations

• The order of elements within a triplet does not matter, but the result must contain distinct triplets.
• Sorting the array first makes duplicate detection much easier.
• Once sorted, you can use the two-pointer technique to find pairs that complete the triplet.
• If the smallest number in a triplet is positive, the sum cannot be zero, allowing early termination.

The Brute Force Approach

Before jumping to the optimal solution, it helps to understand the brute force approach. This uses three nested loops to check every possible triplet. While simple to write, it has O(n³) time complexity and will time out on large inputs.

def three_sum_brute_force(nums):
    result = []
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triplet = sorted([nums[i], nums[j], nums[k]])
                    if triplet not in result:
                        result.append(triplet)
    return result

# Example usage
nums = [-1, 0, 1, 2, -1, -4]
print(three_sum_brute_force(nums))
# Output: [[-1, -1, 2], [-1, 0, 1]]

The brute force approach works but is inefficient. The duplicate check using triplet not in result adds another layer of overhead, making the practical performance even worse than the theoretical O(n³).

The Optimal Two-Pointer Solution

The optimal approach reduces the problem to multiple 2Sum problems. First, sort the array. Then, iterate through each element as a potential first element of the triplet. For each fixed element, use two pointers (one starting just after the fixed element and one at the end) to find pairs that sum to the negation of the fixed element.

Step-by-Step Algorithm

• Sort the input array in ascending order.
• Iterate through the array with index i from 0 to n - 3.
• If nums[i] > 0, break early because no triplet can sum to zero.
• Skip duplicate values of nums[i] to avoid duplicate triplets.
• Initialize two pointers: left = i + 1 and right = n - 1.
• While left < right, compute the current sum of the three elements.
• If the sum is zero, record the triplet and move both pointers inward, skipping duplicates.
• If the sum is less than zero, move left forward to increase the sum.
• If the sum is greater than zero, move right backward to decrease the sum.

Complete Implementation

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

    for i in range(n - 2):
        # Early termination: if the smallest number is positive,
        # no triplet can sum to zero
        if nums[i] > 0:
            break

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

        left, right = i + 1, n - 1

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

            if current_sum == 0:
                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

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

    return result

# Example usage
nums = [-1, 0, 1, 2, -1, -4]
print(three_sum(nums))
# Output: [[-1, -1, 2], [-1, 0, 1]]

# Additional test cases
print(three_sum([0, 1, 1]))
# Output: []

print(three_sum([0, 0, 0]))
# Output: [[0, 0, 0]]

print(three_sum([-2, 0, 1, 1, 2]))
# Output: [[-2, 0, 2], [-2, 1, 1]]

Complexity Analysis

Sorting the array takes O(n log n) time. The outer loop runs O(n) times, and for each iteration, the two-pointer scan takes O(n) time. Therefore, the overall time complexity is O(n²), which is a significant improvement over the O(n³) brute force approach. The space complexity is O(1) if we ignore the space required for the output, or O(n) in the worst case for the output itself, since there can be up to O(n²) triplets in pathological cases.

Handling Variations of the Problem

Interviewers often modify the 3Sum problem to test your adaptability. Common variations include finding triplets that sum to a target other than zero, finding the triplet whose sum is closest to a target, or counting the number of valid triplets rather than returning them.

3Sum With a Custom Target

def three_sum_target(nums, target):
    nums.sort()
    result = []
    n = len(nums)

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

        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

print(three_sum_target([1, 2, 3, 4, 5, 6], 10))
# Output: [[1, 3, 6], [1, 4, 5], [2, 3, 5]]

3Sum Closest

def three_sum_closest(nums, target):
    nums.sort()
    n = len(nums)
    closest = float('inf')

    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if abs(current_sum - target) < abs(closest - target):
                closest = current_sum

            if current_sum == target:
                return current_sum
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return closest

print(three_sum_closest([-1, 2, 1, -4], 1))
# Output: 2

Best Practices

• Always sort first: Sorting unlocks the two-pointer technique and makes duplicate handling straightforward. The O(n log n) cost is negligible compared to the O(n²) main loop.
• Skip duplicates aggressively: After finding a valid triplet, always skip over duplicate values for both the second and third elements. This prevents duplicate triplets in the output without needing a set.
• Use early termination: If the array is sorted and the current first element is already greater than zero, no further triplets can sum to zero. Breaking early can save significant time on certain inputs.
• Avoid modifying the input: If the caller expects the original array to remain unchanged, work on a sorted copy instead of sorting in place.
• Test edge cases: Always test with arrays of length less than three, arrays with all zeros, arrays with all identical elements, and arrays with no valid triplets.
• Prefer readability over micro-optimizations: The O(n²) solution is already optimal in terms of asymptotic complexity. Avoid clever tricks that sacrifice clarity for marginal speed gains.

Common Pitfalls to Avoid

One frequent mistake is forgetting to skip duplicates for the first element. Without the check if i > 0 and nums[i] == nums[i - 1]: continue, you will process the same first element multiple times and generate duplicate triplets. Another common error is moving the pointers incorrectly after finding a valid triplet. You must move both left and right inward, not just one of them, because the current pair is already consumed.

Developers also sometimes forget to check left < right inside the duplicate-skipping while loops. Without this guard, the pointers can cross each other or go out of bounds, leading to incorrect results or runtime errors. Always include the boundary check in every inner loop.

Testing Your Solution

A robust test suite is essential for verifying your 3Sum implementation. Here is a set of test cases covering typical and edge scenarios.

def test_three_sum():
    assert three_sum([]) == []
    assert three_sum([0]) == []
    assert three_sum([0, 0]) == []
    assert three_sum([0, 0, 0]) == [[0, 0, 0]]
    assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
    assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
    assert three_sum([1, 2, 3, 4, 5]) == []
    assert three_sum([-2, 0, 1, 1, 2]) == [[-2, 0, 2], [-2, 1, 1]]
    assert three_sum([-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]) == [
        [-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2],
        [-2, -2, 4], [-2, 0, 2]
    ]
    print("All tests passed!")

test_three_sum()

Conclusion

The 3Sum problem is a perfect example of how sorting and the two-pointer technique can transform an O(n³) brute force solution into an elegant O(n²) algorithm. By fixing one element and reducing the remainder to a 2Sum problem, you not only improve performance but also gain a reusable pattern that applies to many related problems like 4Sum, 3Sum Closest, and container-with-most-water variants. Mastering the duplicate-skipping logic and the careful pointer movement is what separates a working solution from a correct and efficient one. With the implementation, variations, and best practices covered in this guide, you now have a complete toolkit to tackle the 3Sum problem confidently in any interview or production scenario.