a cleaner solution,
def triplets_with_sum_0(nums: List[int]) -> List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
# handle duplicates with these 3 lines
# note: only need to check for i and i-1.
# (left, right) won't throw duplicates since
# they are moved on each iteration
if i == 0 or nums[i] != nums[i - 1]:
left = i + 1
right = n - 1
while left < right:
x, y, z = nums[i], nums[left], nums[right]
s = x + y + z
if s == 0:
res.append([x, y, z])
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return res
Based off of your python code:
For Java -
Collections.sort(nums);
ArrayList<List> res = new ArrayList<>();
for(int i = 0; i < nums.size() - 3; i++){
if(i == 0 || nums.get(i) != nums.get(i-1)){
int l = i + 1, r = nums.size() - 1;
while (l < r) {
int sum = nums.get(l) + nums.get(r) + nums.get(i);
if (sum == 0){
List<Integer> tempRes = new ArrayList<>();
tempRes.add(nums.get(i));
tempRes.add(nums.get(l));
tempRes.add(nums.get(r));
res.add(tempRes);
r--;
}
if (sum > 0)
r--;
else
l++;
}
}
}
return res;
this will fail with input nums = [-1, 0, 0, 1, 1].
def remove_duplicates(arr, target):
arr.sort()
res = []
for i in range(len(arr)):
right = len(arr) - 1
left = i + 1
while left < right:
total = arr[left] + arr[right] + arr[i]
if total == target:
res.append([arr[left], arr[right], arr[i]])
left += 1
elif total > target:
right -= 1
else:
left += 1
return res
I think it’s cleaner solution
def triplets_with_sum_0(nums: List[int]) → List[List[int]]:
i = 0
j = len(nums) - 1
nums.sort()
res = []
for k in range(len(nums)-3):
i = k + 1
j = len(nums) - 1
while i < j:
t = [nums[k], nums[i], nums[j]]
if sum(t) == 0 and t not in res:
res.append(t)
if sum(t) < 0:
i += 1
else:
j -= 1
return res
Since when did python move Counter from collections to typing?
Also, the explanation of the solution is so incredibly unclear.
“Each cycle, we move the pair of pointers and see if they are in the list. If they are, they are a valid pair of pointers.”
This website is full of lazy writing. I’m a little mad at myself for paying money for this garbage website.
And to add to my earlier comment:
“If a BST is an option, then use it to reduce the need for sorting.”
Yes, I imagine most people reading this site know that you mean Binary Search Tree when they read BST, but as a general rule of thumb when writing, you should indicate what an acronym means before introducing it. Instead, you just dropped BST in the middle of an article explaining two pointers.
Another possible solution, using a dictionary to ensure there are no duplicate triplets:
def triplets_with_sum_0(nums: List[int]) -> List[List[int]]:
result = {}
nums = sorted(nums)
for i, first_num in enumerate(nums):
j = i + 1
while j < len(nums) - 1:
second_num = nums[j]
third_num = 0 - second_num - first_num
k = len(nums) - 1
while j < k:
triplet = [first_num, second_num, third_num]
key = '_'.join([str(num) for num in triplet])
if nums[k] == third_num and key not in result:
result[key] = triplet
break
k -= 1
j += 1
return list(result.values())
Golang solution
func tripletsWithSum0(nums []int) [][]int {
if len(nums) < 3 {
return nil
}
sort.Ints(nums)
result := make([][]int, 0, len(nums)/3)
left, right := 0,0
for i := 0; i < len(nums)-2; i++ {
// return early if we know there is no hope of ever being at 0
if nums[i] > 0 {
return result
}
left, right = i+1, len(nums)-1
// skip duplicate numbers so we don't duplicate results
if i > 0 && nums[i] == nums[i-1] {
continue
}
for left < right {
// skip duplicate numbers so we don't duplicate results
if left > i+1 && nums[left] == nums[left-1] {
left++
continue
}
sum := nums[i] + nums[left] + nums[right]
switch {
case sum == 0:
result = append(result, []int{nums[i], nums[left], nums[right]})
left++
right--
case sum > 0:
right--
case sum < 0:
left++
}
}
}
return result
}
simple clean and fast
def triplets_with_sum_0(nums: List[int]) -> List[List[int]]:
nums.sort()
triplets = []
for p1 in range(len(nums) - 2):
if p1 >= 1 and nums[p1] == nums[p1 - 1]:
continue
p2, p3 = p1 + 1, len(nums) - 1
while p2 < p3:
total = nums[p1] + nums[p2] + nums[p3]
if total < 0:
p2 += 1
elif total > 0:
p3 -= 1
else:
triplets.append([nums[p1], nums[p2], nums[p3]])
p2 += 1
p3 -= 1
while nums[p2] == nums[p2 - 1] and p2 < p3:
p2 += 1
return triplets
With recursion
from typing import List
def triplets_with_sum_0(nums: List[int]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
n = len(nums)
nums.sort()
res = []
def dfs(start, path):
if len(path) == 3 and sum(path) == 0 and path not in res:
res.append(path)
return
elif len(path) == 3:
return
for i in range(start, n):
dfs(i+1, path + [nums[i]])
dfs(0, [])
return res
Simple code passing all the tests.
def triplets_with_sum_0(nums: List[int]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
res = set()
nums.sort()
for i in range(len(nums)-2):
j = i+1
k = len(nums)-1
while j<k:
if nums[j] +nums[k] == -nums[i]:
res.add((nums[i],nums[j],nums[k]))
j+=1
k-=1
elif nums[j] +nums[k] < -nums[i]:
j+=1
else:
k-=1
res = list(res)
res.sort()
return res
This article needs to really be written again properly. The explanation has incomplete and absolutely random sentences -
"
Each cycle, we move the pair of pointers and see if they are in the list. If they are, they are a valid pair of pointers. If the position of the pair changes, move the slow pointer and reset the position of the pair.
For this question, duplicates are not allowed, and the result must be sorted, so we can do a few things to simplify. We use a map to count the multiplicity of the numbers that appeared. If binary search tree is an option, then use it to reduce the need for sorting. Every time the pair is reset, the left pointer is reset to the position of the first pointer to guarantee sorted order.
Time Complexity: O(n^2)
We have a pointer moving through the list and each step we move through the list another time.
"
Should have really seen these comments before paying for this website!
Hey, sorry we are in the process of content overhauling. some of the content were not reviewed properly and I will be rewriting it this week.
I agree with unhappy coder. The explanation here is not very clear. Perhaps adding a visualization as shown for other solutions would be helpful.