View on NeetCode
View on LeetCode

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

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

Solution

Approach: Sort + Two Pointers

The key insight is to first sort the array, then fix one element and use two pointers to find pairs that sum to the negative of the fixed element. This reduces the 3Sum problem to multiple 2Sum problems.

To avoid duplicates, we skip over repeated values for all three positions (fixed element, left pointer, and right pointer).

Implementation

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

        for i in range(len(nums) - 2):
            # Skip duplicate values for first element
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Two pointers for remaining elements
            left, right = i + 1, len(nums) - 1
            target = -nums[i]

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

                if current_sum == target:
                    result.append([nums[i], nums[left], nums[right]])

                    # Skip duplicate values for second element
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1

                    # Skip duplicate values for third element
                    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

Complexity Analysis

• Time Complexity: O(n²), where n is the length of the array. Sorting takes O(n log n), and for each element, we perform a two-pointer search which takes O(n). Overall: O(n log n + n²) = O(n²).
• Space Complexity: O(1) or O(n) depending on the sorting algorithm used. We don’t count the output array in space complexity.

Key Insights

1. Sort First: Sorting enables us to use two pointers efficiently and makes duplicate detection straightforward by checking adjacent elements.

2. Reduce to 2Sum: By fixing one element and finding pairs that sum to its negative, we convert 3Sum into multiple 2Sum problems.

3. Skip Duplicates Carefully: We need to skip duplicates at all three positions:
   • Fixed element: if i > 0 and nums[i] == nums[i - 1]: continue
   • After finding a match: skip duplicates for both left and right pointers

4. Target Optimization: Instead of checking if nums[i] + nums[left] + nums[right] == 0, we check if nums[left] + nums[right] == -nums[i], which is clearer.

5. Early Termination: If nums[i] > 0, we can break early since all remaining elements will be positive (array is sorted), making it impossible to sum to 0.