3Sum - Leetcode 15 - 2 Pointers (Python)
ฝัง
- เผยแพร่เมื่อ 23 ส.ค. 2024
- Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gah...
Complete DSA Pathway Zero to Hero: • Data Structures & Algo...
Please check my playlists for free DSA problem solutions:
• Fundamental DSA Theory
• Array & String Questions
• 2 Pointers Questions
• Sliding Window Questions
• Binary Search Questions
• Stack Questions
• Linked List Questions
• Tree Questions
• Heap Questions
• Recursive Backtracking...
• Graph Questions
• Dynamic Programming (D...
My Data Science & ML TH-cam Playlist: • Greg's Path to Become ...
Learn Python and Data Science FASTER at mlnow.ai :)
Support the content: / @greghogg
Follow me on Instagram: / greghogg5
Connect with me on LinkedIn: / greghogg
Follow me on TikTok: / greghogg5
Coursera Plus: imp.i384100.ne...
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.ne...
- Stanford Algorithms: imp.i384100.ne...
- Python Data Structures: imp.i384100.ne...
- Meta Coding Interview Prep: imp.i384100.ne...
Python:
- UMichigan Python for Everybody: imp.i384100.ne...
- Python Mastery from MLNOW.ai: mlnow.ai/cours...
- Google IT Automation w/ Python: imp.i384100.ne...
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.ne...
- IBM Full Stack Developer: imp.i384100.ne...
- Meta Back-End Developer: imp.i384100.ne...
- John Hopkins HTML, CSS & JS: imp.i384100.ne...
- IBM DevOps: imp.i384100.ne...
Cloud Development:
- AWS Fundamentals: imp.i384100.ne...
- GCP Cloud Engineer: imp.i384100.ne...
- Microsoft Azure Fundamentals: imp.i384100.ne...
Game Development:
- Michigan State Unity Development: imp.i384100.ne...
- UColorado C++ for Unreal Engine: www.coursera.o...
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/cours...
- Python for Data Science by MLNOW.ai: mlnow.ai/cours...
- Google Data Analytics: imp.i384100.ne...
- IBM Data Science: imp.i384100.ne...
- IBM Data Engineer: imp.i384100.ne...
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/cours...
- ML w/ Andrew Ng: www.coursera.o...
- Deep Learning w/ Andrew Ng: imp.i384100.ne...
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Naming the function three sum is wild ☠️
Well... everything fine apart for the face that this solutions gets: "Time limit exceeded"
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 -> th-cam.com/video/jzZsG8n2R9A/w-d-xo.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.
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 :)
At 5:21, can you explain more about hashable and mutable in Set?
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
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
Very informative 👍
I like those videos.
Awesome!
Nice info👍
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
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
My brain exploded
😂
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 .
I fucking love you, what can I do with this?
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
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?
Using a set feels like cheating here...