0% completed
Triplet Sum to Zero (medium)
On This Page
Problem Statement
Try it yourself
Problem Statement
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
Example 1:
Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [[-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explanation: There are four unique triplets whose sum is equal to zero. smallest sum.'
Example 2:
Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.
Constraints:
3 <= arr.length <= 3000- -10<sup>5</sup> <= arr[i] <= 10<sup>5</sup>
Try it yourself
Try solving this question here:
Anonymous
· 2 years ago
func findTripletSumToZero(arr: [Int]) -> [[Int]] {
let set = Set(arr)
var triplets = Set<Set<Int>>()
var i = 0
var j = 1
while (i < arr.count && j < arr.count) {
if (!set.contains(-1 * (arr[i] + arr[j]))) {
if (i == j) {
j += 2
} else {
j += 1
}
} else {
let triplet = Set([arr[i], arr[j], -1 * (arr[i] + arr[j])])
if (!triplets.contains(triplet)) {
triplets.insert(triplet)
}
if (i == j) {
i += 2
} else {
i += 1
}
}
}
return triplets.map { set in
set.map { elem in
elem
}
}
}
Anonymous
· 2 years ago
You only need to ensure two of the three numbers are not repeating. Because if 2 of the 3 are unique then the triplet is inherently unique. The second while loop for adjusting the right pointer is not necessary and makes the solution a more confusing.
Anonymous
· 3 years ago
class Solution: def searchTriplets(self, arr): triplets = [] # TODO: Write your code here arr.sort() n=len(arr) for i in range(0,n-2):#go upto the third last element only el=arr[i] if i>0 and arr[i]==arr[i-1]: continue j=i+1 k=n-1 while(j<k): #TODO: logic for skipping second element already chosen el2=arr[j] el3=arr[k] if arr[j]+arr[k]==(0-el): triplets.append([el,el2,el3]) j+=1 k-=1 while(j<k and arr[j]==el2): j+=1 while(j<k and arr[k]==el3): k-=1 elif arr[j]+arr[k]<(0-el): j+=1 while(j<k and arr[j]==el2): j+=1 else: k-=1 while(j<k and arr[k
Anonymous
· 3 years ago
The solution for this doesn't work, getting runtime errors for the Javascript version. Even if I copy the exact solution and paste it.
Anonymous
· 3 years ago
It seems like the only accepted solutions also sort the result array which doesn't seem to be part of the problem statement. If it is not a hard requirement, instead of checking for duplicates within searchPair, we can also append tuples to the list and then use a set to only leave the unique tuples before converting the tuples into lists.
Anonymous
· 3 years ago
/** Sort the array , iterate over the array by having left and right pointers and find the sum. */ public Set<List<Integer>> searchTriplets2(int[] array) { Arrays.sort(array); Set<List<Integer>> triplets = new HashSet<>(); // Iterate only length -2 since you cant make triplets with only 2 elements for (int i = 0; i < array.length - 2; i++) { // Left is 1 ahead of i when it starts int right = array.length - 1; // Right always starts from the end int left = i+1; while (left < right) { int currentSum = array[i] + array[left] + array[right]; if (currentSum == 0) { triplets.add(Arrays.asList(array[i], array[left], array[right])); left++; right--;
Anonymous
· 3 years ago
Isn't sorting done in place? If so, shouldn't the space complexity because be constant if we are ignore the output array?
Anonymous
· 3 years ago
I've read and watched a few videos on this problem and I really think it would be helpful if there was a good visual representation of what is going on. Especially when the "correct" solution here is very complicated and verbose.
Anonymous
· 4 years ago
If you find a triplet on the first call to seach_pair you will get a list index error because right already equals the end of the list so right +1 is out of bounds.
Anonymous
· 4 years ago
The code itself is pretty complicated, but this video gives a better visualization of how it works. Check it out: https://m.youtube.com/watch?v=PXpthXV1mmw
Reading Progress
0%
On This Page
Problem Statement
Try it yourself