Two Sum - Leetcode 1 - HashMap - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@mikemihay]

is not slow, is just perfect for non native English speakers

[@prasanthn8576]

osm dude!

[@tnmyk_]

Hi, what exactly is the Blind 75 curated list? what does Blind mean in it?

[@ramkrishnasharma3814]

@@tnmyk_ you should be able to do the questions on that list even if you're blind

[@tahirraza2590]

Thanks a lot man!!

[@BirinderSingh]

Interview tip: If the interviewer asks something and you don't know the answer, just answer "a hash map should do the trick". 90% success rate 70% of the time.

[@binitrupakheti4246]

And then they ask you to show it on code

[@stovegamesgames6917]

math is not mathing

[@mohdquamartyagi331]

​@@stovegamesgames6917because hash is hashing

[@olamilekanadebowale2804]

@@stovegamesgames6917 dude its a joke

[@manjinderrandhawa5094]

I literally tried it couple years back and I can confirm that it DOES NOT work 🤣

[@kaixuanhu8332]

leetcode 1: Where dreams start

[@napallday9334]

leetcode 2: Where dreams end

[@jasontsai8596]

no one care your comment

[@inAndOut323]

😂😂

[@cimbot]

@@napallday9334 LMAO

[@hieunguyentrung9434]

hello world of leetcode

[@rain-er6537]

As someone who is new to python, the most confusing part was people calling it hasmap and not dictionary. It only clicked for me when I realised that it is just a dictionary.

[@LordPrivate]

Same here, if this was just said it the many coding videos I watched regarding 'hashmaps' it would have saved me a lot of time hahaha

[@MyBinaryLife]

a hashmap is a ubiquitous data structure used by essentially every programming language. a dictionary is not really something outside of python, but is pythons implementation of a map. Thats why they are biased towards using the term hashmap in the coding videos.

[@TrendyTales-ep9yq]

yes even I used to confuse myself with enumerate

[@hellowill]

@@MyBinaryLife C# also calls it Dictionary

[@lalitmali555]

video is helpful. one advice: -don't put the next video link/thumbnail at the end of the video. it covers the code part. if you want to put then add a 10-sec blank screen at the end and put there.

[@tim895]

Thank you NeetCode for the incredible explanation videos, and the BLIND-75 playlist particularly!! I can confidently say that your videos were an integral part of me being able to get an exciting new position with a global tech company. I'll definitely be supporting your channel through Patreon, and looking forward to your future content!

[@AizenSosuke10000]

What's meant by BLIND 75???

[@ayush51379]

@@AizenSosuke10000 BLIND-75 PLAYLIST: kzbin.info/www/bejne/gX3PiXZ8fJqHpKM

[@senpie-i1f]

something else that's worth mentioning is that there exists a O(n log n) solution. this obviously is inferior to the average case O(n) performance of a one-pass hash table, but it's worth mentioning. this is from the CLRS algorithms textbook, exercise 2.3-7. basically, the procedure is to first perform a merge sort on the array, followed by a binary search of the complement of each element. the merge sort takes O(n lg n) time, and performing a binary search (log n time) on n elements takes O(n lg n) time. thus, the entire algorithm takes O(n lg n) time.

[@nicolasgoosen5142]

How do you keep track of the original indices in this case? Remember also, that the array [a, b] returned must be in ascending order.

[@SaurabhGupta-ei2hl]

@@nicolasgoosen5142 also if we copy the entire vector then it will take extra memory + time

[@gastonseneza45]

@@SaurabhGupta-ei2hl Once you sort why not use two pointers instead. That'd be done in one pass.

[@limwilfred1336]

@@SaurabhGupta-ei2hl Runtime: 41 ms, faster than 96.25% of Python online submissions for Two Sum. Memory Usage: 14.4 MB, less than 45.03% of Python online submissions for Two Sum. Just tried it. In Python as well.

[@limwilfred1336]

@@nicolasgoosen5142 after finding the number, find the index based on the original list. so make a copy before u sort.

[@shanekim10]

I can't thank you enough. I've never seen anyone making the explaination this simple/easy/concrete

[@bigazTV]

I know how to solve a lot of leetcode problems but I don’t know how to explain in detail what I’m doing during interviews. Essentially idk how to sound more technical and I gotta say these videos have been a big help.. I also started helping friends(forcing them to do leetcode session) so I can improve lol

[@BahnMiFPS]

can i be that friend yo lol

[@licokr]

I stored all the pairs of indies and values and sorted the array and used the two pointers that starts at the each edge of the array. More comlicated and inefficient. This solution is really nice. Your ability to figure what you have to do to solve a question is really amazing. I've learned a lot today too! Thanks a lot!

[@jixster1566]

God, Im a SWE but suck so bad at these leetcode questions

[@som6553]

lol

[@IhsanMujdeci]

It makes sense, there are 2 values needed for a sum. One of the values has to appear after another. Cool work around.

[@whimsicalkins5585]

I solved "Two Sum" a gazillion times. Still every time I start afresh, I fold up like a cheap Walmart chair. As @NeetCode says, only way to solve these questions to keep grinding.

[@3zoabdullah333]

leetcode make me feel so dumb, how do people come up with these solutions?

[@juandager5220]

A lot of practice and experience. Crawl before walking. Walk before running.

[@atomix2933]

How is this considered easy?

[@kvelez]

class TwoSum: def summation(self, nums, target): prevMap = {} for i, n in enumerate(nums): diff = target - n if diff in prevMap: return [prevMap[diff], i] prevMap[n] = i return

[@ndemazizou9866]

can you please explain this part? return [prevMap[diff], i]

[@pleps3098]

@@ndemazizou9866 that returns the index of the two numbers that you are looking for. prevMap in this example is a dict, and prevMap[diff] is giving you a number(int value). i is defined in the for loop, so i also returns an int value.

[@vonmansfeld2244]

Thank you so much. I've had no idea except brute force but your solution is so easy!

[@HarimaKentaro]

Nice, I only got it through the comparison with hashmap way. Your one way pass was really good and informative :) had to watch and compare codes for some time to better understand. Hopefully, I get used to recognizing these patterns or techniques to do things and use it next time.

[@tanweermahdihasan4119]

Amazingly neat explanation and walkthrough. I have one quesiton. In 7:03, you have created a dictionary with values --> index mapping. While this make things easier in later part, but do not you think that creates a possibility of duplicate keys?

[@nicolasgoosen5142]

It's safe to ignore, or just overwrite, duplicate keys. For example, if you've got to the point of overwriting the key, you've already proven that it's not a potential solution for current key, so current key * 2 isn't == target, i.e. having two of them isn't going to help you find a solution any more than having one of them, so just discard duplicate values.

[@tanweermahdihasan4119]

@@nicolasgoosen5142 Excellent, thanks Nicolas.

[@coderecipeofficial]

On a funnier note, Leetcode 1: Where dreams start . . . Leetcode 2: Where it ends... Story of most coders on leetcode 🤭

[@blunygeorge]

You could briefly explain how hashmaps work to make this more meaningful. Without that information people may think that doing similarly what you first showed but always checking the elements before the current index is the same as using a hashmap.

[@yashasmn245]

Python dictionary data structure

[@ogreeni]

Right. I didn’t like this explanation.

[@NIKOS.koukos]

I have extensive experience in implementing and operating key:value patterns across a wide spectrum, ranging from custom hash functions to simple Kafka partitioning. It's been a while since I refreshed my understanding of such problems, so I've started practicing on platforms like LeetCode. I recognize that while this may seem like a straightforward problem, it took me some time to grasp the logic behind the reverse key:value pattern solution. I'm sharing my perspective for those already familiar with hash logic (key:value) to potentially aid in understanding such problems in a more generic manner. Let's disregard the value:index relationship and focus solely on the key:value pattern. In any hash-based operation, the goal is to find a key to return the associated result (value/s). In our scenario, during iterations, we're searching for a value (a number). This means that the value becomes the key in our hash map, and we obtain a result based on the problem's description, which happens to be the 'index' or the key of our original array. In any problem, the objective is to search for one or more keys and obtain a result. In our case, the crucial aspect is that the result should correspond to the 'old' keys. So in any scenario where you're utilizing a hash map, your primary focus is on what you're searching for and what the desired result should be.

[@darylthomas7317]

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i,num in enumerate(nums): for j in range(i+1,len(nums)): if i < len(nums)-1: if nums[i] + nums[j] == target: return [i,j] else: return [] I did this brute force, and it is at 44ms and 14.2MB memory. I do not think hashmaps are useful in a higher level language like python which runs c underneath. Maybe c++ or java are able to leverage it due to proximity to the assembly. The hashmap time was 60s right?

[@nicolasgoosen5142]

Even though your brute-force solution of O(n^2) technically outperformed the O(n) hashmap solution, it'd still crash on larger inputs, where the hashmap would continue running reasonably well. I'm pretty sure that LeetCode intentionally *don't* test your code on 10^9 cases tailored to worst-case scenarios (the solution pair being the last pair in the array) because they'd tie up their own servers in never-ending loops.

[@minciNashu]

Leet code benchmarks are not consistent, you can submit the same code multiple times and each time get different results

[@vchandra6315]

HI - Thank you for explaining the solution for each coding problem with the visual approach (brute force, how to make it better using the right algorithms like two pointers, sliding windows, etc) and included the coding as well. I am really impressed with it. Thanks again! By the way, do you have the source code for all of the Blind-75 problems (github)? Please let me know.. Thanks

[@NeetCode]

I do have the source, I'll be sharing something on that tomorrow, I think it will be really helpful 🙂

[@vchandra6315]

@@NeetCode Thank you in advance! The way you explained all Interval related coding problems and the solutions(meeting rooms, merge interval, insert interval, etc) really helped me grasp the concept with confidence. You have created an awesome channel. Thanks again.

[@NeetCode]

@@vchandra6315 Thank you so much!! Really happy they were helpful!

[@freddyhaug9379]

Starting over my leetcode grind after a 3 month break and two failed interviews this week. Time to make it count.

[@MrMaskedhater]

How's it going bro?

[@karollewandowski465]

def twoSum(table, target): for i in range(len(table)): for j in range(1, len(table)): if table[i] + table[j] == target: return [i, j] print(twoSum([2, 7, 11, 15], 9))

[@warzonemoments3970]

I did that too but that takes a lot of time compared to the above solution

[@alexanderp7521]

O(n^2)

[@heathergray4880]

"don't need a return out here, but I'll just put a return for no reason" - honestly this is the kind of stuff that confuses newbies

[@t74devkw]

Honestly, if a newbie is so newbie that they don’t know what a return statement does, they should learn the basics of a programming language before attempting LeetCode. This is not a diss, this is an advice.

[@mitalikambli5592]

Your channel is so underrated!! Thank you so much it was veryyyy helpful!!!❤️❤️❤️❤️

[@rishikeshv.m5055]

Thanks for the explanations..Helped me a lot Sir!!

[@NeetCode]

Thanks! Happy it was helpful! :)

[@fm7004]

Brilliant, thank you, I gain more confidence by following your coding instructional videos, God bless 🙏🏻🥰

[@AlexN2022]

Question about the hash approach: in STL at least, we would use std::map as the hash map. To find if a key exists in a map, we would need to use map::find( key ). The complexity of map::find() is O(log( map::size() )). We are doing this N times, so our total complexity seems to be O( N*log(N) ) instead of linear as you seem to suggest. If true, this is the same as sorting the array first, and then walking it from both ends. What am I missing?

[@xinchenz6796]

I think you should just use std::unordered_map here, the time complexity for unordered_map::find() is O(1)

[@balaparanj4355]

You're correct that the C++ std::map operations have a time complexity of O(log n). However, std::map is a tree-based container and its operations are log n because they involve tree traversals. But when we refer to "hash" operations in the context of this problem, we're generally referring to hash table or hash map operations, not map operations. C++ provides std::unordered_map which is a true hash table implementation. The complexity for search, insert, and delete operations in an ideal unordered_map are O(1) (constant time) on average. This is because hash tables use a hash function to directly map keys to buckets in an underlying array, so it doesn't need to traverse a data structure like a tree or a linked list to find an item. So, when using std::unordered_map for this problem in C++, the overall time complexity can be O(n), making the hash table approach more efficient than the sorting + two-pointer approach (O(n log n)) for larger inputs. Here's how you might write it in C++: ```cpp class Solution { public: vector twoSum(vector& nums, int target) { unordered_map num_map; for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; if (num_map.count(complement)) { return { num_map[complement], i }; } num_map[nums[i]] = i; } return {}; } }; ``` This way, the average time complexity is O(n).

[@AlexN2022]

@@balaparanj4355 std::unordered_map trades average for extremes. While expected performance is O(1), extreme performance is now O(N) versus ordered map's guaranteed O(logN). In reality, as measured by multiple concerned parties, using unordered_map is often slower and almost never faster than using the sorted map. In a non-existing ideal world, a hash map is O(1), but in reality we have to deal with hash conflicts, and that cannot be done in O(1). It's a principal problem, not just C++ STL implementation specifics. The difference between ordered and unordered implementations just demonstrates this issue.

[@balaparanj4355]

@@AlexN2022 Yes, you're right. Hash tables like `std::unordered_map` do have an average case time complexity of O(1) for search, insert, and delete operations, but this can degrade to O(N) in the worst-case scenarios due to hash collisions, which means multiple keys have been assigned the same hash. When a collision occurs, a process must take place to resolve the collision, which adds to the time complexity. In reality, these worst-case scenarios can happen but are often rare if a good hash function is used. On the other hand, `std::map` is typically implemented as a balanced binary search tree (like a Red-Black tree) and has a guaranteed lookup and insertion time complexity of O(log N), which can be preferable in situations where worst-case guarantees are more important than average-case speed. However, your point that `std::unordered_map` is often slower and almost never faster than `std::map` may not be universally true. The performance of these data structures can significantly depend on the specific use case, the quality of the hash function, the nature of the data being stored, and the operations being performed. It's also worth noting that `std::unordered_map` can potentially use more memory than `std::map` due to the need to manage the hashing and collision resolution mechanisms. This can be an important consideration in memory-constrained environments.

[@gkof23]

I haven't learn Hashmap yet, but I wanna try out Leetcode (at least the first problem) Realized I'm lacking something, and looked this up, turns out idk what hashmap is, then I looked into it, also learnt about big O notation. Went back to this video and everything makes sense, including the algorithm at 3:40. Looks like I need to keep leetcode on the back burner for now since clearly I don't have enough fundamental

[@Windows-st3ti]

do you remember the video?

[@Moody0101]

The most optimized solution I could find tbh, Thank you so much :3 I will share it with my friends :3

[@NeetCode]

Thanks! :)

[@saugatkarki3169]

Thanks for everything. When I get the Job, I promise I will give a lot bigger thankyou haha

[@NeetCode]

Thank you so much!

[@justinskaggs7021]

out here loving the tutorial and then you open python and I go blind from the white background😂 love the video tho!

[@hridyepuneetsingh5172]

Well that was a success. As i got understood how hash table works. Thanks 😊

[@ChaosArtist]

Thanks for the breakdown of this solution, very helpful.

[@harrisonooi296]

i swear, the best videos are always the ones that have like the fewest amount of views. thank you so much.

[@izzyr9590]

you sir, is god sent! I used your idea and beat 97% python submissions! I started with a timeout!

[@jhoanmartinezsilva2609]

Without enumerate def twoSum(target, nums): register = {} for k in range(len(nums)): val = target - nums[k] if nums[k] in register: return [register[nums[k]], k] else: register[val] = k target = 6 nums = [1,2,4] twoSum(target, nums)

[@t74devkw]

enumerate is more performant.

[@jesseinit]

How do you get so good to know that the trick of using the subtraction of the value from the target and storing in a hash? Is it by repetition or there is a rule in the book?

[@satyampatel3713]

pattern recognition, you’ll become better more the problems you solve

[@plumbob109]

Great explanation and visuals!

[@MaxShapira2real]

Here is another way to solve this using a simpler approach: def find_sum_pair(numbers: list[int], target: int) -> str: seen_numbers = set() for num in numbers: if target - num in seen_numbers: return f"Found pair: {target-num}, {num}" seen_numbers.add(num) def main() -> None: numbers = [1, 2, 3, 5, 5, 6, 4] print(find_sum_pair(numbers=numbers, target=10)) if __name__ == "__main__": main()

[@luiggymacias5735]

But the question asks for the Indexes not the numbers, with sset it wouldnt work

[@bradleyvazquez]

Im gonna get there bro One day I'll be working at a big company and be getting paid more than 200,000 :)

[@v0rtex-]

yea but that's in python where you can say If in map. In c you have to iterate through

[@mearaftadewos8508]

your explanation is super! but enumerate takes O(n) time so it makes it more expensive than to loop based on the index. like this: def two_sum(arr, t): table = {} for i in range(len(arr)): diff = t-arr[i] if diff in table: return (i, table[diff]) table[arr[i]] = I print(two_sum([1,5,3,6,4,8], 11))

[@user-pt9eo2pu8j]

Using the enumerate function shouldn't make the time complexity any worse as far as I know. Both of these should be O(n)

[@minciNashu]

enumerate provides an iterator, not an entire list, so there's no difference i.e. it's a generator function, uses yield

[@a.j1031]

Is this just as valid? def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums) - 1): if target - nums[i] in nums: return [i, nums.index(target - nums[i])]

[@underflowexception]

Week 1 at new job: Can you please fix the link in the footer? Thanks

[@fardeendingankar7318]

if their is space constraint than we might sort it and use two pointer technique one pointer to start and other to left

[@Jia-Tan]

Sorting the array would be hugely time inefficient. And using two pointers is no faster than just iterating through the array twice, since you either do 2 passes of single operations or 1 pass of double operations

[@natnaelberhane3141]

Fascinating explanation! Thank you. How about using a nested for loop? I see Leetcode says your run time is 60ms. I solved the question with a nested for loop and the run time was 45ms.

[@amateruss]

Wouldn't that yield an O(n^2)?

[@JohnSmith-uh6cs]

This is not optimal. As Russ said, its n^2 for each for loop in your code.You could have sorted it first then searched, but the sort time is n log n. Not fantastic but better than n^2

[@Sabre5106]

Bro I'm fresh out of CS50P, this is the first easy question? WHAT THE HELL IS A HASHMAP BRUH

[@cschipg4688]

JS: function twoSum(array, target) { let map = new Map() for(let i = 0; i < array.length; i++) { difference = target - array[i] if(map.get(difference) !== undefined) { return [i, map.get(difference)] } map.set(array[i], array.indexOf(array[i])) } }

[@shantisuma7738]

bro do u have any reference where i can learn js dsa

[@holiday2147]

Line 7: if diff in prevMap: this also iterates every element when current difference matches with element in prevMap. So this is also ?O(n2)

[@stevelyle3538]

Correction. You first explain populating the HashMap with the array value. Later in the code you demonstrate populating the HashMap with the target-array[i] value. For_what_you_said for ever element in the array tested you are also searching the HashMap; which is just as incremental of a search as is bruteforce iterating over the original array. You are literally tripling up the iterations that otherwise just doubled up. And creating & appending to the HashMap also isn't free such as searching the hashMap isn't free. At what point is a double search loop bruitforce more efficient than a triple search loop with HashMap?

[@TheGreatMind55]

Hello sir. Nice question. I might be late to answer but I'll still do it. Hashmap is in dictionary format. Searching in Hashmap takes O(1). He has used 'if' statement to get the search. So it won't add loops to it. The final time taken is O(n) that's linear

[@chrisstolfa6819]

Hash map is o(1), brute forcing by checking every value is o(n^2) because you're doing a full pass through for each element so it's at worst 16 pass throughs. The last solution here is o(n) since it's one pass through while accessing the hash map is o(1).

[@sahilverma6160]

from itertools import combinations m=9 a=[2,7,11,15] a1=list(combinations(a,2)) a3=list(map(sum,a1)) for p,i in enumerate(a3): if i==m: print([a.index(a1[p][0]),a.index(a1[p][1])]) my solution

[@marianpascu8474]

I do not understand how the return statement does not return the indexes in reversed order, because [prevMap[difference]] should represent the index of the difference, which basically means [3,1], and not the number that is currently being checked under the for loop.

[@PaulJohnson-er9es]

it doesnt matter what order the indexes are returned in

[@HectorC]

I came up with: aDict = {} for i, n in enumerate(nums): if n in aDict: return [i, aDict[n]] aDict[target-n] = i Beats 98.53% of users on memory Beats 62.62% of users on runtime. I'm guessing without the subtraction variable its faster?

[@juandager5220]

Those times in ms are not reliable. They depend on the backend process of the website. Instead, focus in Big O of time and space. Those are more important for the interview.

[@tomcat9761]

8:08 "But I'll just put a return for no reason." 🤣

[@sameerbvk1976]

essentially using hashmap would be o(n^2) only right. I try to do the same in cpp then i would essentially require 2 loops.

[@9Steff99]

I believe there's a small detail missing in this solution: Don't you also need to check if i is already in prevMap before inserting it? Otherwise, we could overwrite our index if the array contains duplicates, but the problem statement asks for the solution with the smallest index.

[@jbn999]

x = [1, -2, 5, 10] tar = -1 for j,i in enumerate(x): #print (tar-1, x[j+1:]) if tar-i in x[j+1:]: print(j,x.index(tar-i)) break

[@8koi245]

Ohhh!! was indeed pretty clever tho rely on the second number instead!

[@vladimirnovacek8854]

I don't get one thing. Why is it faster to store the values to a hashmap and then look if the values are in it instead of looking directly into the list? Like this: if diff in nums[i+1:].

[@nikhil_a01]

`diff in nums` does a hashmap lookup on diff and returns True if it's in the map. You run a hashing function on `diff` and it gives you the index where it will be in the hashmap. So we know exactly where to look in the hashmap. Then it just has to check if it's there or not. Even if there are 10,000 slots in the hashmap we only have to look at 1 of them. Looking directly in the list means you have to search through half the list on average. If there are 10,000 numbers in the list, you search 5000 of them on average. If you're lucky it might be the first element in the list, if you're unlucky you might even have to search all 10,000 of them. But on average it's way slower than a hashmap.

[@n.h.son1902]

I can get this problem solved by initializing a separate hash map but it requires multiple passes. Either way still has the same time and space complexities but I like the one pass solution more.

[@lianjie8871]

Hi I'm wondering that if the for loop iteration has a complexity of O(n), what about the code "if diff in Hash map"? I guess that would be another O(n) complexity and the total complexity will be O(n^2)? Please correct me if I'm wrong

[@chagsssss]

I have the same doubt

[@EricCycles]

hash maps provide a constant time search so O(1) as opposed to O(n) if you use an array. Since each search is O(1), they all aggregate to the same

[@kiethuynh2820]

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashMap = {} for i in range(len(nums)): if nums[i] in hashMap: return [i, hashMap[nums[i]]] neededNum = target - nums[i] hashMap[neededNum] = i

[@zohayer.mehtab]

Thank you, man! I'm starting today for second time.

[@ROHITHKUMARREDDY-b9q]

leetcode1,A journey started today.

[@vihaansharma275]

When you are searching a hash map for a value, doesnt that also increase the time complexity?

[@bad-orange10294]

Because of the way a hash map is set up, checking if a key exists in the hash map has constant time complexity

[@vihaansharma275]

How? doesn't it iterate through it making its time complexity alone O(n)?@@bad-orange10294

[@MaximuskingTO]

@@vihaansharma275 the worst case is O(n), but that rarely happens, so we use the average time complexity which is O(1)

[@vihaansharma275]

how is the average O(1)? Lets say a list of 10 elements existed, the best case would be O(1) and worst O(10), so how is the average O(1)?@@MaximuskingTO

[@MaximuskingTO]

⁠@@vihaansharma275I included a link but youtube didn’t allow me to post it Search: hashmap average time complexity stackoverflow

[@rananiyati4]

Nice explanation! Thanks!

[@abdelballa]

Why is the clever approach superior than just building the complete hash map at the start? Is it because it will likely use less memory?

[@NeetCode]

In terms of Big-O, it's not more efficient.

[@yt-spikegaming7394]

I got new test case like this : nums = [1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1] and target = 3 so for once who are confused u just have to check weather key/val pair with the key you are trying to add already exists otherwise you will get an error that key/val pair with give key already exists

[@pshubhaprasad]

Thanks for these content !!

[@mindset873]

Hi. I have this code here class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)) : curr_sum = nums[i] j = i + 1 while j target or j == len(nums) : break if j < len(nums) : curr_sum += nums[j] j += 1 I was having problem with submission any helps appreciated.

[@balaparanj4355]

The code you have shared implements a variation of the sliding window approach rather than the two sum problem. The two sum problem requires finding exactly two elements that add up to the target, but your current implementation can find a sum with more than two elements. The two sum problem is typically solved using a hash map to track the complement of each element for the given target. If you encounter an element which is already in the hash map, it means you have found the pair that gives the sum equal to the target. Here's how you can modify your code to solve the two sum problem: ```python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hash_map = {} for i, num in enumerate(nums): complement = target - num if complement in hash_map: return [hash_map[complement], i] hash_map[num] = i ``` This code iterates through the input list `nums` and calculates the `complement` of the current number for the given `target`. If the `complement` is found in the `hash_map`, it means we have found two numbers whose sum is equal to the `target`, and we return their indices. If the `complement` is not found, we store the current number and its index in `hash_map`. Please note that this solution assumes that exactly one pair of numbers in the list adds up to the `target` (as mentioned in the problem statement). If there can be more than one pair, or if there's a possibility of no such pair, you would need to adjust the solution accordingly.

[@PawanKumar-tu6ti]

dhanyawaad !!

[@NeetCode]

dhanyawaad for watching ^_^

[@PremPal-uy4nm]

""" My Notes for this problem Special points are marked with "#" which will refer corresponding line in code. Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. """ """ Approach 1: O(N*N) 1.Bruteforce-Just visiting each value and adding with other values of array and checking if sums equal to target. If yes then return the indexes. #2. Making sure that I don't check for previously cheked vallues to avoid some repetition. However in some other techniques where we start second loop from 0 like first loop. There we have to make arrangements to avoid adding the same element to itself. Otherwise there will be an error for specific cases where target and counterpart are same. """ def two_sum(arr,target): for i in range(0,len(arr)): for j in range(i+1,len(arr)): #2 if (arr[i]+arr[j]==target): return [i,j] print(two_sum([3,2,4],6) ) """ Approch 2: O(N) 1.Basically storing all the element of array in hashTable with corresponding original index. Format:- ht={item:index} 2.Afther this We have to go throught each element of array and check if it's counter part exit in hashTable. 3.If No, then we will move to next element. If yes, then return the indexes. * In above algorithm we need to make arrangement for situation wher item and it's counter part can be same. we do this by adding codition in if statemet. Like this:- ht[target-[numsi]]!=i 4.The above problem arises because we make hole hashTable initially and then itterate through array. This can be avoided with small tricky algorithm. -First we visit a element. -Then we check, if this element's couunterpart exist in our hastTable. If not then we add the item with it's index in hashTable. e.g ht={item:index} -If yes, then it means we found item and it's counter part and we return the corresponding indexes. * In this case we don't have to worry about situation wher item and it's counter part are the same item of an array. """ def twoSum(nums,target): ht={} for i in range(len(nums)): if target-nums[i] not in ht: ht[nums[i]]=i else: return (ht[target-nums[i]],i) print(twoSum([3,2,4],6))

[@xx-jk1iq]

how do you check if the counter part exists in the hash table?

[@aadityakiran_s]

Hey so if the elements are duplicates. that is if an array like this exists. [1, 1, 1, 1, 4, 5], target = 9. Then an error would be thrown since we're adding 1 as a key to the HashTable twice. So we have to check if a duplicate exists and skip over it for that case. Is that not correct?

[@justadev____7232]

Unfortunately we couldn't just skip over it. For example if we had an input of [ 3, 3 ] and our target sum = 6. Then our answer would be [ 0, 1 ]. I don't think his answer is accounting for this. That's why I'm trying to find help in the comments too

[@aadityakiran_s]

@@justadev____7232 Yeah. It's not a big deal you'll find solutions everywhere.

[@PaulJohnson-er9es]

This is unnecessary. An error won't be thrown for each new 1, the value at key '1' be overwritten with each new index for 1. This should be fine in every situation, because the only time a duplicate would matter is if its the solution, and in that situation the return would be triggered before any important data would be lost. Basically, any duplicate is automatically not part of the solution unless the solution is one number added to itself. For example: [2, 4, 5, 8, 2, 1] target = 4 Once it reaches the second 2, it will trigger the return before the first 2 is overwritten. If duplicates are part of the solution, they always trigger return. Any duplicates not part of a solution can always be ignored.

[@aadityakiran_s]

@@PaulJohnson-er9es Actually, that depends on the language. C# indeed throws an error. Maybe some languages are just easier for DSA than others.

[@gyandeepkumar4406]

The explanation was very good But can you please code in Java to relate more at the end and when we do ourselves before your code to check if we got it correct or the mistakes please?

[@adarsh601]

I tried to do it just using a list instead of a dictionary (hashmap): def twoSum(self, nums: List[int], target: int) -> List[int]: done = [] for i in nums: diff = target - i if diff in done: return [nums.index(diff),len(done)] done.append(i)

[@gnaneshwaar2594]

Great Video! but a small question.. Why will the space complexity be O(n) shouldn't it be O(n^2)? we use space for the list and the hashmap... am I wrong in the above assumption? can anyone help me around here? thanks in advance :)

[@isws]

basically the list takes O(n) space and the hashmap takes O(n) so the total space complexity would be O(2n) which is the same as O(n)

[@gnaneshwaar2594]

@@isws thank you so much for that!

[@janvichokshi4892]

the complexity of line 7 --> " if diff in prevMap " is O(N) so final complexity would be O(N*N). Instead you can use dictionary method get(), complexity of get method is O(1). Instead of if diff in prevMap Try: if prevMap.get(diff) Also, what if there are duplicate keys ?

[@nikhil_a01]

The `in` is overloaded to work differently for different data structures in Python. It's O(1) for dictionaries. The solution works fine if there are two duplicate numbers. Try it with [3, 3] and target = 6. The problem doesn't allow more duplicates than that. If we had [3, 3, 3] there would be multiple solutions and the problem guarantees a unique solution.

[@xx-jk1iq]

how does the in method in general reduce time complexity? this is what i am having trouble understanding with hash maps. when searching for the complement, don't you have to iterate through the hash table list of values?

[@mohammedabdalmajed3914]

Is it a better solution? for num in arr: if (Target-num) in arr and num!=Target-num: return [arr.index(num),arr.index(Target-num)]

[@adarshsasidharan254]

Your videos almost feel like Cheat Code

[@saitrinathdubba]

Brilliant explanation !! Thank you !!

[@ethanzheng4673]

Beautifully explained!

[@ahmedmaa4380]

This will be sub O(n^2) only if "diff in prevMap" is O(1).. If this operation requires a linear search of the hashmap's keys, this is theoretically as bad as the nested loop checking each element in the array against all others.

[@nikhil_a01]

"diff in prevMap" just does a normal hashmap look up. It's completely standard to assume O(1) hashmap look up. Yes, it can theoretically be O(N) if somehow all your values hashed to the same position in the hashmap. But if you have a good hashmap implementation that is extremely unlikely.

[@draugno7]

isn't how we get the time complexity of the first solution that we calculate iterations as (n - 1) + (n - 2) ... + 1, which is ((n-1) * n) / 2, which approximates n^2 ?

[@shxynh]

Sir, Thankyou thankyou thankyou so much.., This video was really helpful. 💯🥰

[@akshay8675]

Bro fantastic video. Thanks a lot.

[@jen-lichen8163]

Thanks for the crystal clear explanation. My question is, I feel this approach is a one-pass hashmap. I am wondering would it be possible to implement Python in two-pass hashamp as that in the solution with Java? Thanks!

[@NeetCode]

Yes, a Two-pass solution is also possible in Python, and i think the code is pretty much the same as in Java. For the first pass, you Map each num to the index. The second pass you search for the nums: num1 + num2 == TwoSum, and make sure that num1 and num2 have different index.

[@jen-lichen8163]

@@NeetCode Thanks so much! I'll see if I can modify that with your suggestions! Appreciated!

[@londonching3343]

so i was laid off recently and decided to begin learning python with cs50. currently on section 4 of cs50 and I don't really understand the code behind solving this problem. hoping finishing cs50 will be enough to get up to speed!

[@emresutmen273]

Thank you very much man one lady was not explaining why not setting the map before we check the complement for first time. And I was go crazy why the fuck she did that etc for an hour.

[@dmitrykim3096]

What if we sort the array and use left and right approach

[@DrifterXx22]

its ordered array of integers - not unordered

[@EnriqueMoranG]

Sir, why is the last step like that? shouldnt it be: prevMap[i] = n???

[@ventin75]

i = index, n = num

[@marinrusi7835]

@@ventin75 but isn't index actually value, and value actually index ? shouldn't it be the opposite prevMap[n] = i ?

[@varsithvarshu5958]

That's cool.but the time complexity can be o(n^2) cause , for loop taked o(n) and "in" operator in python takes o(n)...Then the time complexity will be o(n^2)💀...the solution might be ""'try: if hasmap[diff] : Return Except: Update hashmap""" Am I right?

[@affenkratzer]

i never knew there was a difference between python and python3 till now

[@luansouzasilva31]

What's the difference between using the "in" keyword over a list compared to a dictionary (hashmap)? I thought that this method does iterate over an iterable object such as a list. This means that "if number in list" requests an iteration over the list, which would take the processing complexity to O^2. But what happens if I instead use a hashmap? Why does the processing complexity become O(n)?

[@LunaFlahy]

the problem requires to return the index of the val. First you need to iterate over the list to find the diff, which costs you O(n), based on that, from the next index, you are going to iterate over the list to find the index of the diff, which coast you O(n). Since this is a for loop, so O(n^2)

[@ZSonnenblick]

the difference is in the datastructure and how different structures are designed to better handle different operations. a hashmap is extremely good for lookups. if you want to check whether an element exists in a hashmap its only O(1) compared to a list where a lookup costs O(n). the idea of using a hashmap is so that when you iterate through the list, you check if the counterpart exists in the hashmap and you can make that search in constant time.

[@sangpark7656]

how can diff in prevMap? Isn't prevmap = {} at first so it is an empty string? How can we assume that values are already contained here?

[@x0stardust-x2e]

In the beginning it is empty, but the elements are getting added to it when the difference is not found in the HashMap.

[@andys2972]

Which Python IDE do you recommend?