hi everyone so in this video I'm gonna
show you five of the problem-solving
techniques I use the most often when I
try to solve pretty much any coding
entropy problem and 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 you're given two
integer arrays for example these two
right here and you're also given a
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 and returns a pair of
numbers that you can make from these two
arrays whose sum is the closest to the
target so in this particular example you
want to be able to find either this pair
right here three-and-twenty or this
other pair right here five and twenty
and that way you'd get the sum of either
23 or 25 and that's the closest you can
get to 24 because there is no pair of
numbers you can make out of these two
arrays that add up to 24 exactly and
here just for simplicity let's just
assume that the two given arrays always
have the same length so let's think
about this problem okay so whenever I
try to solve a coding interview problem
the first thing I like to do is I like
to come out with a brute force solution
in this particular case naive brute
force solution might be to check every
single pair so that would be despair
despair despair and so on and then this
pair despair despair and just like that
you can check every single pair and
since there are N squared
possible pairs like that assuming that
the length of each array is n this
solution would take of N 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 so what I would do is I would
then ask the interviewer or something
like you know this is just a brute force
solution but should I maybe look for a
more efficient solution
and if the interviewer says yes you know
you should look for more optimal
solution then we can go to the next step
and here's the next step and by the way
these are actually the steps I
personally took to solve this particular
problem
so what I did after you know thinking of
the brute force 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
whose sum is the closest to the target
so I thought maybe a simpler version of
this particular problem would be to find
a pair of numbers whose sum is exactly
equal to 24 and that's what I started
thinking about and here's the solution I
came up with for that problem first of
all we're gonna initialize an empty set
and then we're gonna go through the
elements in the first array we're gonna
put all of these elements in this set
and after that we're gonna go through
the elements in the second array and as
we do we're gonna check if there's any
pair that adds up to the target exactly
24 in this particular case so when we
were looking at for example this number
four right here we'll just ask ourselves
is there a number 20 in the first array
and that's easy to check and just by
checking if there is 20 in the set and
if there is that's the answer we can
just return 20 and 4 and if not we can
just go to the next element which is 1
in this particular case and we can just
repeat the same thing you know ask
ourselves is there a number 23 in the
set and if there is that's the answer
and then just go through the entire
array just like that and this solution
would take off end in time because we
only need to go through each of these
arrays just once and once you have a
solution to the simplified version of
the original problem you might actually
be able to use the insights that you get
from that to solve the original problem
and 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 and if there isn't you
know we just need to ask ourselves the
same question with different numbers how
about you know 25 and what about 23 and
so on and as long as we keep increasing
this range pretty much forever I guess
we'll eventually find the right solution
and you know each of these steps takes
over n in time
so the entire time complexity of this
solution would be of x times n 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 2 because you know we will only
need to ask ourselves about 24 and then
either 23 or 25 and this right here
might be actually a pretty good solution
so I would sort of you know repeat the
procedure as what I did earlier you know
I would ask the interviewer 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 the 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 these
arrays each of them has only four
elements instead of six and let's say
the target should be 13 and when I came
out with this example I thought you know
these two arrays are small enough so
that it's pretty easy to compute the sum
of 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 the
one as you can see you know the first
array seven for 110 is right here on the
y-axis you might say and four five eight
seven is on this axis you know I just
made this diagram on paper and then I
started computing the sums of each pair
like seven four seven and five seven
eight and seventy seven and so on
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 pattern so that's what
I did as you can see each of these
arrays have been sorted 1 4 7 10 and 4 5
7 8 and once I had this on paper
I started computing the psalms again
and once I computed all the sums it was
pretty easy to see what the correct
solution was in this particular example
the target sum is 13 so the correct
solution would be any of these four
values right here so you know the
correct solution would be any one of
these pairs for 877 and so when I saw
this the only sort of pattern I saw was
that these solution values seem 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
useful 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 and the next thing I
thought was what if we don't know any of
the sums for any of the pairs yet then
we might randomly check one of the pairs
let's say four and five right here and
you know compute the sum for nine and I
realized that as soon as we know that
this is nine we don't have to check this
cell anymore and that's because this
array right here is sorted so if you go
to the left and this matrix of sums this
son right here is definitely gonna be
less than this sum 9 whatever and this
sum is so we can mark that as definitely
not announcer you know using what's the
X right here and we can do the same
thing for this cell as well you know
because this array is sorted if you go
up the sum will be less than 9 which is
less than the target so this sum will
definitely not be an answer because it's
gonna be farther from the target than
this sum so we can mark that as X now
you know it's not announcer and we can
do the same thing for this cell as well
for the same reason and after that we
might randomly check this sum this pair
7 and 7 and we find that this is 14 of
course using the same logic once we know
that this is 14 we don't have to check
these three cells anymore
and that's because these three sales if
you check the sum that's going to be
greater than 14 which is greater than 13
so these sums are going to be farther
from the target then 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
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 visualizing this
problem a little bit but I decided to
visualize this problem with a much
bigger example you know to gain some
more insights so let's say that these
are and just like what we saw earlier
the two arrays that were given and these
are raised let's say are already sorted
so these numbers and that are
represented by Y go up in this direction
that's how it's story and these numbers
represented by X go up in this direction
and let's say that the target sum that
we're looking for is 70 so with this
example just like we did earlier we
might check a random pair and the sum
for it let's say we check on this sum
you know this number and this number
whatever they are and the sum happens to
be 60 and once we know that at this song
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 and the same thing with
these numbers and all of these numbers
so at that point we can make we can mark
all of those sales as definitely not the
answer that we're looking for and after
that we might check this sum right here
and if the sum of these pairs this
number and this number whatever they are
happens to be 68 since that's less than
symmetry we'll be able to tell that we
can mark all of these numbers as not an
answer
and if we want we can just keep going
like that so we might check this son
right here and if that happens to be 80
which is greater than 70 we'll know that
all of these these cells are not the
answer that we're looking for so let's
mark those as not an answer either and
basically we can just keep going just
like that so as you can see all of these
numbers are less than the target and all
of these numbers are greater than the
target and this blue region and 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 and just by
looking at it I thought I'm starting to
see you know the same kind of pattern as
what we saw earlier so just looking at
this black region of possible answers I
thought this region you know seems to
form itself in this kind of shape and
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 of this region and then somehow
navigate ourselves through this region
to find our answer I'm using that bit of
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
setup as before we have the two arrays
represented by y's and x's
and let's say that these are already
sorted we've already sorted them and you
know Y is go up in this direction and X
is go up in this direction and the
target that we're looking for is 70
again now to begin our search we're
gonna check the top right corner and
let's say that the sum of that pair this
number and this number right here
happens to be 60 which is less than
savory of course then at that point
we'll know that all of these pairs are
not the answer now
looking for after that we can you know
mark those as not our uh sir and check
this number so go down one cell and then
check this number and if that happens to
be less than seventy again let's say 62
we can do the same thing mark those
cells as not our answer and then you
know keep track of this number two and
after that we're gonna go down one cell
again and if that happens to be greater
than seventy let's say 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 than 70 we're gonna
mark these numbers
that's not our answer and so on so just
like that we can you know complete our
search in this zigzag kind of way and as
we go through that we can you know keep
track of the pair that we've seen so far
whose sum is the closest to the target
okay and once I come up with a solution
like that and according it to me
what I'd like to do is I like to test my
solution on a few examples and 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
up with earlier and as we saw earlier
with these two arrays and the target of
13 there were four correct solutions
these four pairs 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 array 741 10 is sorted and
then laid out here on the y-axis and the
second array 4 5 8 7 is sorted and then
laid out on this axis the first step of
our solution is checking the top right
corner so we're gonna ask yourselves
okay what's the sum of this pair right
here and that's of course 9 you know 1
plus 8 is 9
and at that point because this is less
than the target well know that we don't
have to check these cells anymore so
after that we're gonna go down to this
cell right here what's the sum of four
and eight that's twelve and that's still
less than the target so we're gonna
we're gonna mark these cells
that's not our answer and then war go
down and then that's 15 which is greater
than the target so we're gonna mark this
one it's not our answer so we can just
basically keep going like that and then
we'll end up going through this kind of
path and if we keep track of you know
the first closest target that we see or
the first spare whose sum is the closest
to the target that's gonna be at this
number right here twelve so from our
solution we're gonna return four and
eight and if we want to return you know
all of these answers we can also do that
just by keeping track of you know the
closest all of the closest pairs anyway
at that point personally I would be
comfortable enough with the solution so
I would find the time complexity and the
space complexity which happened to be of
n log N and of n assuming that you use
an off of n log and sorting algorithm
and after that I would just start coding
and if you're not like 100% sure with
your solution one more technique you can
use is you can say something like I'm
pretty comfortable with the solution so
I think I'm gonna start writing some
code and you know try to observe the
interviewers face if the interviewer
looks pretty happy like happy enough
then you can start writing some code and
for this particular solution if you're
curious about how I would actually
implement it you can check out my
solution code in Python and Java at CES
those of that io / problem okay so
recently a lot of people have been
asking me for advice on how to get
better at problem solving and honestly I
think the best way is to just you know
solve a lot of problems and
ocelots and for that I actually want to
recommend two pieces of resources the
first one is my udemy course called 11
essential coding interview questions and
you know coding exercises this course is
intended for beginners to intermediate
learners and in this course I cover 11
of the most frequently asked questions
with some coding exercises in Python and
Java the second one is this website
called daily coding problem it's
actually run by a friend of mine who I
used to work with at Google and what I
really like about them is the fact that
they provide a pretty detailed solution
for each of their daily coding problems
and that solution is actually only
available in their premium subscription
but I would say even their free
subscription and you know their blog
articles are pretty helpful anyway thank
you as always for watching my videos and
I'll see you guys in the next one