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.
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!
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.
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.
@@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.
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.
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!
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
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))
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.
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.
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()
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
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.
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.
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?
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.
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.
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?
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.
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
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)
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 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.
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?
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).
@@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.
@@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.
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
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?
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
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])]
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))
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.
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.
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:].
`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.
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?
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
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).
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
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
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?
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.
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
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.
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?
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
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.
""" 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))
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.
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
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
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?
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.
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.
"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.
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 ?
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.
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?
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.
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.
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)?
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)
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.
