Python Programming Practice: LeetCode #1 -- Two Sum

Подписаться 48 тыс.

Просмотров 197 тыс.

50% 1

In this episode of Python Programming Practice, we tackle LeetCode #1 -- Two Sum.
Link to the problem here:
leetcode.com/p...
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...
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/g...

Опубликовано:

26 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 103

@GamingNoodle 3 года назад

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.

@UnknownSend3r 3 года назад

Have you started on medium problems yet. And how are the easy problems to now, 4 months later.

@lonestarstatechris 2 года назад

I know that feeling

@jitendrarajde430 Год назад

literally same feeling brother

@sleeptalkenthusiast 2 месяца назад

he literally doesn’t explain anything he’s doing but ok

@maxgriffiths6968 4 года назад

This is great content. Your explanations are clear and logical. Thanks

@NOBOBI1306 6 месяцев назад

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 []

@marcofer1996 2 года назад

Great video with clear explanation on every concept. Amazing!

@VihaanKembhavi-u5y 7 месяцев назад

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

@dapianna23 6 месяцев назад

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.

@VihaanKembhavi-u5y 5 месяцев назад

you're right. it should be index(target-x) != index(x). my bad

@jacobforson2209 2 месяца назад

Am so confused 😢

@jimmymesa 4 года назад

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?

@DataDaft 4 года назад

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.

@kvelez 11 месяцев назад

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

@joshikaran-zm2ju Год назад

other videos in yt looks like they memorizing the code and faking like the they thinking and coding , but this one looks legit

@yowanehakuuu Год назад

Amazing explanation, I understood for the first time after watching many videos

@jaishreeram4177 9 месяцев назад

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

@Draco-pu4ro 3 года назад

Your explanations are so precise and easy to understand. Is it possible to make three sum explanation video?

@DataDaft 3 года назад

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.

@Draco-pu4ro 3 года назад

@@DataDaft Thanks :). can you share me the links for Data Analysis series?

@DataDaft 3 года назад

@@Draco-pu4ro ru-vid.com/group/PLiC1doDIe9rCYWmH9wIEYEXXaJ4KAi3jc

@Draco-pu4ro 3 года назад

@@DataDaft Thanks for your support

@liatris69 2 года назад

What about traversing the list, subtracting the number at the current index from 9 and then searching the list for the complement?

@nourdouffir 2 года назад

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.

@TheMouseJerry-du1md 3 месяца назад

Thank you for sharing the videos. keep going and I'm purely subscribing to your channel just for leet code problems in python.

@Kerogas_ 9 месяцев назад

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]?

@HarshvardhanKanthode 8 месяцев назад

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]

@9362boy 3 года назад

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 .

@priyavardhanpatel6155 3 года назад

thank you for such a nice way of doing and explaining the problem.

@DataDaft 3 года назад

Glad you liked it! I'm planning to do more videos like this in 2021!

@priyavardhanpatel6155 3 года назад

@@DataDaft waiting 😊

@sumantwankhede 2 года назад

sorry but i didn't understand the code/problem statement.

@senshai1267 Месяц назад

leetcode problem 1 feels like final bosss haha

@bvlmari6989 6 месяцев назад

Great explanation, i needed it thank you!

@michasekua4642 2 года назад

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

@FsimulatorX 2 года назад

either remove 'List', or replace it with 'list'

@Miggy97 Год назад

Might be an error with pycharm as 'List' should be 'list' on there.

@ajm0o 3 года назад

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

@spacegoat_3d801 2 года назад

Time limit exceeded

@xkoredeveloper8422 4 года назад

This is great!

@kosmonautofficial296 2 года назад

Great video thank you. I paused and thought about this for a while and didn't come up with the dictionary lookup.

@greyshopleskin2315 Год назад

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

@Elunicozorro 7 месяцев назад

Should we just assume that for the first solution that the two values that sum to target will be consecutive?

@IDK-kv8ob 3 года назад

This is amazing. You are awesome

@swworn Год назад

i dont understand anything

@TrismegistusH Год назад

that's how I feel revisiting this after 2 years and is funny i think i solved this problem before and just forgot

@kvelez 11 месяцев назад

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

@DeshBhakt588 4 месяца назад

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

@brandiblythcook754 2 года назад

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 :(

@brandiblythcook754 2 года назад

well I removed type identifiers and it works. Not sure why it's saying Syntax error :/

@sangpark7656 Год назад

hey, but seen = {} is an empty string at first. how can it be assumed to contain?

@bubbatheg Год назад

Another solution could be: looping through all the numbers

@pharaoh9483 Год назад

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

@Moody0101 3 года назад

Thanks you, I understood :3

@newyabba5756 2 года назад

Aren’t numbers from 2nd loop being used more than once?

@YouTubeTOS 2 года назад

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]

@phoebeiz Год назад

Can anyone explain me why bulid a new dictionary?

@beb57swatimohapatra21 3 года назад

can we do it using list? plz someone send me the code, cz m getting wrong answer using list

@simparinkasamuel7810 4 года назад

superb!.

@ShubhamKumar-iv7qh 3 года назад

Why showing Syntex error

@wesleyurena2217 Год назад

How would I wun this code in VScode?

@Bingbong420style Год назад

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?

@iroveth6690 Год назад

elif

@DetectiveConan990v3 5 месяцев назад

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.

@lorenagonzales2350 3 года назад

why -1 in the first loop? Without -1 works as well.

@huynhwinnie7383 2 года назад

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.

@Miggy97 Год назад

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.

@anshurana9451 Год назад

Can you give me your insta id

@davidebizzarri9460 8 месяцев назад

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?

@kxadecode 6 месяцев назад

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

@DetectiveConan990v3 5 месяцев назад

its a dictionary which has faster access time than a list

@sangpark7656 Год назад

hey, what's the purpose of enumerate here?

@Sam-yu4ve Год назад

it gives you the index value as well as the number in the list

@ThatWomanIsNotMeAndImNotWhite Год назад

The second solution was highly efficient

@m.c80 2 года назад

What DS/a is being used here?

@Sam-yu4ve Год назад

yo mama

@alfalink98 Год назад

@@Sam-yu4vethanks friend

@IMDash_freak002 Год назад

I can't understand it 😭

@mryup6100 11 месяцев назад

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.

@DetectiveConan990v3 5 месяцев назад

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

@tochimclaren 3 года назад

While loop... Pathetic.

@NaveedAhmed-xt4xk 6 дней назад

bad video

@NaveedAhmed-xt4xk 6 дней назад

give me good questions

@addictedroaster1573 3 года назад

U are just copying the code..... Peeky eyes

@DataDaft 3 года назад

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.

@loden5677 2 года назад

@@DataDaft reading this was reassuring, thought I was crazy unable to solve it so methodically and smoothly + quickly lol

@navjotsingh2251 2 года назад

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

@taenight2359 Год назад

why did we exclude the last number in 1st loop using -1??

@joaquing3263 Год назад

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

@mryup6100 11 месяцев назад

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.

@SanjalaPradhqn 11 месяцев назад

Thank you sir ❤

@amanullahshareef1768 2 года назад

why did we not loop till the end for the first loop, and did the len(nums)-1

@newyabba5756 2 года назад

In 2nd loop, it will start at i+1. If first loop reach num , 2nd loop start at num+1 .. array out of index

@huynhwinnie7383 2 года назад

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…

@basedgod5881 2 года назад

@@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

@huynhwinnie7383 2 года назад

@@basedgod5881 ah thanks for the explanation!!

@matattz Год назад

This is fantastic content thank you!

@danielsun716 2 года назад

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.

@huynhwinnie7383 2 года назад

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

@DetectiveConan990v3 5 месяцев назад

have you studied data structures? it is imperative that you do so.

@danielsun716 5 месяцев назад

@@DetectiveConan990v3 not yet. But I have learnt more than then. Thanks a lot.

@DetectiveConan990v3 5 месяцев назад

@@danielsun716 yeah man good luck