Triple Sum Zero — Problem Statement & Solution Guide
Problem Description
Given an array of integers, find the count of unique triplets that sum to zero.
Examples
Input
[0, -1, 1, 0]
Output
3
Explanation: Step-by-step: First, we sort the array. Then, we fix the first element and use two pointers to find the other two elements that sum to the negation of the fixed element. We skip duplicate triplets by incrementing the first pointer when the second pointer is pointing to the same element as the first pointer. Finally, we return the count of unique triplets.
Input
[0, 0, 0]
Output
1
Explanation: Step-by-step: First, we sort the array. Then, we fix the first element and use two pointers to find the other two elements that sum to the negation of the fixed element. We skip duplicate triplets by incrementing the first pointer when the second pointer is pointing to the same element as the first pointer. Finally, we return the count of unique triplets.
Constraints
- 3 <= n <= 3000
- -10^5 <= arr[i] <= 10^5
Optimal Approach & Strategy
Sort the array. Iterate i from 0 to N-2. Use left and right pointers to find pairs summing to -arr[i]. Skip duplicates to ensure unique triplets. Time: O(N^2), Space: O(1) auxiliary.
Brute Force Approach
Use three nested loops to check all combinations. Time: O(N^3).
Verified Code Solutions
function threeSum(nums) { let count = 0; nums.sort((a, b) => a - b); for (let i = 0; i < nums.length - 2; i++) { let left = i + 1, right = nums.length - 1; while (left < right) { let sum = nums[i] + nums[left] + nums[right]; if (sum < 0) left++; else if (sum > 0) right--; else { count++; while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } } } return count; }class Solution {
public int solution(int[] nums) {
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = nums.length - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
count++;
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return count;
}
}def solution(nums):
nums.sort()
count = 0
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
count += 1
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
return countfunction threeSum(nums) { let count = 0; nums.sort((a, b) => a - b); for (let i = 0; i < nums.length - 2; i++) { let left = i + 1, right = nums.length - 1; while (left < right) { let sum = nums[i] + nums[left] + nums[right]; if (sum < 0) left++; else if (sum > 0) right--; else { count++; while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } } } return count; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.