3Sum - Leetcode 15 - 2 Pointers (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@khndokarrashid2991]

Love your videos man! im currently a data analyst trying to transfer over to software engineering and this is helping me a lot!

[@GregHogg]

That's awesome! Glad to hear it and best of luck :)

[@abbasfadhil1715]

Naming the function three sum is wild ☠️

[@DetectiveConan990v3]

they knew what they were doing

[@leonchen89]

Leetcode geeks who watch this video and will never participate in such activity.

[@DetectiveConan990v3]

@@leonchen89 not nice bro

[@jyotiaggarwal6983]

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

[@praveenchandkakarla406]

Hi jyoti, You can use the below code without using hashmap, reference -> kzbin.info/www/bejne/oKu9pHpuo5eFb6M 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

[@arindambhattacharjee9270]

@@praveenchandkakarla406 nai degi

[@praveenchandkakarla406]

@@arindambhattacharjee9270 don't need as well

[@newbiedb]

At 5:21, can you explain more about hashable and mutable in Set?

[@rijumondal6876]

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; } }

[@zdzisawdyrman7789]

Well... everything fine apart for the face that this solutions gets: "Time limit exceeded"

[@matthewbuchholz5251]

This is not true - this solution just successfully passed all test cases for me

[@Gangrelguy]

This is true, but to put the actual answer here, this is the video that updates this solution to pass all tests. kzbin.info/www/bejne/inPIgZagbamarq8

[@saitejasai4879]

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!

[@IshanParikh-j4k]

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?

[@cs_peter_lorenz]

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.

[@NitinKumar-qs9tw]

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.

[@GregHogg]

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

[@Glitzwhisker]

Leet code no longer accepts tuples in the answer

[@ankitchoudhary4618]

Very informative 👍

[@DariusD0815]

What is considered a "duplicate triplet"? All value permutations of a triplet are duplicates? e.g. [2,-1,-1] or [-1,2,-1]?

[@GregHogg]

Yeah different permutations of the same numbers are not desired

[@siddheshdewalekar7364]

Nice info👍

[@chriszhu589]

🤔anybody else getting this? `{(-1, 0, 1), (-1, -1, 2)} is not valid value for the expected return type list`

[@ThsHunt]

why do the step of filling hashset doesnt count towards the time

[@sonicrushXII]

It does take time, But it's constant time Constants are generally dropped when Calculating end time

[@samspeaks-hk1vp]

shouldn’t time complexity more than o(n3) cause we sorting in the inner loop?

[@haythemkhiari1089]

i think it is O(n^2 log(n) ) because sorting take O(log(n)) not o(n)

[@philipp1717]

You always sort tuples with the length 3, which is constant

[@samspeaks-hk1vp]

@@philipp1717 hmm .

[@SashoSuper]

I like those videos.

[@GregHogg]

Awesome!

[@onlywrestling7810]

It gives TLE, only 312/313 test cases are passed

[@GregHogg]

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

[@santanu_barua]

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); }

[@lakshayjain9337]

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

[@rakeshande449]

It's getting TLE

[@GregHogg]

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

[@Buckwheattomato]

thanks for answered. I got TLE too.@@GregHogg

[@benravenhill484]

My brain exploded

[@GregHogg]

😂

[@jagrat12354]

getting Time Limit Exceeded using this method, dont know why. Even running ur code does the same

[@GregHogg]

They recently changed this question so this solution doesn't run on the last test case. Very dumb of them to do that

[@saaddude1]

@@GregHogg Any idea, how to tweak the solution to pass all test cases?

[@antipainK]

Using a set feels like cheating here...

[@emirhanbilgic2475]

I fucking love you, what can I do with this?