there is a better solution I guess, why using a set to store unique list, we can just move the pointers till we found a new int in a sorted array, this will basically cancel the possiblity of taking the duplicate without using the extra space class Solution { public List threeSum(int[] nums) { List ans = new ArrayList(); int n = nums.length; Arrays.sort(nums); for(int i = 0 ; i < n-1 ; i++){ int j = i+1; if (i > 0 && nums[i] == nums[i - 1]) continue; int k = n-1; while(j < k){ int sum = nums[i] + nums[j] + nums[k]; if(sum == 0){ ans.add(Arrays.asList(nums[i],nums[j],nums[k])); while(j < k && nums[j] == nums[j+1]){ j++; } while( j < k && nums[k] == nums[k-1]){ k--; } j++; k--; } else if(sum < 0){ j++; } else{ k--; } } } return ans; } }
This is true, but to put the actual answer here, this is the video that updates this solution to pass all tests. ruclips.net/video/TBePcj8DgxM/видео.html
First of all thanks for your videos and you explain very well. :) I may have found a limitation of your solution: Your hashmap only works by the assumption that there are maximum duplicates of the same number. Is that a requirement for the this leetcode questions? What is about, if you have [-1,0,1,2,-1,-4, -1] ? Here would be 3 times -1. The indexing would be become wrong.
If we have a duplicate in nums, we are replacing the value of corresponding duplicate (i.e,. new index of duplicate) in dict. Doesn't this affect the code? I watch your videos. You explain well. thank you!
Hi, I used your solution for Python3 and after submitting,it is showing Time Limit exceeded. How can I improvise it to resolve this issue as I see we using two pointer approach here with hashMap simultaneously which costs O(N*2) complexity but sorting and storing in set increases its complexity.could you please help
Hi jyoti, You can use the below code without using hashmap, reference -> ruclips.net/video/jzZsG8n2R9A/видео.html def threeSum(self, nums: List[int]) -> List[List[int]]: res=[] nums.sort() for i in range(len(nums)): if i>0 and nums[i] == nums[i-1]: continue l,r = i+1,len(nums)-1 while l < r: thSum = nums[i]+nums[l]+nums[r] if thSum < 0: l += 1 elif thSum > 0: r -= 1 else: res.append([nums[i],nums[l],nums[r]]) l += 1 while l < r and nums[l] == nums[l-1]: l += 1 return res
Yeah, they added this test case in literally a few days after I posted this video. I'll have to redo it with the n^2 solution that avoids using a Hashmap
Java Solution for this: ------------------------------------- public List threeSum(int[] nums) { Map map = new HashMap(); for (int i = 0; i< nums.length; i++) { map.put(nums[i], i); } Set result = new HashSet(); for (int i = 0; i< nums.length;i++) { for (int j = i+1; j< nums.length; j++) { int desired = -nums[i] - nums[j]; if (map.containsKey(desired) && map.get(desired)!= i && map.get(desired)!=j) { List triplet = Arrays.asList(nums[i], nums[j], desired); Collections.sort(triplet); result.add(triplet); } } } return new ArrayList(result); }
Great logic But why this c++ code is storing similar strings vector threeSum(vector& nums) { unordered_map map; int i,j,n=nums.size(); vector ans; sort(nums.begin(),nums.end()); for(i=0;i
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Naming the function three sum is wild ☠️
they knew what they were doing
Love your videos man! im currently a data analyst trying to transfer over to software engineering and this is helping me a lot!
That's awesome! Glad to hear it and best of luck :)
there is a better solution I guess, why using a set to store unique list, we can just move the pointers till we found a new int in a sorted array, this will basically cancel the possiblity of taking the duplicate without using the extra space
class Solution {
public List threeSum(int[] nums) {
List ans = new ArrayList();
int n = nums.length;
Arrays.sort(nums);
for(int i = 0 ; i < n-1 ; i++){
int j = i+1;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int k = n-1;
while(j < k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
while(j < k && nums[j] == nums[j+1]){
j++;
}
while( j < k && nums[k] == nums[k-1]){
k--;
}
j++;
k--;
}
else if(sum < 0){
j++;
}
else{
k--;
}
}
}
return ans;
}
}
Well... everything fine apart for the face that this solutions gets: "Time limit exceeded"
This is not true - this solution just successfully passed all test cases for me
This is true, but to put the actual answer here, this is the video that updates this solution to pass all tests. ruclips.net/video/TBePcj8DgxM/видео.html
Very informative 👍
First of all thanks for your videos and you explain very well. :)
I may have found a limitation of your solution: Your hashmap only works by the assumption that there are maximum duplicates of the same number. Is that a requirement for the this leetcode questions?
What is about, if you have [-1,0,1,2,-1,-4, -1] ? Here would be 3 times -1. The indexing would be become wrong.
Nice info👍
At 5:21, can you explain more about hashable and mutable in Set?
If we have a duplicate in nums, we are replacing the value of corresponding duplicate (i.e,. new index of duplicate) in dict. Doesn't this affect the code? I watch your videos. You explain well. thank you!
Hi,
I used your solution for Python3 and after submitting,it is showing Time Limit exceeded.
How can I improvise it to resolve this issue as I see we using two pointer approach here with hashMap simultaneously which costs O(N*2) complexity but sorting and storing in set increases its complexity.could you please help
Hi jyoti,
You can use the below code without using hashmap, reference -> ruclips.net/video/jzZsG8n2R9A/видео.html
def threeSum(self, nums: List[int]) -> List[List[int]]:
res=[]
nums.sort()
for i in range(len(nums)):
if i>0 and nums[i] == nums[i-1]:
continue
l,r = i+1,len(nums)-1
while l < r:
thSum = nums[i]+nums[l]+nums[r]
if thSum < 0:
l += 1
elif thSum > 0:
r -= 1
else:
res.append([nums[i],nums[l],nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
return res
@@praveenchandkakarla406 nai degi
@@arindambhattacharjee9270 don't need as well
When I used this solution in Python, it was accepted. However, as you mentioned, using Python 3 causes a time limit exceed.
I like those videos.
Awesome!
Hey Greg! unfortunately time limit exceeded for last test case [0,0,0,0,0.........0,0,0] on Leetcode. 312/313 test cases passed.
Yeah, they added this test case in literally a few days after I posted this video. I'll have to redo it with the n^2 solution that avoids using a Hashmap
Java Solution for this:
-------------------------------------
public List threeSum(int[] nums) {
Map map = new HashMap();
for (int i = 0; i< nums.length; i++) {
map.put(nums[i], i);
}
Set result = new HashSet();
for (int i = 0; i< nums.length;i++) {
for (int j = i+1; j< nums.length; j++) {
int desired = -nums[i] - nums[j];
if (map.containsKey(desired) && map.get(desired)!= i && map.get(desired)!=j) {
List triplet = Arrays.asList(nums[i], nums[j], desired);
Collections.sort(triplet);
result.add(triplet);
}
}
}
return new ArrayList(result);
}
did the same solution as yours, but when I submit it on leetcode, it is showing "Time limit Exceeded", is there a possible O(n) solution?
It's getting TLE
Yes, they actually changed it very recently and this no longer passes! You need to do the one where you sort and then use two pointers now
thanks for answered. I got TLE too.@@GregHogg
What is considered a "duplicate triplet"? All value permutations of a triplet are duplicates? e.g. [2,-1,-1] or [-1,2,-1]?
Yeah different permutations of the same numbers are not desired
Great logic
But why this c++ code is storing similar strings
vector threeSum(vector& nums) {
unordered_map map;
int i,j,n=nums.size();
vector ans;
sort(nums.begin(),nums.end());
for(i=0;i
shouldn’t time complexity more than o(n3) cause we sorting in the inner loop?
i think it is O(n^2 log(n) ) because sorting take O(log(n)) not o(n)
You always sort tuples with the length 3, which is constant
@@philipp1717
hmm .
My brain exploded
😂
why do the step of filling hashset doesnt count towards the time
It does take time, But it's constant time
Constants are generally dropped when Calculating end time
Using a set feels like cheating here...
It gives TLE,
only 312/313 test cases are passed
Yes, sorry. Leetcode recently added a case to make this solution not work. At some point I'll make a solution for a different algorithm that works
getting Time Limit Exceeded using this method, dont know why. Even running ur code does the same
They recently changed this question so this solution doesn't run on the last test case. Very dumb of them to do that
@@GregHogg Any idea, how to tweak the solution to pass all test cases?
I fucking love you, what can I do with this?