Find all unique triplets summing to zero
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates array-based algorithm design, handling of duplicate results, and analysis of time and space complexity when producing unique triplets that sum to zero.
Constraints
- 0 <= len(nums) <= 3000
- -100000 <= nums[i] <= 100000
Examples
Input: ([-1, 0, 1, 2, -1, -4],)
Expected Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: The only unique triplets that sum to zero are [-1, -1, 2] and [-1, 0, 1].
Input: ([0, 0, 0, 0],)
Expected Output: [[0, 0, 0]]
Explanation: Even though there are multiple ways to choose three zeros, they all form the same triplet, so it appears once.
Input: ([],)
Expected Output: []
Explanation: An empty array cannot contain any triplet.
Input: ([1, 2, -2, -1],)
Expected Output: []
Explanation: No combination of three numbers sums to zero.
Input: ([-2, 0, 1, 1, 2],)
Expected Output: [[-2, 0, 2], [-2, 1, 1]]
Explanation: The two unique triplets summing to zero are [-2, 0, 2] and [-2, 1, 1].
Solution
def solution(nums):
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] > 0:
break
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return resultTime complexity: O(n^2). Space complexity: O(n) in Python due to sorting overhead, excluding the returned result.
Hints
- Sorting the array helps you avoid duplicates and makes it possible to use a two-pointer scan.
- Fix one number, then look for two remaining numbers whose sum equals its negation.