You disrespect FAANG coding questions, and then fail them.. What happens if you are asked for a target which is twice an existing number in the array? What happens if you have duplicates in the array? Consider [2, 3] and [2, 2, 3] with the target 4.
That's because code speed and time complexity far more important in general than some extra memory usage. Even a few dozen GBs of extra RAM are quite cheap compared to a slightly better CPU. For example no one complains that a game occupies 10 GB of ram as long as it runs fast.
I think you can simplify this to a single pass through the array. As you go through the first time, check if the complement of the current value is already loaded in the map. If so return that and the current index. If not, add the current value to the map and continue iterating. This way you’re essentially checking each number against all numbers behind it. Still the same bigO, but you cut the iterations in half.
It would take your tc:0(nlogn) and sc:0(n) but if your sort it and implement 2pointer algo it takes constant space complexity with time complexity beeing O(nlogn)
I used to get really confused when people would talk about 'hashmaps', since I learned everything in PHP and JS. Felt like such an idiot when I realised it's just an associative array 🤦♂️
But what happens if the number you're at is half the target, so when searching if there's a distinct index with that value, your program might just use your current index? For example, if you're at a 3 and your target is 6, you'd have to check if there's another 3 rather than just say your current 3 is in the array (e.g arr = [3,2,1] and target is 6).
What about if the target is 4 and your elem at which u are is 2 ? What if there is more than one Occurance of any number in list and then how will you store the no into dict/hashmap
Lets say there is 3 instead of 7 in the map , and there also a 6 somewhere in it, will the code run first for 9-2 and when it does not find 7 it loop again until it searches for 9-3 to then find the 6?
@JustinK0 it subtract the target from the first element and see if there is a match to the result (of the subtraction) but if it did not find a match will it not perform the subtraction on the second element and so on ...? I hope I explained my request for clarification clearly and thank you for the reply
@@dannyisrael it subtract the target from the first element and see if there is a match to the result (of the subtraction) but if it did not find a match will it not perform the subtraction on the second element and so on ...? I hope I explained my request for clarification clearly and thank you for the reply
@@M4AH1990 I don't think so. Binary search takes log(n) in the worst case scenario not n.log(n) because n.log(n) means that we have two loops with one being nested like this (that's just an example): for (int i = 0; i < n; i++) --for (int j = 1; j < n; j *= 2) Usually you find this complexity in divide and conquer problems. Binary search only requires one loop so it's log(n) not n.log(n) (assuming the array is sorted)
@@thecoolnewsguy It's o(n.lg(n)) because, in the worst scenario, you'd go over each element from the start, and then search for its answer in the remaining of the array. Of course, assuming it's sorted. Well, it could be lower. Because if you're at index i, as i goes from 0 to n - 2, you'll perform a binary search in (n - i - 1) elements. Not sure about the math here, but it won't be as low as o(n), as I explained above.
@@M4AH1990 oh I got you. Yes you're right it's O(n.log(n)) because you will need to iterate through the whole array O(n) in the worst case scenario and then for each element, you perform binary search O(log(n)) so there's a nested loop and the final complexity is indeed O(n.log(n)). Forgive me for my mistake 😁.
You disrespect FAANG coding questions, and then fail them.. What happens if you are asked for a target which is twice an existing number in the array? What happens if you have duplicates in the array? Consider [2, 3] and [2, 2, 3] with the target 4.
I think I would just use the hashmap to find any values before implementing there current value into the hashmap, I.e check for 2 before I implement 2 into the hashmap. Chill out man, part of the journey with the interview is to find alternate solutions to fulfill the criteria the interviewer wants.
And since you got me interested, I’d say the case of duplicate values would still be handled with the same solution. If the target is 10, and the current iteration is on a 5, then I’d simply look if the map has a 5 already.
But you increase time complexity since it it wouldn’t be a hashmap solution anymore. I think most people can agree that the current model of computing pursues speed and doesn’t care about space complexity.
How do you fuck up the solution to the easiest leetcode question? Bruh you make a set and add to it as you iterate through. Its one pass you don’t need to make a hashmap before hand
Since you have to return the indices, how would you do it with a set? Unless you are being imprecise with your language and really mean a hashmap. Also, there's obviously a trade off between readable code for someone seeing this problem for the first time, and the ideal answer you'd want to to give in an interview. You're acting like he gave a O(2^n) solution for this problem. It's literally fine.
@@mujtabarehman5255Yea, I mean. Hashmap. Add to it as you iterate through. If he is trying to be educational and teach others, he should not show a subpar technique for the easiest leetcode problem. It it was something more complicated I would understand
@@destroyer-fr4dz Yeah, fair enough then. I suppose at this point if a company gives you TwoSum then you pretty much have to nail it, given how popular it is. I still think that getting the main idea (ie use a hashmap) across is more important than the ideal code. But on the flip side you can argue that the single loop isn't even much harder, so he should easily be able to show that instead. I get your point.
pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html When calculating Big-O Notation, its customary to drop the factor for each term since they will even out if the input is large enough, so O(2n) gets reduced to O(n) approximately.
Lol this guy and his junk code again. You can easily do this in a single loop by checking for the value in the map and adding only if its not there. These kind of details matter when interviewing esp when its something so obvious
Expected complexity of a hashmap build IS O(n). Pessimistic is O(n^2) - but this happens only when you have a very bad hashing function with a lot of collisions.
I really don't know why FAANG loves Two Sum, Three Sum and so on so much... but they do! So here you go! :)
Is Threesum and so on... also best solved with hashmaps?
You disrespect FAANG coding questions, and then fail them.. What happens if you are asked for a target which is twice an existing number in the array? What happens if you have duplicates in the array? Consider [2, 3] and [2, 2, 3] with the target 4.
Interviewer: How do you…
Applicant: HASHMAP!
So true
😂
That's because code speed and time complexity far more important in general than some extra memory usage. Even a few dozen GBs of extra RAM are quite cheap compared to a slightly better CPU.
For example no one complains that a game occupies 10 GB of ram as long as it runs fast.
I think you can simplify this to a single pass through the array. As you go through the first time, check if the complement of the current value is already loaded in the map. If so return that and the current index. If not, add the current value to the map and continue iterating. This way you’re essentially checking each number against all numbers behind it. Still the same bigO, but you cut the iterations in half.
How in the fuck did I get into the Einstein side of TH-cam shorts
its a dynamic programming approach called sum of subsets
It would take your tc:0(nlogn) and sc:0(n) but if your sort it and implement 2pointer algo it takes constant space complexity with time complexity beeing O(nlogn)
Best part about this one is that you don’t need to sort the array for getting all the pairs😊
you can use the two pointer approach here for the most optimal solution with time complexity - O(n) and constant space complexity
I would have used two pointers for a sorted array, btw unlocked new jutsu😅
Hahaha awesome!
but this wont use if you question asked to return an index too.
Ideally if the array is sorted the you should use binery search where the complexity is Log n. But in other cases your method is optimum.
Actually if it's sorted the best you can do is still O(n)
I used to get really confused when people would talk about 'hashmaps', since I learned everything in PHP and JS. Felt like such an idiot when I realised it's just an associative array 🤦♂️
and people like to call indices pointers -- not awesome when you are used to pointers referring to memory addresses.
Yeah, the quintessential JS object that holds pretty much everything.
Awesome 👏
By the way, sessions are filling up fast for my 1 on 1 tutoring sessions! Email greg.hogg1@outlook.com if you're interested in learning DSA with me :)
But what happens if the number you're at is half the target, so when searching if there's a distinct index with that value, your program might just use your current index? For example, if you're at a 3 and your target is 6, you'd have to check if there's another 3 rather than just say your current 3 is in the array (e.g arr = [3,2,1] and target is 6).
when ur at an element, update the hashmap AFTER u look up target - element
There should be a check for where desired == target. If so, h[desired] needs to be an array with length > 1, and return its first two elements
I thought you’re gonna come with some other solutions, just for fun. Same old same old
Nice
this is whrere we begin
Yes 💯🤣
What about if the target is 4 and your elem at which u are is 2 ?
What if there is more than one Occurance of any number in list and then how will you store the no into dict/hashmap
Correct! You'd need to make sure that the index in the Hashmap isn't the same index as where you are in the array. Awesome thinking :)
Best solution will be 2 pointer approach
You would need to pre-sort the list for this approach to work
Unless the array is sorted, no.
Did it
why not just .index(7) instead of storing a hashmap
still on2 because you are doing 2 loops there
Hashmap & Two pointers 🗿🗿
The one he's using is it brute force approach?since I'm seeing 2for loops nested loop
@@Momentum_animationyes
Is everything solved with hashmap? or is it my recommendation.
because is ordered, you could solve this with two pointers two
Just throw in a hashmap in every problem and you basically solved 80% of it
Lets say there is 3 instead of 7 in the map , and there also a 6 somewhere in it, will the code run first for 9-2 and when it does not find 7 it loop again until it searches for 9-3 to then find the 6?
There is no "loop again" the solution is O(n)
It will iterate once through the hashmap looking for a possible solution
@JustinK0 it subtract the target from the first element and see if there is a match to the result (of the subtraction) but if it did not find a match will it not perform the subtraction on the second element and so on ...? I hope I explained my request for clarification clearly and thank you for the reply
@@dannyisrael it subtract the target from the first element and see if there is a match to the result (of the subtraction) but if it did not find a match will it not perform the subtraction on the second element and so on ...? I hope I explained my request for clarification clearly and thank you for the reply
If you don’t understand how a hashmap works idk man
Brain boom
I tried to answer this simple question in c#. Messed up the declaration of the dictionary and my streak. C# outside of unity is 😢.
Yeah I also had an easier time with it in unity
We can also use binary search
Probably no guarantee that the array is given out sorted.
Also, even if sorted, it would be o(n.lg(n)).
@@M4AH1990 I don't think so. Binary search takes log(n) in the worst case scenario not n.log(n) because n.log(n) means that we have two loops with one being nested like this (that's just an example):
for (int i = 0; i < n; i++)
--for (int j = 1; j < n; j *= 2)
Usually you find this complexity in divide and conquer problems. Binary search only requires one loop so it's log(n) not n.log(n) (assuming the array is sorted)
@@thecoolnewsguy It's o(n.lg(n)) because, in the worst scenario, you'd go over each element from the start, and then search for its answer in the remaining of the array. Of course, assuming it's sorted.
Well, it could be lower. Because if you're at index i, as i goes from 0 to n - 2, you'll perform a binary search in (n - i - 1) elements. Not sure about the math here, but it won't be as low as o(n), as I explained above.
@@M4AH1990 oh I got you. Yes you're right it's O(n.log(n)) because you will need to iterate through the whole array O(n) in the worst case scenario and then for each element, you perform binary search O(log(n)) so there's a nested loop and the final complexity is indeed O(n.log(n)). Forgive me for my mistake 😁.
@@thecoolnewsguy You got it bro 😎
do this on c then we will talk.
I think it will be awhile until we talk then haha
You disrespect FAANG coding questions, and then fail them.. What happens if you are asked for a target which is twice an existing number in the array? What happens if you have duplicates in the array? Consider [2, 3] and [2, 2, 3] with the target 4.
I think I would just use the hashmap to find any values before implementing there current value into the hashmap, I.e check for 2 before I implement 2 into the hashmap. Chill out man, part of the journey with the interview is to find alternate solutions to fulfill the criteria the interviewer wants.
@@victortang9320 I didn't like his disrespectful comment "I really don't know why FAANG love this question so much, but they do".
@@oferron4894 surely when they see your comments praising their questions they will hire you as their new ceo
Probably he said it as a video starter.
And since you got me interested, I’d say the case of duplicate values would still be handled with the same solution. If the target is 10, and the current iteration is on a 5, then I’d simply look if the map has a 5 already.
Couldn’t you just use 2 pointers for this and use them to traverse the array, and removing the extra space complexity of the hashmap?
But you increase time complexity since it it wouldn’t be a hashmap solution anymore. I think most people can agree that the current model of computing pursues speed and doesn’t care about space complexity.
Wont it iterate whole hashmap to search for that number internally? Just curious
No because searching in a hashmap is O(1)
@@absentchronicler9063 ok got it.
I love this comedian :)
Not sure about this. Building a hash map isn't actually free either.
the n should be a different company
Sorry?
This can be solved in logn
You mean n log n
How do you fuck up the solution to the easiest leetcode question? Bruh you make a set and add to it as you iterate through. Its one pass you don’t need to make a hashmap before hand
Since you have to return the indices, how would you do it with a set? Unless you are being imprecise with your language and really mean a hashmap.
Also, there's obviously a trade off between readable code for someone seeing this problem for the first time, and the ideal answer you'd want to to give in an interview. You're acting like he gave a O(2^n) solution for this problem. It's literally fine.
@@mujtabarehman5255Yea, I mean. Hashmap. Add to it as you iterate through.
If he is trying to be educational and teach others, he should not show a subpar technique for the easiest leetcode problem. It it was something more complicated I would understand
@@destroyer-fr4dz Yeah, fair enough then.
I suppose at this point if a company gives you TwoSum then you pretty much have to nail it, given how popular it is. I still think that getting the main idea (ie use a hashmap) across is more important than the ideal code. But on the flip side you can argue that the single loop isn't even much harder, so he should easily be able to show that instead. I get your point.
Just trying to make it readable. You're right, there's slightly better
How is this solution O(n)? If anything i think it O(2n)
pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html When calculating Big-O Notation, its customary to drop the factor for each term since they will even out if the input is large enough, so O(2n) gets reduced to O(n) approximately.
O(2n) is O(n) time complexity
Lol this guy and his junk code again. You can easily do this in a single loop by checking for the value in the map and adding only if its not there. These kind of details matter when interviewing esp when its something so obvious
This is explained so badly, I couldn't understand the solution even though I already know it 😢
Something’s really wrong with your head then.
the fact companies hire people based on these stupid problems boggles the mind.
this won't ever be asked anyway, they actually ask leetcode hards
If time isn't a constraint then we could use two pointers if the array is sorted which probably takes nlogn time
Why? Hashmap Is faster at O(n)
This solution is O(n^2) lol
It's not lol
@@GregHoggOh shit you're right. I didnt realize it was O(1) to check membership in a hashmap. That's cool
Building the hash map is not O(n). If you don't already have the map, then your solution isn't O(n).
Well this is just wrong lol
@@GregHoggu tell him greg u a legend
Expected complexity of a hashmap build IS O(n). Pessimistic is O(n^2) - but this happens only when you have a very bad hashing function with a lot of collisions.
It's only O(n) if you have _no_ collisions. Average time is n lg n. Best possible case is n, but worst possible case is n^2.
Even if there where 10 different loops , it’s still o(n)
If loop is inside a loop than it’s o(n^2)