TWO SUM II - Amazon Coding Interview Question - Leetcode 167 - Python

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.

[illuminado]

high quality explanations, honestly way better than most channels on this site. great work

[Gabriel-cdjx]

The beauty about these challenges is that the code is simple but the logic to get to an optimal solution is quite complex.

[canete_code]

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

[vetoramireziii]

I like how you also included the brute force solution. Thanks a lot!

[MegaWinner]

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<b, but somehow after running the algorithm we do not get any solution.
Now consider that at each step we only move the upper pointer down 1 index, or lower pointer up 1 index. Which means at some point before the alogrithm terminates, one of the pointers must be at a or b. Since we only moved the pointer by 1 each time it is either the lower pointer at a or upper pointer at b.
If the lower pointer at a, then the upper pointer must be larger than b since it is the first time either pointer hits {a, b}. Then sorted array implies that the current sum must be larger than required sum, so we will keep moving the upper pointer down by 1 until it eventually hits b.
Vice versa if upper pointer at b.

[joshuao]

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.

[prabinlamsal]

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).

[theornament]

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.

[TheZayzoo]

No way amazon asked this simple question 😂, I took 2 coding interviews with amazon and its always matrices or something difficult.

[FluidEnjoyer]

Really clear explanation with no useless information and a smart solution on top of that.👍

[DanielSmith-ujrr]

Hey There! I always look for your solutions in the YouTube 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.

[iworeushankaonce]

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)

[MinhNguyen-lzpg]

Brilliant mate, consistent quality explanation from the start!

[ardemus]

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 <= the target. This could eliminate thousands or millions of checks on a real algorithm with a large data set.

[infinitefretboard]

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.

[regnam]

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.

[adveshdarvekar]

It feels so good when you solve using the exact method I was thinking about!

[AdityaSharma-wgrj]

best LC python solutions. I recommend this to everyone!

[gorsama-]

The two pointers solution was actually pretty neat 👌

[jst]

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)