0% completed
Solution: Triplet Sum to Zero
Problem Statement
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
Examples
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.
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>
.....
.....
.....
Carol Lisbon
· 3 months ago
Doing set comprehension like my solution is technically slower than the given solution but it is much more intuitive and simple to look at
def searchTriplets(self, arr): triplets = set() arr.sort() for i in range(len(arr)-2): if i > 0 and arr[i] == arr[i - 1]: continue left_i = i+1 right_i = len(arr)-1 while left_i < right_i: if arr[i] + arr[left_i] + arr[right_i] == 0: triplets.add((arr[i], arr[left_i], arr[right_i])) left_i += 1 elif arr[i] + arr[left_i] + arr[right_i] < 0: left_i += 1 else: right_i -= 1 return [list(t) for t in triplets]
Aleti Jagadeswara Rao
· 4 months ago
for i in range(len(arr)): if arr[i] > 0: # This will help to break the loop if there are no negative vals break if i > 0 and arr[i] == arr[i-1]: # skip same element to avoid duplicate triplets continue self.searchPair(arr, -arr[i], i+1, triplets)
umesh
· a year ago
To form a triplet, you can chose first number in n ways. For each first number, second number can be chosen from the remaining n-1 numbers. But you don't get any choice for the third number, it must be -1*(first_num + second_num). Thus total of n*(n-1) or O(n^2) possibilities.
Kartiki Sharma
· 2 years ago
Triplets storage: The space used to store the resulting triplets is , where
Kis the number of triplets found. In the worst case, this could be proportional to N^2, especially if there are many valid triplets.
Shouldn't this be O(N)? Given an array of 3 items, it is only possible for at most one triplet to exist in the best case, which is N/3.
Văn Trần Phú Quí
· 2 years ago
The current is:
current_sum = arr[left] + arr[right] = -1 + 3 = 1
Should it be -1 + 3 = 2 instead?
willumeh
· 2 years ago
So, I understand that we are taking a three sum and manipulating it to look similar to a two sum, there the sum will equal -targetsum , where targetsum is the item at index i. My question is why does the value to the left of index i not matter?
V F
· 2 years ago
Does non-decreasing have a special meaning? Or is it just increasing?
If not, please reword to increasing.
Muhammad Shayan
· 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
}
}
}
Ariel Davies
· 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.
himanshu1495
· 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
Reading Progress
0%