Leetcode Solution - 1.0 Two Sum | Javascript

[Music] hi everyone so you're probably here because you want to prepare for that you know upcoming encoding interview or you're just interested in keeping your coding skills sharp I'm about to just start a series here where we basically go through majority of the questions in lis code and provide a video explanation of all the solutions I know when I was going through the process of going through these li code sometimes just simply reading the solution it's not sufficient for me I think one of the best ways to really understand the question is through teaching so I'm gonna try use this as a good platform to both a sharpen my skills and B hopefully provide a detailed explanation on each solution to problems and hopefully this will help your journey to become a very successful software engineer so what do we stop blabbering and let's go right into the problem so the first question we're gonna go trying to solve is a very easy one it's probably what everyone starts off with and that is called the to some problem so in this problem if we read the question it says given an array of integers return indices of two numbers such that they add up to a specific target so in this statement we have to pay attention to couple of things we have to pay attention to what we're given and what we expect to return back so luckily in lis code they actually tell us that on the right over here already but in the interviewing question this may not be the case so I highly recommend just getting to the habit of identifying what are your inputs and what are you is your expected output so in this case your expected inputs are two things a num spur am which is an array of numbers and specifically integers so not know like decimal etc etc and you're giving a target well a target as being a number as well so what this really means is that you know you're given an array and in that array of numbers you find two elements that add up to this particular target there's another staining here on the bottom that says you may assume that each input would have exactly solution and you may not use the same element twice this is kind of kind of important sometimes when you go through an interviewing process an interviewer may you mean you may sound like oh why are they saying this very obvious assumption or why are they saying these things sometimes this is a very big hint to how to optimize your possible solution so in this case you know we're given we know that okay we don't have to put in an error check to see if there's a valid solution or throw it off because we know by the assumption here there's exactly one solution so we could pretty much don't have to check if the array is size zero or anything like that we can just know that assume that okay cool there's one one there could be a one solution so forget that part the second element question here says like the same element cannot be used twice so meaning that you can't go like okay if the target is like for example four you can't just go oh I'm just gonna get returned zero zero as your solution because that's not valid so why don't we go through the next phase which is trying to understand look at an example what this question is really asking for so in this case here they're looking at okay well given an array 2 7 11 15 and given a target of 9 what 2 elements in here will equal to 9 let's think about it I know in a very easy you could probably say oh yeah it's just the first two elements great that's definitely the solution which is a number add zero and now I'm at one position zero at position 1 2 plus 7 equals 9 great and you return an array of 0 & 1 but you have to think about it how do you actually get this number right so there's if you really want to think of what the simple way you could think about okay I can use either a a brute force way because I could always go all right I'm gonna get I know my first for loop will be like you know checking to I could compare each of these values one by one and add it and see if they check to be nine or go it'll be go like two we'll check with seven that was nine that's great but assuming let's make an assumption like this target is like 17 right it'll be like to you know check here you know not 17 check the next number no that's not 17 but 2 and 15 that 17 that's great then you could do that but two for loops may not be the most optimal solution because that's in time complexity wise that's Oh N squared and if you I probably go later on and talk about time complexity space complexity in a later video but at this point in time that's probably not the best solution but it is a solution nonetheless so let's let's think about other ways of trying to solve this particular problem if you know a little bit of math I think you can probably already know like oh wait I actually don't have to write two for loops I can actually just go through it once and identify whether or not the second number exists because there's exactly one solution we know that right so we could actually just go through it once and know if it exists or not but but how do I do that right so this is where we kind of think about okay what's available to us what kind of data structures available to us and what kind of mathematics is available to us right this is a pretty easy one so if you think about it all I really need to do is actually just take the target maybe as you go through these numbers so trying to store or something right we could store a value and put it on to like some sort of storage location and then look look for the look for that what we're trying to store so what I'm trying to say is like try to think about it what am I trying to store I know they're probably some of you smart guys there already know you can simply just go and look at to get to your target number nine and minus two which in this case would be seven right so we could store it in store the number seven with a second cape with a key that's seven and the index as the index of where that location is so as you iterate you could go and just check this dictionary or check this thing in the storage device right so what I'm trying to do so let's let's get into the code by the way this video is completely raw I don't bother editing it cuz I just wanted to give you the real deal so if some things I slip Bob or some comments I'm just doing in one take so please forgive me but let's just go try and solve this problem right now cool so I think that if I'm looking at doing it this way if we look at time complexity wise I'm only gonna go through this like once and then I'll have I'll know I'm creating like basically a dictionary that stores the you know the target minus the actual value itself so as as a key and then you're pretty much it's an O of n time complexity while on the space-wise is probably gonna be relative sing o of n so I think that's pretty efficient and let's put some code on the screen so you guys probably could fall along a little bit better so the language I'm gonna use right now is gonna be JavaScript if you probably already see in yellow right so I personally like to change it into more es6 context so i change it here move that and do my wonderful error function oops not the question mark but the arrow function alright cool so the storage or the data structure I want to use here is some sort of hash map or just a simple like dictionary or in simple terms just a simple object right so I'm gonna create something called like storage so you can think about this as like as your temporary memory the store the values that we were mentioning it earlier you know the nine minus two and then what do we do here okay cool so what the next step is pretty much okay now we have a storage device now we have to iterate through this particular array so let's do that for let I'm gonna use the more es6 lip syntax index and num dot entries and I can't spell today entries oh cool so what am I doing here so as I iterate through every element in nums right here one two three four I'm basically extracting the index and the actual number out so I can use it to compute and to see what I'm storing in this storage device right so one of the things I want to first check is it the number I'm trying to check is that even containing here in the first place so what I mean by that is if my storage given that particular number right in this case - in this case - does that exists is that undefined in here in this in the first iteration yeah undefined is that undefined if it is undefined oops not undefined actually that was wrong let's think about it well we probably think about the opposite which is let's see if that number we're looking for does that exist in here if it does exist then we can actually return that particular element out so what I mean by that is okay so in this storage in this case - I'm checking to see if it's does not equal to undefined right if it does not equal to undefined it means that oh cool it does exist in here so what does that mean it means that I can actually just return the results now return an array of storage storage store god I can't spell today storage at the number and return the index and that will be your solution but if it's not there if it doesn't exist if it doesn't exist what do you do so that's the thing that we're talking about earlier I'm gonna actually go storage storage at the target - the number will equal to the index so you see what I'm trying to do here it's simply I'm creating an object right example so what i'm doing here i'm creating object and for example we use this musics example as we're trying to do here so as we iterate so the first time we go through this loop we're gonna go hit - right - so in our index in here in this case i'm just gonna say index so you know index will equal 2 - 0 your number will equal to 2 in this first iteration right so what do I do I'm gonna check if the storage I'm just gonna also put the store this is this thing here it's storage right so I'm gonna see like okay well the storage at number 2 does it exist well no it doesn't right because it's an empty object so what are you doing the first element well I'm gonna take the target in this case is 9 so go 9 minus 2 in this case would be 7 that's pretty much my my key right and the value I'm putting in there is the index which is 0 so now I have a key and an index of where that particular element would be right so now it goes in here it's done this statement and it's gonna loop back again and now the index is gonna be at 1 while your value is gonna be 7 and that's gonna do the check again all right so does storage at number 7 does that exist in this in here well we just had something in here yeah it sure does so what I'm doing here right now I was like ok cool so we know that this particular number is defined in the storage well we could just simply just return the current index and the index of the previous number that was stored in here so we're returning what they wanted which is the index of the two numbers that when added together would equal to 9 so let's let's try to run this and see if it solves the problem who's right submit code cross my fingers oh no error what did I do wrong in here right to some I had capital huh bunny funny cool cool alright so we solve the problem so that's it that's your question number one hopefully this is a relatively good explanation I'm gonna try to improve as I go along and I'll take a lot of feedback if you guys want more explanation on how to solve some of these problems if you're free to pay me or in the comment below but this is a working progress I'm no expert and of course this is all in one cut I'm not gonna chop things up if I screw up on screen you're gonna capture the raw thing the real melee romi but yeah that's pretty much it question number one done now wait for next week or maybe tomorrow we'll see further question um to see you guys [Music]

Channel: ThinkFWD

Views: 17,714

Rating: 4.909091 out of 5

Keywords: Software Engineering, Leetcode, google, facebook, amazon, Coding Problem, Javascript, algorithms, Data Structure, Interview Prep

Id: IufUNRCQ37E

Length: 14min 24sec (864 seconds)

Published: Sat Sep 21 2019