Java Interview Coding Challenge #2: Two Sum [Java Brains]

in this video we're going to be tackling a coding challenge which involves an array and an expected some there are various variations for this challenge one popular variation that I've seen is something referred to as twosome so the idea is this you're given an array of numbers you're given one number which is the result and what you need to do is find two numbers in that array on adding which is going to result in the result number that you have so I'm going to look at a problem on leet code which is closest to what I'm trying to solve this is this is kind of what it looks like let's solve this variation of the problem today given an array of integers return the indices of the two numbers such that they add up to a specific target you may assume that each input has exactly one solution we may not use the same element twice so those are good points to note if these weren't provided in the question and you were asked this in an interview the first thing to ask would be those things right so am I to assume that you will have one solution or multiple solutions or I might assume that I should use two different numbers that can't use the same number twice those are valid questions to ask the interviewer so here's an example let's say this is these are the numbers right - seven eleven and fifteen the target is nine so you need to find two numbers in the study on adding of which results in nine so these are the two inputs that you're gonna get get an array and a number so here we find that none of 0 and num of 1 so 2 plus 7 add together to get 9 so the result will be those indices it will be 0 and 1 because it's these two which add up to get 9 right so this is a challenge let's look at the pseudocode for how we would approach solving this problem it's add some dummy numbers here so that it's useful for us to practice this is something that I would recommend when you're by porting a problem just add some sample inputs so that you have something to go off of and you have a concrete objective which guides your algorithm so let's say I add some numbers here I'd say 2 3 7 4 and then you're some the result is seven now you know by looking at this that these two are the values that you need right and what you need to do is return and index the result the output so this is the expected result and this is these two are the input and then the output would be the index one which is this guy here and the index three does this guy here so this is what we need to do so how would you go about solving this the easiest brute force way of doing this would be to loop through this array in a nested loop right take each element and then compare it with every other element here and see if adding those two 2007 well no and take this element and compare it with every other element so you're basically having a I equals 0 to n and then J equals 0 to n and then you're comparing array of I plus array of J to check if it's equal to the expected result all right this is the brute force solution does not recommend it this results in the time complexity of Oh n square which is not the best stuff algorithms you don't want to do that unless you have to and in this case there is a better way so what's the better me see if you think about the brute force approach that we did we had two nested inner loop what the outer loop was doing was looking at one element and then in the inner loop using the inner loop we were comparing that element against each of the other elements to see if the sum of those resulted in the expected result that's kind of like that kind of comparison is something that you will have to do you will have to find those two elements but then the problem is that since we are looking at an array given an element given one value to find if that Delta exists in the array you have to look through because there's no other way to me array works is you gotta have that positioning way of looking up things so let's say your expected result is seven and you've got three well guess what you have to loop through the whole array to look for a four but then let's say we find an alternative the the structure that makes it easy for us to look up a particular number right so we're going through this array let's say we look through this just once instead of having a nested array we look through just once and every time we encounter a number we kind of register it in a different data structure which makes it easy for us to look up the value right did you find it too and then we say okay to if you have an empty data structure now I'm just going to save that to somewhere say save it in a set for example you'll find a 3 well 3 I'm gonna check if the Delta so let's say there is under 7 right now 3 requires another number which is 4 ok so I'm gonna say expected result minus the number that I have right now just for I'm gonna say did I encounter a 4 before I'm keeping track of all the numbers that I've encountered in my 1 pass through the array and I'm keeping that in a separate data structure so when I get a 3 I'm gonna subtract it from the expected number I'm gonna give the Delta and say okay is this Delta something already encountered before in my scan of theory when I look at that data structure is there a 4 in there well no the 4 isn't in there so I'm going to move to the next number right so before we had the separate data structure the only way to find that out was there another number was to kind of loop through the whole array but let's say I use a data structure which facilitates lookup in that case I can quickly look up from this data structure and if the Delta exists if I already encountered the Delta before great we can go ahead and return the value if not I'm gonna say ok I'm gonna save this number into this data structure for later right so we need this data structure which is which is handy for looking up things so there are two data structures that come to mind one is a set one is a map a set is something that you can look at and say ok does this thing contain a value it's a very very quick operation to have a set of numbers and say does this set contain that's off one operation right the other option is to use a map in which case again the key value pairs the key is something that you can look up in off one time so which one of those two data structures to be need to use if we use a set we will know what the number is and we will be able to tell ok we've got a match here but then what we end up losing is the position of where we found that thing right so let's say we find at three and we know that okay there is no four yet I'm gonna save this in this data structure and then eventually I'm gonna encounter four I'm gonna look at the Delta three have I encountered a three before yes I've encountered a three now I've got four and three which equals to seven I've got the result now I know the position of four but have lost the position of three because I just have a set which is contained okay that's this number exists or not what I also need to do is not only do I need to save that number that I've encountered before also need to save the position of that number right so when I get a three and I'm saving it to the data structure and you say okay I found three in position index one so that when I eventually encountered a four I look up okay that's three exist yes three exist what is the index in which I found three well that is index one so I can take that index and then returned from my method the position of four and the position of 3 which are the two numbers which eventually make up the result right so because of these constraints I need a map right so this how the algorithm is gonna go work with a map what I'm gonna do is I'm gonna do one pass through this thing it's not gonna be a double loop it's just gonna be one pass through this thing and every time I get a number so they take it to number two and I'm going to say for I equals 0 to n once I get a number I'm going to calculate the Delta which is basically the difference between the expected result let's call this target minus ru Phi okay now if this Delta is something that I've already encountered then they've got my answer so what I need to do is I need to keep a list of all the numbers that I've encountered in this loop so I'm gonna keep this map gonna call this number I'm gonna initialize it to an empty map first and this is the map in which I keep track of every number that I have found so what I'm gonna do is if the map contains Delta then I need to return the current index which is I which is a portion of the sum one portion of the sum the other portion of the Sun is in the map I'm gonna say of Delta and I'm gonna get the value of it because the value is what's gonna contain the index this is gonna be clear when I'm to show you what I'm saving here if it doesn't match here I need to save I'm going to save the map dot put I'm going to put the array of I and then the index I all right so every time when I pass through this array I'm going to save the array element and then the index and then before I directly go ahead and save it maybe every number that I check might be a possible solution so what I'm gonna do is I'm going to first check if then the map already contains the Delta which is the difference that I'm looking for if I already encountered it then the value of that thing is the index of the previous element and then the current elements value the current elements index is I so I'm gonna return these two all right so that's the pseudocode the algorithm now let's write some code and actually test this out so I'm gonna create a Java class here with the main method the name of the classes challenge to to some right and then now in my main method I'm going to call this method here which is public static and I'm going to return another government teacher it's gonna be two elementary and then get to some and then this accepts two inputs what is theory and what is the expected result right that's the inputs to our algorithm I'm gonna make this an injury numbers and then the integer target and now I can call this from my main method let's say in numbers and I'm gonna give the same numbers that we picked in this example all right I'm gonna say 2 3 7 4 and and then I'm going to set the target as 7 and I'm going to print get to some off numbers and target all right now we have the structure ready let's implement the algorithm that we've discussed what I have to do I need to loop through this list so I'm going to have a for loop here is 0 now I am going to get the Delta equals target - numbers off I so this is the Delta that I need to look for now I need to make sure if this Delta has already been encountered so in order to figure out keep a track of what are the numbers that have already encountered I need to keep a map so I'm going to make a map off integer and integer so the key is going to be the value of the number and then the value of the map is going to be the position that the index in the array alright so ok let's call it Ted number equals new I'm gonna make this a hashmap now since I have the Delta I can check how's this Delta already been encountered if this numbers that contains key of Delta that I need to return the right positions right so let me tackle that a little bit it doesn't contain it I need to keep track of this new number and then proceed further right so let's say this doesn't contain now I need to save this value to visit it numbers this is a number but the key is going to be Phi and then the value is going to be the position I so every time I'm visiting a number and putting the contents into key and then the index into the value all right so now that I've done this every time I'm checking for this Delta if this Delta has already been visited the other piece after some if it's already been visited and I need to return a new integer array with two numbers what are the two numbers the first number is going to be the current position which is one part of the sum the second index is going to be the value of this Delta key all right so I'm going to get the value visited numbers dot get Delta all right now if this all goes through and then you don't have any matches well now the question is how do you want to handle the errors you can of course throw an exception or you can return index minus 1 minus 1 I guess I'm just gonna do that I'm going to return in minus 1 and minus 1 this is something that if you're in an interview you might want to ask the interviewer ok what is the expected behavior if nothing you here and now algorithm is pretty much done so if I were to run this but this particularly with this expected target it should match next one and index 3 find out I'm going to right click run as java application all right let me save this into and then I'm going to 0 right so I get 3 & 1 so let's do something else let's say the result is 6 in which case it should print 0 and then 3 all right let's run this it prints 3 & 0 let's try some negative numbers make this minus 2 and then let's say there is also 6 now it should print 0 & 4 all right it prints 0 & 4 all right so that was a quick look at solving another coding challenge which is to get the indices of two values in the array whose sum adds up to an expected some hope this was helpful thanks for watching

Channel: Java Brains

Views: 102,300

Rating: 4.9129987 out of 5

Keywords: java brains, java, interview, coding, coding challenge, java interview, java interview questions, interview coding challenge, interview practice, koushik, koushik kothagal, java interview videos, java interview challenge videos, brains, kothagal, kaushik, tutorial, programming, eclipse, beginner, challenge, java programming, java tutorial for beginners, training

Id: TcsYEnMrnFo

Length: 15min 7sec (907 seconds)

Published: Sun Jul 21 2019