This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[JohnWasinger]

Interviewer: How do you…
Applicant: HASHMAP!

[euclid]

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.

[rony]

its a dynamic programming approach called sum of subsets

[mastrassassn]

How in the fuck did I get into the Einstein side of YouTube shorts

[chrisgascoyne]

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 🤦‍♂️

[peacist]

I would have used two pointers for a sorted array, btw unlocked new jutsu😅

[prathamparikh]

Ez way but simple looping are[i] and arr[i+1] just then sum first two check then go for second and third - first ...

[nithish]

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)

[sruthimajhi]

you can use the two pointer approach here for the most optimal solution with time complexity - O(n) and constant space complexity

[Rajib]

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.

[thezenmasterandy]

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

[hit]

Best part about this one is that you don’t need to sort the array for getting all the pairs😊

[אלכסייטברובסקי]

Not ideal you, you can go through the array on one loop and check each time if it is in the hashmap and if not just add it to the hashmap then you will have a real O(n)

[acceleratedofficial]

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

[sumkid]

after learning 2 pointers i already forgot the hashmap approach lol

[observer]

Is everything solved with hashmap? or is it my recommendation.

[khaledalmutairi]

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?

[fortunethedev]

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?

[tashi]

I thought you’re gonna come with some other solutions, just for fun. Same old same old