So in this video, I'm gonna show you five of the problem solving techniques I use the most often when I try to self pretty much any.

According to the problem on, I'm gonna show them to you in the context of trying to solve a specific problem.

So let's get started.

Okay, So here's the problem we're gonna try and solve today.

Ah, you're given to Inter drove race, for example, these two right here.

You're also given our target, which is just a number.

Let's just say that the problem here is writing a function that takes these three pieces of information on returns.

Ah, pair of numbers that you can make from these two race whose some is the closest to the target s.

So in this particular example, you wanna be able to find either this barrel right here three on 20 or this other pair of here five on 20 and that way you'd get the summer off either 23 or 25 on.

That's the closest you can get to 24 because there's no pair off numbers you can make out of these to a race that add up to 24 exactly on here just for simplicity.

Let's just assume that the two given a race always have the same length.

So let's think about this problem.

Okay?

So whenever I try to solve according to be a problem Ah, the first thing I like to do is I like to come out with a brute force solution.

In this particular case, naive brutes for a solution might be to check every single pair, So that would be despair, despair, despair.

And so and then despair, despair, despair.

Just like that, you can check every single pair since there are n squared possible pairs like that.

Assuming that the length of each array is n, uh, this solution would take both and squared in time.

So this is just a simple brute force solution.

But this might be actually all you need, depending on the particular interview s.

So what I would do is I would then ask the interview or something like, you know, this is just a brute force solution, but should I maybe look for a more efficient solution on if the interviewer says Yes, you know, you should look for more optimal solution, then we can go to the next step.

And here is the next step on by late, These are actually the steps I personally took to solve this particular problem s o what I did after, You know, thinking of the boot for solution is I started thinking of a simpler version of this problem.

You know, as we saw earlier, the problem was to find a pair of numbers who's some is the closest to the target.

So I thought maybe a simpler version off this particular problem would be to find a pair of numbers who's some is exactly equal to 24 on.

That's what I started thinking about.

And here's the solution I came out with for that problem.

First of all, we're going to initialize on empty set and then we're gonna go through the elements in the first Ray.

We're gonna put all of these elements in this set, and after that, we're gonna go through the elements in the secondary on as we do.

We're gonna check if there's any pair that as up thio the target exactly 24 in this particular case.

So when we're looking at, for example, this number four right here Well, just ask ourselves, Is there a number 20 in the first degree?

And that's easy to check on just by checking if there's a 20 in the set on.

If there is, that's the answer.

We can just return 20 on four.

And if not, we can just go to the next element, which is one in this particular case, we could just repeat the same thing.

You know, ask ourselves, Is there a number 23 in the set on?

If there is, that's the answer.

And then just go through the entire Ray just like that on this solution, I would take over and in time because we only need to go through each of these arrays just once on.

Once you have a solution to the simplified version off the original problem, you might actually be able to use the insights that you get from that to solve the original problem on dhe.

For this particular case, here's what I thought I thought.

To solve the original problem, we need to just ask ourselves, Is there a pair of numbers that add up to 24?

Exactly.

If there isn't, you know, we just need to ask ourselves the same question with different numbers.

How about 25?

On what?

About 23 so on.

As long as we keep increasing this range pretty much forever, I guess we'll eventually find the right solution on.

You know, each of these steps takes over and in time, so the entire time complexity of this solution would be off x times end, where X is the number of times we need to repeat this procedure in that particular case.

And here, in this particular case, X is just too, because, you know, we will only need to ask ourselves about 24 on there.

Either 23 or 25 on this right here might be actually a pretty good solution.

So I would sort of repeat the procedure as what I did earlier.

You know, I would ask the day we were I think this is a pretty good solution, but should I maybe look for a different solution?

If the interviewer says yes, you should look for a different solution.

Then we'll go to the next step after this.

For the next step, we're gonna use my tip number three, which is to think about the given problem, using simple examples, maybe simpler ones than that, given example.

Using those examples, try noticing a pattern.

So, as we saw earlier, the given example was this one.

You know, it's pretty simple already, but you might want to come up with an even simpler example to make it easier to think about this problem.

So that might be something like this, for example, So as you can see Ah, these air race, each of them has only four elements instead of six.

Let's say, Ah, the target should be 13 on.

When I came up with this example, I thought, You know, these two rays are small enough so that it's pretty easy to compute the sum off every single pair.

And I thought, maybe using that information, I'll be able to spot some kind of pattern.

So that's what I started doing.

First of all, I made a diagram like this one.

A zoo can see, you know, the first array seven for 1 10 is right here on the Y axis.

You might say on 4587 is on this axis.

You know, I just made this diagram on paper and then I started computing the sums off each pair like 74 seven, and 578 and 77 And so and then I realized it's probably better to sort these arrays first before computing the sums so that it's gonna be easier to spot a powder s.

So that's what I did.

As you can see, each of these arrays have been sorted.

147 10 and 4578 On Once I had this on paper, I started computing the sums again.

And once I computing all the sums, it was pretty easy to see what the correct solution Waas.

In this particular example, the target some is 13.

So the correct solution would be any of these four values, right?

Here s O.

You know, the correct solution would be any one of these pears for 877 And so when I saw this, the only sort of pattern I saw was that these solution values seemed to align themselves in this kind of direction.

You know, that's pretty vague.

And I had no idea, you know, if that was gonna be used for at all for trying to solve this problem when I was trying to solve it.

So I kept thinking about this problem a little bit more on.

The next thing I thought was what if we don't know any of the sums for any of the pears yet?

Then we might randomly check one of the pairs.

Let's say four on five right here.

You know, compute the sum 49 on.

I realized that as soon as we know that this is nine, we don't have to check this cell anymore on.

That's because this array right here is sorted.

So if you go to the left and this matrix of sums on this son right here is definitely gonna be less than this.

Some nine, whatever this summits.

So we can mark that as definitely not an answer.

You know, using what's the X right here.

We can do the same thing for this cell as well, you know, because this already is sorted.

If you go up, the sum will be less than nine, which is less than the target.

So this some will definitely not be an answer, because it's gonna be farther from the target than this son.

So we can mark that as X you know, that's not an answer.

We could do the same thing for this cell as well.

For the same reason On after that, we might randomly check this sum.

This pair seven on seven on we find that this is 14.

Of course, using the same logic.

Uh, once we know that this is 14.

We don't have to check these three cells anymore.

And that's because thes three sales, if you check the sum, that's gonna be a greater than 14 which is greater than 13.

So these sums are gonna be farther from the target than this sum that we checked 14.

Okay, so I think this insight is a little bit more helpful than what we had earlier.

But for me personally, uh, just having this insight alone was not quite enough to actually start forming a solution.

So I went to my next step, which is to use some form of visualization.

So we already started visualized in this problem a little bit, but I decided to visualize this problem with a much bigger example, you know, to get and some more insights s.

So let's say that these are just like what we saw earlier the to erase that were given on these air race, Let's say, are already sorted.

So these numbers on that are represented by why go up in this direction?

That's how it started on these numbers represented by X.

Go up in this direction on Let's say that the target.

Sandler.

We're looking for a semi.

So with this example, just like we did earlier, we might check around them, pair on the sum for it.

Let's say we check this some, you know, this number on dhe, This number, whatever they are on the Somme happens to be 60 on once.

We know that at this some right here is 60.

We'll know that we don't have to check these numbers anymore because these sums are gonna be less than 60 which is gonna be farther from the target on the same thing with these numbers on all of these numbers.

So at that point we can make, we can mark all of those sales.

It's definitely not the answer that we're looking for on after that.

We might check this son right here on if the summer off, these pears, this number on this number, whatever they are happens to be 68 since that's less than 70 will be able to tell that we can mark all of these numbers.

That's not an answer.

And if you want, we can just keep going like that s so we might check this some right here on if that happens to be 80 which is greater than 70 will know that all of the use these sales are not the answer that we're looking for.

So let's mark those as not an answer either.

Basically, we can just keep going just like that.

So, as you can see, all of these numbers are less than the targets on.

All of these numbers are greater than the targets on this blue reason on the orange region represent, you know, the cells that we don't have to check because we know that our answer doesn't lie in there.

So I actually made this kind of diagram on paper when I was trying to solve this problem on just by looking at it, I thought, I'm starting to see you know, the same kind of pattern.

Asked what we saw earlier eso just looking at this black region of possible answers I thought this region, you know, seems to form itself in this kind of shape.

On this is, you know, kind of similar to what we saw earlier with a simple example.

So just looking at it, I thought, you know, maybe we can start from the top right corner off this region and then somehow navigate ourselves through this region to find our answer.

I using that video insight, I was actually able to come up with my solution for this problem.

So let me show you that solution right now.

Okay, So let's say we have the same kind of set up as before.

We have the two arrays represented by wise on excess.

And let's say that these are already sorted.

We've already sorted them on dhe.

You know, wise go up in this direction and excess go up in this direction On the target that we're looking for is 70 again.

Now, to begin our search, we're gonna check the top right corner.

Let's say that the sum of the pair, this number and this remember here happens to be 60 which is sincerity, Of course.

Then at that point will know that all of these Paris are not the answer that we're looking for.

After that, we can mark those as not our answer and check this number.

So go down one So and then check this number on.

If that happens to be less than 70 again, let's say 62.

We can do the same thing.

Mark those cells as not our answer.

And then you keep track of this number two.

And after that, we're gonna go down one cell again on if that happens to be greater than 70.

That says 75.

We'll know that all of these cells are not the answer that we're looking for.

We can basically, you know, keep going like that, you know, check this number.

If that happens to be less Ness City, we're gonna mark these numbers as not our answer on.

So So, just like that, we can complete our search in this zigzag kind of weight on as we go through that we can keep track of, uh, the pair that we've seen so far who's some is the closest to the target.

Okay, on once I come up with a solution like that in according interview, what I like to do is, uh I like to tests my solution on a few examples on I highly recommend doing this too.

So let's say that, you know, we're gonna test our solution with the example that we came out with earlier on as we saw earlier with these two, a race on the target of 13.

There were four correct solutions.

These four Paris right here.

So let's see if we can find, you know, one of them with this solution.

So let's set this up the same way as before.

We're gonna, you know, sort these arrays first.

And then, you know, we can visualize them this way.

So the first ray 741 10 eyes sorted and then laid out here on the Y axis on the second array 4587 is sewed it on, then laid out on this axis the first step off our solution.