ฝัง
- เผยแพร่เมื่อ 25 พ.ย. 2019
- In this episode of Python Programming Practice, we tackle LeetCode #1 -- Two Sum.
Link to the problem here:
leetcode.com/problems/two-sum/
If you don't know Python, you can learn the basics of Python for data analysis using this guide I created on Kaggle (DataDaft video series forthcoming): www.kaggle.com/hamelg/python-...
Python Programming Practice is a series focused on teaching practical coding skills by solving exercises on popular coding websites. Note that the solutions seen here may not be the most efficient possible.
I am not going to provide the full code in the video description for this series, since copy and pasting solutions is not in the spirit of doing coding exercises. It is intended that the video will help you think about problems, approaches and how to structure solutions so that you are able to code up a working solution yourself.
⭐ Kite is a free AI-powered coding assistant that integrates with popular editors and IDEs to give you smart code completions and docs while you’re typing. It is a cool application of machine learning that can also help you code faster! Check it out here: www.kite.com/get-kite/?... - ภาพยนตร์และแอนิเมชัน
I've seen 100 vids on this two-sum problem and it just never clicked with me. I just dont think people could teach it in a way that I would understand. This short video of yours very clearly explained it and I finally understand now. This was a big brick wall for me so it feels amazing to finally get through it.
Have you started on medium problems yet. And how are the easy problems to now, 4 months later.
I know that feeling
literally same feeling brother
This is great content. Your explanations are clear and logical. Thanks
Great video with clear explanation on every concept. Amazing!
Amazing explanation, I understood for the first time after watching many videos
Thank you for sharing the videos. keep going and I'm purely subscribing to your channel just for leet code problems in python.
This is an awesome walkthrough of coding !! Just a quick question.. Do we need the elif in 2nd solution ? Can't it be within for .
Great explanation, i needed it thank you!
This is great!
This is fantastic content thank you!
This is amazing. You are awesome
thank you for such a nice way of doing and explaining the problem.
Glad you liked it! I'm planning to do more videos like this in 2021!
@@DataDaft waiting 😊
sorry but i didn't understand the code/problem statement.
The second solution was highly efficient
Thanks you, I understood :3
def twoSum(self, nums: List[int], target: int) -> List[int]:
numToIndex = {}
for i in range(len(nums)):
if target - nums[i] in numToIndex:
return [numToIndex[target - nums[i]], i]
numToIndex[nums[i]] = i
return []
def twoSum(array, target):
for x in array:
if target - x in array and target - x != x: return [array.index(x), array.index(target - x)]
easy 3 liner
That works for distinct numbers but not if the numbers that add up to the target are the same. If the array is [2,2] and target = 4, it should return [0,1] but your function returns [] instead.
you're right. it should be index(target-x) != index(x). my bad
In the 2nd solution, how does Python find out whether the value is or is not in the dictionary without looping through the dictionary somehow?
Good question Jimmy.
Dictionaries in Python are implemented as hash tables under the hood, which allow you to look up whether an item exists in the table directly in constant run time instead of having to go through every element one at a time to check membership like you would with a normal list or array. Basically, the keys or index values for a dictionary are passed through a complicated "hash function" which assigns them to unique buckets in memory. A given input value for the key or index will always access the same bucket when passed through the hash function, so instead of having to check every value to determine membership, you only have to pass the index through the hash function and then check if anything exists at the bucket associated with it. The drawback of dictionaries is that they are not ordered and require more memory than lists.
What about traversing the list, subtracting the number at the current index from 9 and then searching the list for the complement?
Each search of the list takes O(n) time, and u have to do this for every number in the list. This works, but isn’t the most efficient solution.
other videos in yt looks like they memorizing the code and faking like the they thinking and coding , but this one looks legit
hey, but seen = {} is an empty string at first. how can it be assumed to contain?
Thank you sir ❤
Aren’t numbers from 2nd loop being used more than once?
Great video thank you. I paused and thought about this for a while and didn't come up with the dictionary lookup.
Hashmaps (dictionaries) are very useful for algorithm. They're used a lot.
Whenever you're stuck just think: would a hashmaps help me?
Also, keep in mind whenever input is sorted or not, if binary search can be useful, trees or graphs. Also recursion and memorization
Should we just assume that for the first solution that the two values that sum to target will be consecutive?
def sum_index(arr, i):
if i >= len(arr) - 1:
return 0
now = arr[i]
next = arr[i+1]
sum = now+next
print(f"Sum {i+1}: {sum}")
return sum + sum_index(arr, i+1)
print(sum_index([2,7,11,18], 0))
Your explanations are so precise and easy to understand. Is it possible to make three sum explanation video?
Thanks for the kind words. I will consider making some more python programming practice videos after I finish the last 3 lessons of the Python for Data Analysis series I'm working on.
@@DataDaft Thanks :). can you share me the links for Data Analysis series?
@@Draco-pu4ro th-cam.com/play/PLiC1doDIe9rCYWmH9wIEYEXXaJ4KAi3jc.html
@@DataDaft Thanks for your support
Using recursion:
def twoSum(j=0,i=1):
if (nums[j]+nums[i])==target:
return [j,i]
else:
return twoSum(j+1,i+1)
print(twoSum())
def check_result(myList , target):
if len(myList) target \
or target != myList[i] + myList[i+1] :
continue
list_indx.extend([i , i+1])
return list_indx
myList = [1 , 2 , 3 , 4 , 5 , 6]
target = 7
print(check_result(myList ,target ))
Time limit exceeded
can we do it using list? plz someone send me the code, cz m getting wrong answer using list
superb!.
How would I wun this code in VScode?
Why showing Syntex error
One question regarding the seen dictionary. We create an empty dictionary called seen, however we are then checking the dictionary to see if it contains the (target-current) number. I am confused on how it went from being empty, to potentially storing numbers?
elif
because we add numbers to it eventually. line 10 is where we add to it. the reason we can't make it originally contain the first number for example is because lets say the target is 4 and the first number is 2, then we see that 4-2 is already in the dictionary but that is an error since we need two values, not one. So it's just something done at initialization which helps with that first issue.
I added this code into my Pycharm.
nums = [2,4,6,8,10,12,14,16,18,20,100]
target = 18
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return([seen[target - num], i])
elif num not in seen:
seen[num] = i
print(twoSum())
and I got error:
NameError: name 'List' is not defined
either remove 'List', or replace it with 'list'
Might be an error with pycharm as 'List' should be 'list' on there.
def getindex(n,lis):
for i in lis:
If n - i in lis:
return[lis.index(i),lis.index(n-i)]
Just reduced number of line
I don't understand the 2nd solution.
At first we have an empty dict.
On a first iteration we added "2: 0" to it.
On a second iteration we subtracted 7 from 9 (target - num) and got 2, that we already have in "seen" as key.
But what is going on in the line 8???
As I can see it is [2, 1] because 9-7 = 2 and i on 2nd iteration is 1.
But how are we getting [0, 1]?
Line number 8 is just returning the Index of the previous number and the index of the current matching number.
The first iteration stores {'2' : 0 } in Seen.
The 2nd iteration will search for a Key = 9-7 = 2, this key exists in the Dictionary.
So it will input '2' in the dictionary, and get back "i" which is the index that we stored the key with. Since we stored 2 in the first iteration itself, the "value" of the "key" is 0.
So it will output [0,1]
Can anyone explain me why bulid a new dictionary?
Isn't doing
"if target - num in seen:" in the second solution the same as looping over all the elements of seen? If this is the case, why is the second solution faster than the first one?
Python interpreter probably uses C when you use built-in things like 'in", so it will be faster than making Python itself to loop over the array
its a dictionary which has faster access time than a list
Another solution could be: looping through all the numbers
if you use the loops you would have to do a double for loop and that would be O(n)^2 which is slower than the O(n) which he showed
why did we exclude the last number in 1st loop using -1??
It’s not excluding the last number. Think of it this way.
Here are the numbers being checked:
1 2 3 4 5
The total numbers. Length of list. I.e Len(num) is equal to a list of 5 numbers.
If we are checking the first number against the rest, then that means that we are checking:
1 against 2,3,4,5
In other words. We are checking 1 against the other numbers by looping 4 times. Since 2,3,4,5 are the total of 4 numbers. Another way to represent this is length of the list, which is 5 minus one which is 4. I.e. len(list)-1
The number is only excluded in the outer loop, but it's ok because it's included in the inner loops. Writing it this way (along with the i+1 in the inner loops) is more efficient since you avoid adding the same numbers (not allowed) or numbers you already added. All this without any conditional checks.
If a list has a length of 5, then it has the indices 0,1,2,3, and 4. Using the 1st solution in the video, looping through the example list above would look like the following. With the number on the left being the index in the outer loop, and the numbers on the right of the arrow being the indices in the inner loop.
Outer Loop 1: 0 -> 1 2 3 4
Outer Loop 2: 1 -> 2 3 4
Outer Loop 3: 2 -> 3 4
Outer Loop 4: 3 -> 4
Notice how no valid combination is left out.
why did we not loop till the end for the first loop, and did the len(nums)-1
In 2nd loop, it will start at i+1.
If first loop reach num , 2nd loop start at num+1 .. array out of index
I had the same question but just figured it out. So let’s say you have an array of 2,3,5,7,4,8,12,1. If we loop first loop til the end without len(nums)-1 then there will be this case when 1 (of the first loop) + 1 (of the second loop). The requirement is not use the same element twice so…
@@huynhwinnie7383 doesnt matter as long as u start the second loop from i + 1 you will never loop over the same two indices it will just return none
@@basedgod5881 ah thanks for the explanation!!
why -1 in the first loop? Without -1 works as well.
Imagine you have [2, 7, 11, 15]. If you dont -1 the first loop then when you loop all the way to the end there will be this case when 15 of the 1st loop + 15 of the 2nd loop but the requirement said you can’t use same element twice.
It will go to the end of the loop and give you an index error since the last element will be given index+1 on the second loop which will cause the error.
Can you give me your insta id
What DS/a is being used here?
yo mama
@@Sam-yu4vethanks friend
Thanks for this, the way you explained it makes sense. However, when I try to run it on leetcode, I get a syntax error
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# don't want to look at the last index (i = index)
for i in range(len(nums)-1):
# dont need to look at indices we've already seen
# -> i + 1, then go to end of nums
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return([i,j])
This is exactly what I have :(
well I removed type identifiers and it works. Not sure why it's saying Syntax error :/
hey, what's the purpose of enumerate here?
it gives you the index value as well as the number in the list
don't say easy! i only searched it up, cause i was confused why my code wasn't working right
class Solution1:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
def sum_index(arr):
for i in range(len(arr)-1):
now = arr[i]
next = arr[i+1]
sum = now + next
print(f"Sum {i} = {sum}")
sum_index([2,7,11,15])
1. I just don't know the logic from 1st one to the 2nd one. I mean how can we jump up to the 2nd logical solution from the 1st one since I am a beginner for coding. I don't think this idea in the 2nd solution would come up in my mind. That is the biggest problem for me.
2. elif num not in seen:
seen[num] = i
lets take an example, [ 3, 3]. target is 6. at first, since the seen dictionnary is empty, so seen should be {3:0} or {0 : 3} ? I just dont know "elif num not in seen" in the dictionary is pointed to the key or the value. that makes me so confused. Can someone help me to figure this out? Cause I searched all the information which not mentioned like this.
It can’t be [3,3] because the requirement said that you may not use same element twice. So every single element in an array or list must be different
have you studied data structures? it is imperative that you do so.
@@DetectiveConan990v3 not yet. But I have learnt more than then. Thanks a lot.
@@danielsun716 yeah man good luck
I can't understand it 😭
I understand that feeling, that just means you really have to break down the problem to understand it. Walk your way through the code, step by step as if the code were executing in slow motion, then it should make more sense why the code is the way it is.
okay here's how I think of it, you basically go through the whole list and at each time you ask yourself, have we already seen the other number which we need to add to this number to get the target value? if yes, return the two indexes. if not, then keep looking until we come to a number where we have already found the number needed to make the first number add to the target. by the time we get to the second of the two numbers, it is guaranteed that the first number will be in there. btw the solution is guaranteed to be in there. maybe this doesn't make sense or maybe it does idk
i dont understand anything
that's how I feel revisiting this after 2 years and is funny i think i solved this problem before and just forgot
While loop... Pathetic.
U are just copying the code..... Peeky eyes
Yes, I prepare the code ahead of time for presentation. It is impossible to come up with and code solutions to problems as fast as I do in these videos off the cuff.
@@DataDaft reading this was reassuring, thought I was crazy unable to solve it so methodically and smoothly + quickly lol
@@loden5677 if you practice data structures off by heart, you can start to think "hey, I can use an array and implement algorithm x" or "hey, I can use bubble sort then use a hashmap and use this structure"
Python has got lots of data structures, so it's worth learning them and start to think in data structures. Then you can start building algorithms more easily. Java is also a language with lots of good data structures built in, so I'd recommend using java and python to get good with data structures and start understanding algorithms.
The better you understand data structures, the better you smoothly build algorithms based on them.