LeetCode 15: 3Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 15: 3Sum?

In LeetCode 15: 3Sum, you’re given an integer array nums, and your goal is to find all unique triplets [nums[i], nums[j], nums[k]] where i != j != k and their sum is zero (nums[i] + nums[j] + nums[k] = 0). The catch? You can’t repeat triplets, even if the same numbers appear in different positions. For example, with nums = [-1, 0, 1, 2, -1, -4], valid triplets are [-1, -1, 2] and [-1, 0, 1]—and that’s it, no duplicates allowed. The solution returns these triplets as a list of lists.

Problem Statement

• Input: An integer array nums.
• Output: A list of lists, where each sublist is a unique triplet summing to zero.
• Rules:
• Triplets must use distinct indices (i != j != k).
• No duplicate triplets in the result.
• Order of triplets or numbers within them doesn’t matter.

Constraints

• 0 <= nums.length <= 3000
• -10⁵ <= nums[i] <= 10⁵

Examples

• Input: nums = [-1, 0, 1, 2, -1, -4]
• Output: [[-1, -1, 2], [-1, 0, 1]]
• Why: -1 + (-1) + 2 = 0 and -1 + 0 + 1 = 0, both unique.
• Input: nums = []
• Output: []
• Why: No elements, no triplets.
• Input: nums = [0, 0, 0]
• Output: [[0, 0, 0]]
• Why: One unique triplet sums to zero.

Understanding the Problem: Finding the Triplets

To solve LeetCode 15: 3Sum in Python, we need to identify all unique triplets that sum to zero without repeating combinations. A naive approach might be to check every possible trio with three nested loops—O(n³) time—but with up to 3000 elements, that’s way too slow. Plus, we’d have to filter out duplicates, which adds complexity. Instead, we’ll use:

• Best Solution (Two-Pointer): O(n²) time, O(1) extra space (excluding output)—efficient and clever.
• Alternative Solution (Hash Set): O(n²) time, O(n) space—intuitive but slightly heavier on memory.

Let’s start with the Best Solution—the two-pointer approach—and break it down step-by-step.

Best Solution: Two-Pointer Approach

Why This Is the Best Solution

The two-pointer technique is the gold standard for 3Sum because it slashes the time complexity to O(n²) and uses minimal extra space (O(1) beyond the output). By sorting the array first, it leverages order to avoid duplicates and quickly find pairs that sum to a target. It’s like playing a game of “find the match” with two friends moving toward each other—fast and fun!

How It Works

Here’s the strategy:

• Step 1: Sort the Array:
• Sort nums to make duplicate handling and two-pointer logic easier.
• Step 2: Fix One Number:
• Loop through each element as the first number (nums[i]).
• Target is -nums[i] (since nums[i] + nums[j] + nums[k] = 0).
• Step 3: Use Two Pointers:
• Set left (after i) and right (end of array).
• Move pointers based on the sum:
• Sum too big? Move right left.
• Sum too small? Move left right.
• Sum equals target? Record triplet, adjust pointers, skip duplicates.
• Step 4: Avoid Duplicates:
• Skip repeated nums[i] values and adjust pointers to skip duplicate pairs.

Step-by-Step Example

Example: nums = [-1, 0, 1, 2, -1, -4]

• Sort: [-4, -1, -1, 0, 1, 2].
• i = 0, nums[i] = -4:
• Target = 4.
• left = 1 (-1), right = 5 (2) → -1 + 2 = 1 < 4 → left = 2.
• left = 2 (-1), right = 5 (2) → -1 + 2 = 1 < 4 → left = 3.
• left = 3 (0), right = 5 (2) → 0 + 2 = 2 < 4 → left = 4.
• left = 4 (1), right = 5 (2) → 1 + 2 = 3 < 4 → left = 5.
• No match.
• i = 1, nums[i] = -1:
• Target = 1.
• left = 2 (-1), right = 5 (2) → -1 + 2 = 1 → Add [-1, -1, 2].
• Skip duplicate left (-1), left = 3.
• left = 3 (0), right = 5 (2) → 0 + 2 = 2 > 1 → right = 4.
• left = 3 (0), right = 4 (1) → 0 + 1 = 1 → Add [-1, 0, 1].
• i = 2, nums[i] = -1:
• Skip (duplicate of -1).
• i = 3, nums[i] = 0:
• Target = 0.
• left = 4 (1), right = 5 (2) → 1 + 2 = 3 > 0 → No match.
• Result: [[-1, -1, 2], [-1, 0, 1]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # Step 1: Sort the array
        nums.sort()
        result = []
        n = len(nums)

        # Step 2: Loop through each element as first number
        for i in range(n - 2):
            # Skip duplicates for i
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Step 3: Set two pointers
            left = i + 1
            right = n - 1
            target = -nums[i]

            # Step 4: Find pairs summing to target
            while left < right:
                current_sum = nums[left] + nums[right]
                if current_sum == target:
                    result.append([nums[i], nums[left], nums[right]])
                    # Skip duplicates for left and 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

• Line 4: Sort nums—O(n log n)—to enable two-pointer logic and duplicate skipping.
• Line 5-6: Initialize result list and get array length.
• Line 9: Loop up to n-2 (need room for two more numbers).
• Line 10-11: Skip if nums[i] repeats to avoid duplicate triplets.
• Line 14-15: Set left after i, right at end.
• Line 16: Target is -nums[i] for the pair to sum to.
• Line 19-30: Two-pointer loop:
• Line 20: Compute sum of left and right.
• Line 21-27: If sum matches target, add triplet, skip duplicates, move pointers.
• Line 28: Sum too small, increment left.
• Line 30: Sum too big, decrement right.
• Time Complexity: O(n²)—sorting O(n log n) + O(n²) for two-pointer.
• Space Complexity: O(1) extra space (excluding output).

This is like a dance of pointers finding harmony at zero!

Alternative Solution: Hash Set Approach

Why an Alternative Approach?

The hash set method offers a different flavor—still O(n²) time but using O(n) extra space. It’s like keeping a little black book of numbers you’ve seen, checking if the perfect third number exists. It’s intuitive and adaptable, though less space-efficient than two-pointer.

How It Works

Here’s the plan:

• Step 1: Fix the first number (nums[i]).
• Step 2: For each second number (nums[j]), use a hash set to find the third.
• Step 3: Target is -(nums[i] + nums[j])—check if it’s in the set.
• Step 4: Use a set of tuples to deduplicate triplets.

Step-by-Step Example

Example: nums = [-1, 0, 1, 2, -1, -4]

• i = 0, nums[i] = -1:
• j = 1, nums[j] = 0 → Target = -(-1 + 0) = 1 → Set: {1, 2, -1, -4} → 1 found → [-1, 0, 1].
• j = 2, nums[j] = 1 → Target = -2 → Set: {2, -1, -4} → No match.
• j = 4, nums[j] = -1 → Target = 2 → Set: {-4} → 2 found (earlier) → [-1, -1, 2].
• i = 1, nums[i] = 0:
• Check pairs, no new triplets.
• Result: [[-1, 0, 1], [-1, -1, 2]].

Code for Hash Set Approach

Copy codeclass Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = set()
        n = len(nums)

        for i in range(n - 2):
            # Hash set for two-sum
            seen = {}
            for j in range(i + 1, n):
                target = -(nums[i] + nums[j])
                if target in seen:
                    triplet = tuple(sorted([nums[i], nums[j], target]))
                    result.add(triplet)
                seen[nums[j]] = j

        return [list(triplet) for triplet in result]

• Line 4: Use a set to store unique triplets as tuples.
• Line 7: Outer loop for first number.
• Line 9-13: Inner loop with hash set:
• Line 10: Target for third number.
• Line 11-12: If target found, add sorted triplet to result set.
• Time Complexity: O(n²)—two nested loops.
• Space Complexity: O(n) for hash set.

It’s a lookup party for triplets!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(n²) time, O(1) space, no extra data structures.
• Cons: Requires sorting.
• Hash Set (Alternative):
• Pros: O(n²) time, intuitive, no sorting needed.
• Cons: O(n) space, trickier duplicate handling.

Two-pointer wins for efficiency.

Additional Examples and Edge Cases

• [0, 1, 1]: [] (no sum to zero).
• [-2, 0, 1, 1, 2]: [[-2, 0, 2], [-2, 1, 1]].
• [0]: [] (too few elements).

Both handle these well.

Complexity Breakdown

• Two-Pointer: Time O(n²), Space O(1).
• Hash Set: Time O(n²), Space O(n).

Two-pointer’s leaner.

Key Takeaways

• Two-Pointer: Sort and slide to zero!
• Hash Set: Lookup the third wheel!
• Duplicates: Sorting or sets save the day.
• Python Tip: Sorting’s your friend—see [Python Basics](/python/basics).

Final Thoughts: Sum It Up

LeetCode 15: 3Sum in Python is a triplet treasure hunt. The two-pointer approach dances through the array with grace, while the hash set method digs with a trusty map. Want more array adventures? Try LeetCode 1: Two Sum or LeetCode 167: Two Sum II. Ready to find those zeros? Head to Solve LeetCode 15 on LeetCode and crack it today!