I'm glad you said this one wasn't obvious. I was hoping I wasn't the only one.

@babybear-hq9yd

3 жыл бұрын

Not at all! I've asked this one on Pramp a handful of times as well, and everyone's always struggled. We're not alone :D

Wow! Best & clearest explanation I've seen for a difficult leetcode question.

@babybear-hq9yd

2 жыл бұрын

so happy to hear that!

Crisp clear explanation. I am glad I found you.

@babybear-hq9yd

2 жыл бұрын

:)

Wow! Thanks a ton for the lovely explanation. You're an awesome teacher.

@babybear-hq9yd

Жыл бұрын

thanks bro!!

Nice explanation! underrated channel!

@babybear-hq9yd

2 жыл бұрын

thx bro :)

effective communication and explanation (uses visuals)

This is such an amazing explanation to this ATROCIAS problem.

@babybear-hq9yd

2 жыл бұрын

woooo!

this video deserved more likes~!! Thx for the great content

@babybear-hq9yd

2 жыл бұрын

Thx a lot Charlie :)

REALLY HELPFUL, THANKS!

@babybear-hq9yd

3 жыл бұрын

Welcome!

Thanks for helping me man! was stuck on this for an hour :(

@babybear-hq9yd

3 жыл бұрын

It’s a toughie!

Very clear explanation! Thank you very much! But I think when sumB == target, you do not need to do right - = 1. Just do left +=1 and check nums[left] == nums[left -1] is enough.

@babybear-hq9yd

3 жыл бұрын

You may be right! :)

@charseo

2 жыл бұрын

I think we still need right -= 1 to avoid out of index

What really bugs me is when the ideal solution is still so high. I got a working solution in O(n3) (like what you have), but I really doubted myself because that still sounds bad.

@babybear-hq9yd

3 жыл бұрын

I hear that loud and clear. Thankfully, of the ~400 some odd problems I've done in Leetcode, I think this one is among the worst time complexities. Only n^3 one that I remember. Other notable ones would be subsets and permutations, which I think were in exponential and/or factorial time complexity :)

Could we remove duplicates from input array before looping to avoid all those conditional checks ?

@babybear-hq9yd

2 жыл бұрын

Perhaps, but the follow up question may be how do you do it without removing so you know which original indices make up the sum. Worth bringing up in the interview tho! Other edge case that may fail on is an array containing n numbers, each of which is the same. You’d be reduced to an array of length 1

What is the space complexity of the solution?

@babybear-hq9yd

3 жыл бұрын

Hey Sabreen, the space complexity would be O(1) if you exclude the result array, or O(n) if you include it in your analysis (typically, we don't include the necessary output in the space complexity.) I would also add that some people may argue that it would be an O(log n) space solution because behind the scenes Python may be using up some space to implement Tim Sort (which is the default O(nlogn) sorting function in Python.) If you were in an interview, you could safely make all these points as each one of them holds water in their own way. I hope this helps!

Sorting introduces O(n log n) time complexity, which should be multiplied into the big O

@babybear-hq9yd

2 жыл бұрын

Not necessarily. Since this is an array of integers you can do a radix sort which is more efficient than n log n. My implementation is n log n but by implementing a different sort it’ll be done faster

@samrazi1

2 жыл бұрын

The sort happens outside of the outer for-loop, so I think you are adding O(n log n) to O(n^3) to get O(n^3 + n log n). Since O(n^3) is the bigger time-complexity then you can say it's the most significant factor in the overall time complexity and drop the O(n log n). At least I think that's right.

@_7__716

2 жыл бұрын

Nice

Tough, but a lower quality version is tenable once you learned the trick.

Why can't we just use hashset to handle the unique values?

@babybear-hq9yd

3 жыл бұрын

Hey Owais, in what capacity would you use the hashset in the method your suggesting? In general, there may be a way to use a hashset similiar to how you would in the Two Sum problem, which you would could solve with O(n) time and space complexity. However, I can't think of a clean way to do that for 3sum and up! (Though I've been wrong before, and I'm sure I'll be wrong again :)

@owaiskazi9941

3 жыл бұрын

@@babybear-hq9yd So, I have written a similar code to what you have explained in the video. Instead of appending the values in a list, I was doing it in a hashset and didn't have any extra checks to handle quadruple duplicate as I thought hashset will do that itself. I ran into TLE. I'm not sure what went wrong

@babybear-hq9yd

3 жыл бұрын

@@owaiskazi9941 I'm not sure off the top of my head but if you paste the code I can take a look and give you my two cents

At leetcode this returns the wrong answer as it is failing at edge case with, I am not sure if Leetcodes expectation is valid as each 0 is not actually a separated list and does not make sense with the description given with the code. def test_fourSum3(self): ans= Solution.fourSum(self, [0,0,0,0], 0) assert ans == [[0,0,0,0]]

@babybear-hq9yd

3 жыл бұрын

i just tested the code out with this case and it worked for me. double check for mistakes!

@suspiriok

3 жыл бұрын

​@@babybear-hq9yd which version of python are you using ? If I am not mistaken I only renamed some variables of yours.

@suspiriok

3 жыл бұрын

TBH I like your soluion better than the leetcodes suggestion as its splitting two methods and I don't think that is necessary.

@suspiriok

3 жыл бұрын

Yes that was my typo I guess, I deleted the previous code I tried but when I double check it worked. And its runtime is also better than leetcodes solution. Thanks for confirming !