TWO SUM II - Amazon Coding Interview Question - Leetcode 167 - Python
VloĆŸit
- Äas pĆidĂĄn 26. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
đ„· Discord: / discord
đŠ Twitter: / neetcode1
đź Support the channel: / neetcode
đĄ CODING SOLUTIONS: âą Coding Interview Solut...
đĄ DYNAMIC PROGRAMMING PLAYLIST: âą House Robber - Leetco...
đČ TREE PLAYLIST: âą Invert Binary Tree - D...
đĄ GRAPH PLAYLIST: âą Course Schedule - Grap...
đĄ BACKTRACKING PLAYLIST: âą Word Search - Backtrac...
đĄ LINKED LIST PLAYLIST: âą Reverse Linked List - ...
Solve it yourself: neetcode.io/problems/two-inte...
0:00 - Intuition / Brute force
3:55 - Two pointer / optimal
6:39 - Coding two pointer
#Coding #Programming #CodingInterview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - VÄda a technologie
đ neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! â€
the video's title should be 167 instead of 157đ€Ł
@@liairi6834 Just fixed, surprised no one noticed until now lol
Do you use blue switches???
Thanks for the video. I would add a if sum == target break as first condition in the while loop. Technically, the return [] should never be executed, and we should avoid such code (generally speaking, if the code is there - it must be executed in some edge cases, and I prefer to not have incorrect code, even if it will never be reached).
high quality explanations, honestly way better than most channels on this site. great work
...and on top of that - high quality microphone setup
I like how you also included the brute force solution. Thanks a lot!
The beauty about these challenges is that the code is simple but the logic to get to an optimal solution is quite complex.
One of the few leetcode mediums I've been able to solve alone, just by watching your videos with similar problems. Really appreciate the help
The solution itself is quite intuitive, the nontrivial part of this question is explaining why it always works (which I'm pretty sure the interviewer will ask).
More specifically, at each step we only consider moving the lower pointer up or the upper pointer down (in order to increase or decrease the sum resp), why do we not need to consider moving both pointers up or down at the same time (which might change the sum)?
Proof: Suppose exists a sorted array of n such that exists 2 indexes a,b that give the required sum, WLOG a
Hey There! I always look for your solutions in the CZcams first and then I move it to someone if I couldn't find your solution available to understand the leet code challenges. Thank you for all your efforts to demonstrate the leet code solutions. It really help us. Thank you! Please post as many solutions you can from leet code.
Really clear explanation with no useless information and a smart solution on top of that.đ
You got a new subscriber in your first couple of minutes! I would love to see & hear more from you, great!
That is very sweet solution! Loved it while you explain and arrive at the solution. Keep up the great work!
Brilliant mate, consistent quality explanation from the start!
That was a great video. I'll be sharing this with some friends for sure.
Amazing solution. Will keep that in mind about using sorted array to our advantage!
Love your videos, they are amazing!
Thank you, this was very helpful.
Your solutions are the best. Thanks!
Amazing explanation !
No way amazon asked this simple question đ, I took 2 coding interviews with amazon and its always matrices or something difficult.
what was the question?
@@robr4501 we cannot share but mine were def on leetcode. Just different wording
I got house robber on one of my FAANG interviews
@@nero9985 which FAANG? Curious who's still asking DP
â@@PippyPappyPattersoneveryone is asking dp
Great explanation!
It feels so good when you solve using the exact method I was thinking about!
Thanks for the explanation!
Youâre literally saving my life rnđđŸthank you for these videos
Happy to help!
Figuratively! Unless your life literally depends on clever pointer manipulation...
@@DrewLevitt lol! figuratively of course
Great solution, good job â
The two pointers solution was actually pretty neat đ
*neet
Please continue to upload videos like this
That's a lot easier than I thought it'd be! They mark it as medium, but it's almost like doing a binary search.
Great! as always!
Not sure if someone else mentioned this, but it seems to me that you could have also excluded 10 in the first round and 7 in the second round. If the array is sorted and 1 + 10 is greater than the target, then nothing after 1 can be added to 10 either. Same for 7 summed with anything after 3.
This still results in O(n^2), right?
@@jimmy090 Yup
I mean yeah, but why waste time with that? It's now like they are thousands of extra iterations. Although I agree with the simple exclusion of >target (9).
@@TheNuub63 That works for this case but not for cases with negatives on the left side unless I am misunderstanding your implications.
@@daimeunpraytor7984 if there are negative numbers you are correct! We would have to check everything basically!
Amazing solution, thank you sir.
best LC python solutions. I recommend this to everyone!
clear explanation, thanks!
Key thing I think you missed deleting array items is that you could have deleted, for example, the 10 in the first one, because if 1+10 > 9, then clearly n+1+10 is going to be correct.
Thank you NeetCode
heroic explanation
such an underrated channel
love your channel. really well done videos. hoping to get FANG now :)
How's it going?
Yo????
Where are you, made it?
nice explanation, thanks!
We can use hash mapping to...
_hash = {}
for index, i in enumerate(numbers):
complement = target - i
if complement in _hash:
return [_hash[complement] + 1, index+1]
_hash[i] = index
i = 2, complement = 9-2 => complement = 7. It will check key 7 is in the hash, if not it will add key 2 in hash
i = 7, complement = 9-7 => complement = 2. Key 2 is present in hash, so it returns index of key 2 and i (add 1 at return because index is starting from 1)
It uses extra space ...
//O(log n) best solution đ
if (numbers.size() target)
r = mid - 1;
else
r--;
}
}
return {-1, -1};
So, in 2sum 2 as compared to 2sum, we use the fact that the array is sorted to take the best-case space complexity from O(n) to O(1).
Thank you so much
I considered two pointers at first but for some reason decided that it wouldn't work. I went with finding the complement by binary search which was kind of an overkill but gave me an obviously suboptimal O(n*logn). Still, better than brute force.
We can stop at 10 from the first iteration since 1+ 10 is 11. No need to continue to 11 as you mentioned and also not to consider 10. So the second iteration array is 3457
This looks good for small arrays, but my guess at a solution for a bigger array would be to use a log search for the number closest to half of the target, eliminating any Halves of the given array who's numbers were above the target, and then use the same method you did to find the pair, except go outward from the middle, where the numbers closest to half of the target are, instead of going inward from the ends.
In good cases that would reduce the amount of searches you would need, although it would give an upper bounds of a n log n runtime if none of the elements were higher than the target.
Hey, thats a good thought! but that wouldn't work if say, all the numbers in the middle 50% are even, and all the numbers in each outer quartile were odd.
beautifully explained
This is satisfyingly efficient. Note that you can initialize r to the smaller the length of the array or the target number. The smallest possible values in numbers[0] and numbers[x] are 1 and x-1, thus the smallest sum is x, and r will always be
This doesn't work if the array can contain negative numbers. LeetCode's constraints say that -1000
non decreasing does not mean the same thing as increasing. It could be the same number many times
â@@romanpisani8157 It is correct, a non-descending array of integers can include duplicate values. However, note that you're responding to an old comment and there is a lot of evidence that the problem details have changed more than once over the years. I may well have made a mistake back then, but we can't really know without the context I was in at the time.
I managed to do this very elegantly without looking at any help. I'm proud of myself, a week ago I was very bad at this.
Here's my solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers) - 1
while numbers[i] + numbers[j] != target:
if numbers[i] + numbers[j] < target:
i += 1
else:
j -= 1
return [i + 1, j + 1]
It's a little bit more elegant as we don't compare the index numbers but the values of the array in those indexes. That's the condition of our while loop. I find it more readable this way.
Either way, great explanation as always.
nums =[3], target =6 fails this
Quick note, this technique only works assuming the list is sorted. So in an interview you have to ask if the indices of the original list being returned is one of the constraints. Given that when you sort the original list the indices of what add up to the target will change.
added this program to my list
this is beautiful!
Bro you're a genius.
This guy talking and typing.. TOP ASMR CHANNEL!!!
I think the first part of the solution is finding r
Thank you man!!.
target = 9
lst = [1,4,5,7,10,11]
for i, el in enumerate(lst):
if (target-el) in lst:
val1 = i
val2 = lst.index(target-el)
break
print(val1+1,val2+1)
Great answer. But time complexity is O(nÂČ). Since the index() takes O(n) time complexity âš
This question is now a Medium! Lol, LeetCode should make it possible for users (at least paid ones) to have an input on the difficulty of problems.
nice explanation
Awesome. Thanks.
When you have sorted array, and target= 9, you can throw away all elements from array at the beginning (before running algorithm code), which are greater than target (15 for this example), because we are doing Two Sum (addition with two numbers)
Negative integers thoâŠ
NeetCode for president.
This can be solved using binary search as well
Had I done this I would have coded option #1 and felt good about myself. Clearly I'm a beta programmer and not a chad coder.
Why not use binary search on the items after the current ?
This video was amazing! Thank you, thank you & thank you! (or thank you * 3 :))
i used the same two sum solution and added +1 returning index. works smoothly
Yes, I wonder why we can't use the same approach here since it's still O(n) complexity.
@@MohamedMosatafaUsing 2 pointers has space of O(1), donât know if it is stated anywhere that it has to be that though but this is the most optimal.
One of the most impressive parts of your leetcode skillz is the ability to draw everything cleanly using a mouse lol
He's probably using a tablet with a stylus.
Great video. I used it for Ruby and am in the 95th percentile for speed.
Looks like sub-linear is possible, instead of moving the pointers to the next position, do a binary search for the number you need or the one right after it.
Binary search is possible, you can even invert the list to improve performance
@@zwanchis how does that improve performance? I could possibly see readability, but isn't it just the mirror of the given array? That would mean you just swap certain operations, right?
What about time complexity? Are you going to apply binary search for each element?
@@aminafounoun Time complexity could be sub-linear by changing the proposed algorithm, of complexity O(N), to instead of moving the right or left pointers just by one, doing a binary search for the value that will be needed. Using the above example, left pointer -> 1, right pointer could be found by looking for 8 (= 9 - 1) using a binary search. The result of the search will yield 7, the entry available in the next position. Then, search for 2 (= 9 - 7), etc. The boundaries of the search narrowing each time. With the resulting complexity O(LogN), because we did not need to examine every position and taking advantage of the sorted order of entries.
@@DavidDLee This does multiple binary searches though, so it will only be O(log N) if the number of binary searches is constant, i.e. the number of searches doesn't increase as N increases.
I don't know if that's true for the average case, but you can find a worst- case example that is O(N log N).
When nums = [1,3,5,6,7,9,11] and target = 13, the left and right pointers alternate between which one has to move. It ends up doing approximately N binary searches.
Even though the array to search decreases by 1 each time, summing up log N + log (N-1) + ... + 2 + 1 is still O(N log N).
One improvement I'd suggest: Lets say your array in all the numbers 1 through 1 million, and you target is 10. You'd waste a lot of time decrementing the right pointer one step at a time. Alternately, if your target is 1.9 million, you waste time slowly incrementing the left pointer. It would be more efficient to use a gallop search to find the next element to stop at each time.
What's a gallop search?
@@MoogieSRO It's where you jump 1 item, then 2, then 4, then 8, etc..
Basically, you know what a binary search is? Where you know that x is too low and y is too high, so you check halfway between them? And if the middle point is too low, it becomes your new x, and if its too high, it becomes your new y? Well, gallop search is what you use when you have an x which is too low, but don't know where the y which is too high starts.
@@macdjord Ahh I see. Thanks for the explanation!
Why why why didn't I figure that out. Thank you master
Does it point out that it has to be positive numbers in the array?
Somehow this has grown into a Medium problem in LC. You might want to move it to another playlist.
This was genius.
u an actual NEET? i am rn but only b/c i chose a shitty major
i'm trying to get into CS industry after this by doing more leetcode and self-teaching algos
do u have a discord?
my discord is hydro#3651
Haha, technically I am a NEET right now, but maybe not in its true meaning. Good luck with self-teaching, it's definitely possible because many people have been successful doing that.
@NeetCode Can I ask if it would be acceptable to use the same theory behind the first Two Sum question (Leetcode 1) in this problem? Logging the difference between the target and the current number in a hashmap would also work no?
thanks
Thanks
1:49 be careful. The statement says integers, so there could be negative numbers and hence there could perfectly be a combination (l,r) with r>T>=0>l (where l is the first element of the solution tuple and r the second, and T is our target value) such as (l+r)==T.
Great video!!!!!! đđđŻ
Edit: I had misunderstood the brute force strategy. I guess it can also work for negative numbers, too.
Technically a valid point, but if we assume the array sorted, the approach works nonetheless ;)
What if there is duplicate numbers in the array? should we add one more condition to deal with that?
What about a binary search for the complement? Where complement = target - first.
Starting from first, search for the complement, if not available, move on to the next value.
This o(n) as well.
That will be O(n.log n) as binary search is O(log n) itself and you might have to search n-1 times in the worst case.
How did you think of using two pointers? I used binary search and wrote a really ugly code
generally speaking you can use two pointer solutions for any of the various Two Sum style problems
wouldnât it be faster if we cut out the numbers that are greater or more than target as well?
Wouldn't this be similar but slightly more efficient? (assumes 1-based array indexes)
n=# array elements
for x from 1 to n-1
for y from x+1 to n
if value[y]>=9-value[x] break
is value[y]=9-value[x] DONE - FOUND IT!
not more efficient or even viable. consider negative numbers.
This was surprisingly easy. I doubt it's a real interview question.
Maybe for interns or new grads
for phone screen interviews and this is not the final solution. They are actually looking for binary search with two points.
If I got asked this question on an interview, I'd do a backflip
great thank you
Very cool
This challenge is actually medium level now (on leetcode)
Which one js better the hashing way or this one?
Great video. Thanks! I have a dumb question. Why couldn't I use the same method from the first version of two sum to solve this?...
I used the method from the first version and added +1 to returns and it worked fine
This one is sorted, so the first one using this solution will miss the mark
This problem says you must use O(1) space while the Traditional 2sum uses a hashmap
Thanks!
Thank you so much!!
Couldn't you add a check "if r > target r-=1" (if right pointer greater than target number, decrement right pointer)?
why would you compare an index with a desired sum?
@@Kokurorokuko I meant the number at index r, rather than index r itself.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers)-1
while numbers[i] + numbers[j] != target:
if numbers[i] +numbers[j] > target:
j -= 1
elif numbers[i] +numbers[j] < target:
i += 1
return [i+1,j+1]
difficult level changed from (Easy to Medium)
I get that we can use this solution, but why donât we use the Hashmap one pass solution? Is it because we occupy O(n) space and that isnât optimal?
A quick performance increase for edge cases:
Add a conditional that checks for length 2. Given we know that there has to exist a valid solution in each test set (as per instructions), a length of two means you can return those values without setting up the pointers. Also, modifying the original array values to instead be 1 and 2 and returning it will also lower space usage (but keep in mind this is not best practice).
For Java I got a 99.2% runtime and 74% memory using these tricks. And I've found atleast in the case of leetcode that a lot of the easy/med problems can be slightly optimized when the solution is guaranteed to exist by doing this setup.
how would u do either of those? not sure if its just me but I don't understand your explanations >.
@neetcode if happen to read this! THANK YOU FAM!
So are we supposed to come up with these solutions ourselves or are we supposed to just do a bunch of questions and memorize these solutions and use them on similar questions that come up with different wording??
amaaaaazing
If you use binary search to find the starting point for pointer two you get a significant perf boost. Further, the statement you may assume that each input has exactly one solution means that the elements of the solution are unique, which means you dont increment the pointer by 1, you find the next unique value by binary search. Meaning the solution is log(n).
This does multiple binary searches though, so it will only be O(log N) if the number of binary searches is constant, i.e. the number of searches doesn't increase as N increases.
I don't know if that's true for the average case, but you can find a worst- case example that is O(N log N).
When nums = [1,3,5,6,7,9,11] and target = 13, the left and right pointers alternate between which one has to move. It ends up doing N binary searches.
Even though the array to search decreases by 1 each time, summing up log N + log (N-1) + ... + 2 + 1 is still O(N log N).
Why don't you remove 10 in the first iteration and 7 in the second one?