What's going on, guys?
Andy here and we are going to solve my first ever interview question, which is only good and it is
called to some.
Now, this question is still asked very often at companies like Google, Facebook, Amazon, and we
are going to solve it from scratch and make sure you stick until the end of the video because they have
a very special Christmas giveaway just for you.
Let's get it started.
And given an array of integers, we should return in, this is of the two numbers such that they adopt
a specific target.
You may assume that each input would have exactly one solution and you may not use the same element
twice.
Well, this is to make the problem with simpler, because we will solve a version in which we will count
how many pairs of elements there are in disarray who are not together to a specific target.
Let's look at our example to Seven-Eleven 15.
And the target is nine.
And we find a zero and one positions.
Two plus one equals nine.
Right.
So pretty straightforward.
Let's jump resorption.
All right, guys.
Pretty obvious that we have a brute force solution for this problem and it's going to be in big of M
squared.
We will make two nested for loops and we will try each pair of indices, any of those Sollom together
to our specific target.
We return it and stop execution, if not in the end.
We are going to return minus one.
But we have exactly one solution.
So no need for this problem.
But if we want to get to the optimal solution, which is linear time, we can't fix both of those indices.
We can fix only one of them.
Right.
So if we call this in, this is I n g we are going to fix the G index.
And we know the value basically of the second element, which is nums of G.
And because we know the target, we know the value of the first element.
Right.
Is going to be target minus nums of G.
And we should only see if there is some index in which that element is equal to our wanted value.
And if it is, we make a pair from this two and we return the solution.
If not, in the end, we return minus one.
But here is not the case because we have exactly one solution.
So let's write the code for this is actually super obvious.
Now, what is our favorite associative container in C++?
It is always the on order map, right?
So I'm going to define here and unwatered map of integers and integers.
So I'm basically associating the value of the element to its index.
Right.
So in an end and let's call it the value to index and we will iterate through our vector.
So we have J.
We are fixing the G, which could start at position one J less than month that sites and J pass.
Pass.
Right.
But before this we should add into our unordered map the element that index zero.
So then to index o nums of zero each is going to be zero.
Perfect.
Not when I'm fixing this g I should try out.
So I want to see if there is the target minus nums of G value in my unordered map.
So how do I do this.
Using the find function val to index dot find of target minus nums of G.
If this is not equal to nums that end.
Right.
This means it exists.
And if it exists, I should return the pair form by these two indices.
So I shall return.
A pair formed by the first index is well to index of target minus nums of J.
And the second one is obviously going to be J.
We just got afterwards.
I should insert this element into my honor, that map, because now this is a potential first index
for another future date.
Right.
So I would have here Val to index of nums of J.
To be equal to J.
Right.
Which is perfect.
After that I shall return here.
Let's say an empty pair because lit code wants to make sure if you have a non-voice function that you
return something.
In either case.
Right.
So even if we will always have a solution so we won't get here, we should return something just to
make sure it works.
Right.
So submit this.
Let's say fingers crossed.
And it's a success.
Perfect.
That's all first of the major two percent, which is really great.
All right, guys, we have sold to some interview questions, still asked super often by Facebook,
Google and Amazon.
And now I have for you two follow up versions, which are the four some in which it is basically the
same problem.
But you have to find Foord numbers.
We have a specific sum.
And then even in the six time, you should find six numbers which are up together to a specific target.
Now, I want you to solve these problems as good as you can.
So in the optimal time complexity you could fight.
I wanted to write this time complexities and the solutions in the comments shared as we do on Facebook
and for the Christmas giveaway.
My special gift for you is that I will choose randomly from the comments and from the shares of Facebook,
a special winner.
And we are going to have a one on one call on Skype or whatever, topping Digitas.
And as always, guys, if you find this content valuable, make sure you support the channel.
Hit that like button.
Hit the subscribe button and they can be just another.