Code › algorithm-study

LeetCode 15 - 3Sum

A 3Sum solution using sorting and a two-sum-style hash map approach.

algorithmleetcodearrayhash-maptwo-sumpythonlearning

This is a Medium array problem where the goal is to find all unique triplets whose sum is 0. A direct triple-loop check would push the time complexity to O(n³), so I fixed one value first and treated the remaining part as a two-sum-style problem.

  • Problem link: 15. 3Sum
  • Summary: Given an integer array nums, return all unique triplets whose sum is 0.

For example:

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

The valid triplets are:

[-1, -1, 2]
[-1, 0, 1]

The problem asks for value combinations, not index combinations. Since the same value combination can be produced more than once, duplicate triplets need to be removed.

Approach

1. Fix one value first

3Sum needs three numbers, but once one value is fixed, the remaining problem becomes a two-sum problem.

If the fixed value is -1, the other two values need to sum to 1.

fixed = -1
target = 1

Then I scan the remaining range and look for the complement needed to reach target. By storing values I have already seen in a hash map, I can check whether the needed complement has appeared in average O(1) time.

target = -nums[i]
nums_map = {}

for j in range(i + 1, n):
    comp = target - nums[j]
    if comp in nums_map:
        answer.add((nums[i], comp, nums[j]))
    nums_map[nums[j]] = j

2. Why sorting comes first

I sort the array before the main loop. Sorting lets me skip the same fixed value in the outer loop, and it also keeps the values inside each triplet in a stable order when they are inserted into the set.

nums.sort()

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

If -1 appears multiple times, only the first -1 is used as the fixed value. Without this check, the same starting value can generate the same triplet again.

3. Use a set to remove duplicate triplets

Even if duplicate fixed values are skipped, duplicate values inside the inner range can still produce the same triplet. Instead of appending directly to a list, I store each triplet as a tuple inside a set.

answer.add((nums[i], comp, nums[j]))

Since the array is sorted, the tuple order stays consistent. At the end, I convert each tuple back into a list to match the LeetCode return format.

return [list(triplet) for triplet in answer]

4. Two-pointer idea

While looking up other solutions, I also studied the sorted two-pointer approach. It still fixes one value first, but instead of using a hash map for the remaining range, it places left and right pointers at both ends and compares the sum.

If the sum is smaller than 0, a larger value is needed, so left moves right. If the sum is larger than 0, a smaller value is needed, so right moves left. When the sum is 0, the triplet is stored, and both pointers move past duplicate values. I kept the code for this version below the implementation I actually wrote.

Troubleshooting

The main point in this problem is duplicate handling. 3Sum returns multiple triplets, and the same value combination should appear only once. I handled this by skipping duplicate fixed values in the outer loop and using a set for the result.

Using a set means the result order is not guaranteed. That is fine for LeetCode because the order of triplets and the order of the full result are not required. If the output order had to be stable, I would need to sort the final result or handle duplicates directly through the two-pointer approach.

Complexity analysis

  • Time complexity: O(n²)

    • Sorting takes O(n log n), and the nested scan dominates the total cost. For each fixed value, the remaining range is scanned once, so the final complexity is O(n²).

  • Space complexity: O(n)

    • In the hash map approach, each fixed value creates a hash map for values seen in the remaining range. The result set also takes space proportional to the number of valid triplets.
    • In the two-pointer approach, excluding the result array, the extra space is O(1) because only pointer and sum variables are needed.

Implementation code

The final implementation sorts the array, fixes one value, and checks the remaining range with a two-sum-style hash map.

from typing import Dict, Set

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        answer: Set[tuple[int, int, int]] = set()
        n = len(nums)
        nums.sort()

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

            target = -nums[i]
            nums_map: Dict[int, int] = {}

            for j in range(i + 1, n):
                comp = target - nums[j]
                if comp in nums_map:
                    answer.add((nums[i], comp, nums[j]))
                nums_map[nums[j]] = j

        return [list(triplet) for triplet in answer]

Two-pointer code I studied afterward

While reviewing other solutions, I also checked the two-pointer version. This approach still fixes one value first, but the remaining range is handled by moving left and right pointers instead of building a hash map.

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        answer = []

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

            left = i + 1
            right = len(nums) - 1

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

                if total == 0:
                    answer.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 total < 0:
                    left += 1
                else:
                    right -= 1

        return answer

The time complexity is still O(n²). The difference is that this version does not build a hash map for every fixed value, so the extra space, excluding the result, is O(1). The duplicate handling is more manual, but this is the more common standard solution for 3Sum.

Summary and reflection

Trying to find three values at once makes the combination count grow quickly. Fixing one value turns the remaining work into a two-sum problem, and a hash map can check the needed complement quickly.

In this solution, sorting reduces duplicate fixed values, and the result set removes duplicate triplets. The hash map version makes the two-sum extension easy to follow, while the two-pointer version reduces extra space and handles duplicates directly.