Oh, you know what time it is, don't you?
What's up, guys?
Endi honor media and yeah, it's into interview Sunday.
We are hitting almost one.
Gay subscribers or by the time I post this will probably pass.
That's so.
That's amazing guys.
Thanks for all the love and praise the like button in advance because you know this problem is going
to be amazing.
Don't you press the subscribe button in advance because you know, my content is awesome.
And if you're new to the channel, you want to pass that coding interviews that you're going to have
after you're getting out of the house.
Or maybe remote.
Who knows?
So this one lead board, a one matrix.
It's making us.
Given the matrix consists of zero and one, find the distance of the nearest zero for each cell that
this is within, two, a descent or wait for it, it's actually adjacent one very nice dude, which
is a fan of ours.
A friend of ours.
A subscriber to the channel, which you should do that also.
So press the subscribe button right now.
Told me that it's not called it's not pronounced decent.
It's adjacent.
So this is between two adjacent cells is one.
And let's take a look at these examples.
But I don't like the text format.
So let me bring my drawing tablet.
And here it is, guys.
The masterpiece.
The first example.
Right.
So the input is a matrix with free rows and free columns.
And for each cell, we have to find the nearest zero.
Let's take a look at this.
Well, for this cell.
It's a zero, right?
So the distance between itself and itself is going to be zero, right?
So this is why this is a zero.
Of course, every cell that is a zero.
We can conclude pretty easily that the answer for it is going to be a zero.
Right.
So let me just feel here.
This little guy, this little one, which has four neighbors of zero.
So obviously, it's all right.
This was a pretty easy example.
Let's take a look at the second one.
In this example, we have a little bit more work to do because obviously there's more at once.
So, again, for all the zeros, we have to just feel these values of zeros.
So all of these are zeros.
And now let's take a look at this one.
Well, obviously, he's got free neighbors, which are zero.
So the minimum distance is one.
Right.
We can pick any of this that for this one has a number of zero.
So this is a one for this one has a number of zero.
So this is a one.
But this one, this little guy doesn't have any neighbor, which is equal to zero.
So this is why we have to perform like two steps, one step here and another step here.
Or maybe this path, one step here and another step here to reach to some of these.
Right.
So this is going to be distance, too.
And this was basically the second example checked.
All right, guys, I don't know about you, but usually when I have this kind of problems where I have
matrixes and I have to compute at distances between one cell to another, they are pretty classical
R&D.
So, like, let's take a look at the LI algorithm if you know it.
That algorithm says that you have a matrix and you have to, again, compute the minimum distance from
some cell to all the other cells.
Right.
So for each cell, the minimum distance from another one and have obstacles and all that stuff like
that.
Right.
So this one obviously is really similar to that.
So what I have done here is that instead of that ugly zero and one matrix, I can imagine this is a
grid.
And in this grid, we have white.
So this white is actually how I want to visualize.
Let's say the the once.
So this is a one, right?
This white dot, then this green dot is actually a zero.
So what I have to do here is that I have this grid.
And for each of these white dots, I have to know the minimum distance until I get to a green dot.
I can get to any green dot and I can obviously work on every of these parts.
Right.
So I don't know.
Let's take one of these.
Let's take this one.
This white one.
Right for this one.
What can I do?
I have to get to a green dot so I can go on this path and then go on this one.
Or I can go on this one and then go on this one.
Or of course, I can go on this one and then move further to this one.
Right.
So what this is here basically is that I have some kind of points and some kind of edges between them.
Right.
Or kind of puffs.
So this is obviously becoming quite clear.
Some graph.
Right.
So I can visualize this matrix.
And again, as I said, this is a pretty classic trick.
So there are a lot of problems in which some matrix when you have distances between cells, you are
going to interpret those as graphs.
So now I have a graph where the number of vertices is.
And crossed em where N is the number of Rose and M is the number of columns, right.
So I have an crossed M vertices, right.
This is the number of vertices or nodes, whatever you wanna call it.
And now what is the number of edges.
Well, for each of these vertices.
Right.
Almost each of them almost.
We have some exceptions like the corners or the bottom row bottom column and stuff like that.
Have four neighbors.
So, of course, for almost each vertex, I'm going to have four edges that are adjacent to that vortex.
Right.
So I'm going to have a maximum, let's say, maximum of four brassed and crossed M edges where again
and is the number of rows and M is the number of columns.
Right.
So and cross them vertices for crust and crust M edges.
Let's remember a little bit of theory right here.
Now, as you can know, there are a couple of types of graphs, but here we are just going to stick
with dough's where the edges are weighted or unweighted.
Right.
So here I have.
And of course, the second category is where I have waited.
Now, the question is this graph.
This matrix, which now we transformed it into a graph in which category it lies, obviously on the
first one.
Right.
Because we don't have any cost.
Like we don't have a cause, let's say two units of time, free units of time to traverse the that age.
Right.
So basically, it's all one step, one unit of time, one unit of distance, however you call it.
So this graph is we have unweighted ages.
Now, what is the algorithm in which you want to find shortest path?
Right.
For unweighted edges.
What's that called?
It's the B office.
Right.
So B f.
S or of course, the full name of it is breath for search.
I think something like that.
So we should perform some B effects.
Obviously, if we didn't know by now the lead algorithm, the classically algorithm is still a B first.
Right.
Where that matrix is a graph.
So we have to perform this.
Be a first on our new graph.
Perfect.
But the problem is that the B office usually had only one source load.
Right?
So usually when I performed a classic B A first.
I have a source known.
So everything starts from this node.
And basically I start from this note, then I can go to all the other nodes and I just expand.
Right.
I go to some neighbor because here the distance was zero.
I go to some unvisited neighbor.
Now the distance is one here.
Then the distance is one here.
The distance is one here.
And each time I visit a new neighbor, I just added into some Q.
Right.
So initially it's the source then from the source.
I have some neighbor, let's say neighbor one with dist. one.
And then of course I have that source.
And that neighbor in my queue.
And the source is over when I visited all its neighbors.
I start again from that neighbor.
I expand a little bit more.
So let's say this has two more neighbors, which their distances is going to be another two.
So I have, let's say, neighbor one one and neighbor one, two.
Those owners are going to be in the queue.
But obviously, maybe I have some other nodes which were already in the queue.
So when I finish this, I'm going to process all of this.
And then I go.
I move.
And so on and so forth.
Right.
So it propagates pretty.
Mostly like a tree.
You can imagine like a tree where your source code is the root.
And then you just expand the level by level indef.
Right.
But it's in breath, actually, by the name.
So what's my point is that the beer fast, the classic VFX version has only one source.
Not.
But is it necessarily bad if I can start this algorithm for a couple of source knots and it's not at
all.
Let's take a look.
All right.
So in this graph, nothing special.
Besides the fact that I have free source not right.
This is exactly like our problem, because in our problem, I have to know the minimum distance until
I get to some zero.
Right.
So all those zeros can be source slots and I can start from them and expand to all the other nodes in
the Matrix.
So here what happens is that I have free source nodes and I want to know when this algorithm finishes.
What is the minimum distance like for some of these nodes, like one, two, three, four or five,
which have no indices?
I want to know what is the minimum distance until some sort of slot from this free?
Well, what I would change here is that I will still perform maybe a face.
So I will still perform this be a first.
But instead of starting with that sword, Snod, which was basically unique, I'm going to start with
all of this free.
So in that cue, I'm going to have as one.
As to and as free.
Right.
So this is basically how I start.
This is my initial Q.
Now we've disinvite.
Let's simulator, it'll be this algorithm source number one, right?
That's it.
Perfect.
It has one neighbor, which is one.
This neighbor is not visited yet.
Right.
So I can conclude that it's distance, its minimum distance until it finds some such.
It's now one.
So in order to do that, let's mark this with distance one, right.
With the red lights.
All right.
Let s market like this.
So this is no distance.
Perfect.
Now, source one had only one neighbor.
It's a new one.
So I will add this to my queue.
Right.
So the queue, which was as one as two as free now has also node one that as one doesn't have any neighbors.
So I just remove it.
Next one is going to be as true as chool.
Has one neighbor not visited yet.
So this distance is now one.
So I will insert these two in my.
As to not any neighbors anymore, I remove it as free one neighbor not visited dist., one I inserted
in my queue.
All right, let's not get out of or that was free.
And this distance is one.
Right.
So, as you can see like this not.
At this does, too, until source number two, this does free until source number one, but distance
one until source number four.
And source number three found it first.
Right.
Because that's how Beerfest worries, you are assured that at each moment of time in this queue, all
these nodes are going to be, let's say, sorted, increasingly.
Right.
Sorted increasingly by what?
By distance.
Right.
So by distance.
By the minimum distance to some of these source nodes.
And because they are always sorted increasingly by this distance, you are assured that the first time
you reach some node, you are going to reach that node with the minimum distance path, which is pretty
amazing.
Right.
So we can perform this be a first.
We have multiple source nodes.
All we have to do is take the cube populated.
We have all the source nodes and then start the algorithm.
What do you think is going to be Stiehm complexity?
Well, on the classic Beerfest.
So let's say one source me offers.
Right.
As we know is the number of vertices plus the number of edges.
Right.
So let's just call this bigger world number of vertices from our problem, like from that matrix when
we transform into a graph.
It's now m crossed M right.
Number of ages is for crossed and crossed M.
So if we add this together, we'll have something like an crust.
M crust five.
But in time complexities.
We don't care about this kind of constants.
So from one source is big of and crust.
But now from multiple sources.
Let's go a little bit back and think about why the Beerfest, the one source B office is bigo of number
of vertices plus number of edges.
Well, this happens because if you think about it, if you think about how that works, you are visiting
each node exactly once when you encounter this, not for the first time.
Right.
So you marked it as visited and you set its distance.
You do that only one time.
Right.
But when it comes to edges, let's say this is an age.
Right.
When are revisiting edges?
Well, when this knot is the current knot and we are trying out each of its neighbors.
Right.
Each of these neighbors.
I am going to visit DSH.
Or if this node was the current not so the not the first not in the queue.
And I am visiting each of its neighbors.
I will visit this age one more time, too, so we can conclude that each age is visited at most two
times.
Right.
This is a total of number of vertices plus to cross.
Number of ages constants are ignored.
So number of vertices plus number of edges.
So what is the difference between the one source and the multiple source approaches?
Well, it's pretty simple.
No difference at all, because when we start from multiple sources, we visit those nodes, too.
So we set their distances to be equal to zero and we push them into the queue.
And again, for each node, we just traverse its edges.
So it's exactly the same thing.
Each edge is traversed most two times.
Each node is processed at most one time.
So we've have multiple sources approach to that complexity is still going to be bego of an crossed.
Now, hopefully everything is clear.
You've understood my approach.
You've understood why this approach works really well in terms of time.
So let's call it in order to get started.
I'm going to need the number of rows and the number of columns.
So let's just stored them in some variables.
And is the number of rows.
So I'll have Matrix Matrix that size and form the number of columns I will have M.
Which is matrix of zero that size.
That what I have here is that I will need to build the distances matrix.
So that is a vector or a vector of integers.
Let's call it this and I would initialize it as an vector of integers.
And each of these vectors is going to be a size M.
And let's initialize them with minus one.
Right.
Because I need to know somehow that these cells are not visited yet.
I will use minus one.
And if the distance that cell is minus one, I know it's not visited.
Which is pretty amazing.
Right.
I avoid storing another matrix of Borland's by just doing this right.
It's not very well, but it's a nice trick to optimize the memory.
So I have the distances matrix is what I have to do is iterate for my matrix and for each cell.
That is zero.
I have to push it into my queue, but I don't have my cube.
So let's build this cube and have a cube in C++.
It's called Just You.
But as we remember in the B A first, the cube consisted of nodes.
Here my nodes are going to be actually cells.
So I have two ways of doing this.
I can either code these cells like I can assign them numbers.
This is from zero two am crust M minus one, right.
Zero.
One, two, three, four.
Yeah.
They add up or I can actually store pairs, pair of integer and integer, which I think is the smarter
way to do it.
Like you can optimize the memory by just storing the indices.
But we don't care about the memory that much to use that optimization.
So it's cool.
So let's just call this cube.
I will iterate through my metrics.
So from zero two and minus one plus plus we have Jay starting at zero.
J.
Less than M.
J.
Plus.
And if this cell matrix of I.
N G is equal to zero then I know this is a source slot.
And what do I do with so snots.
Well, first of all, I initialize their distance with zero because that's what's up.
The distance to itself is zero and they are visited basically.
And then I will push it into my Q So could that Bush pair of I n g.
Perfect.
Now this is basically the initialization.
It's time for the B office.
And as we said, until this Q or as long is the right word, I think as long as this Q is not empty
I will take does not.
Which is in the front of the queue.
So pair of end and end, I can call it Noad.
Let's do that.
Cue that front.
Right.
So I'll take that note.
And what I'm going to do with it is that I am going to try out each of its neighbors.
Now, how do I know the neighbors?
Well, this note is a cell, right?
So it basically has at most four neighbors, not for the neighbors.
I want to do something more special here.
And this is actually a very, very nice trick.
You can do something like that.
You can.
Let's say have caused it.
Right.
The X here.
And you can say equals and you can do this for Y.
So what I'll do here is that I'll basically have to a raise, which are Kunst integers and they will
represent my possible direction.
So up, down, left and right.
So instead of trying out for like copying the same code four times and just adjusting it to the direction
to the neighbor, I will basically have a single for loop and it's going to take the direction from
these two arrays.
So minus one, as you write, minus one is zero is for the op neighbor, zero and one zero and one is
for the right neighbor.
Right.
So the X is basically with how much I will increase the row and the Y is we've how much I would increase
the column.
So minus one zero zero one one zero.
In order to go down one zero and zero minus one.
Right.
And the last one is zero minus one.
Perfect.
Now I have this.
What shall I do?
Well, first of all, I took my note.
So for trying out each neighbor, I will fix that direction.
So I have T equals zero T less than four plus plus.
Right.
T is the direction.
Now this neighbor is going to be not that first blast.
The ex of team and node.
That second.
Plus d y of D.
Right.
Let's talk this into another bear.
So let's say a bear of EMT and no one is going to be known that first blast this or that second.
OK.
So this is not the one.
This is the neighbor.
Right?
I want to do the neighbor.
Right.
So let's actually call this neighbor because no one is there.
Anyways, these variables are awful anyways, but we are not doing some coding interview right now so
we can feel free to use their names who aren't.
Let's see.
So this is the neighbor, right?
Neighbor.
And I want to try this neighbor out.
So it.
First of all, this neighbor got to be valid because I can do something like that.
I can, let's say, have this note here.
If you take a look at the example, right.
And when I want to go down, I will actually go down.
But the problem is that that said is not valid.
So I have to check that, too.
So what I basically do here is that I will check if this neighbor is valid.
And in order to check if this neighbor is valid, I can actually make another function and I think I'm
going to do that.
So let's call it Boole is valid and this function is going to take a pair of end and end pair of in
and end.
And let's just call this cell.
Right.
So cell and I'm going to check if this cell is valid.
How do I do that?
Well, first of all, if cell that first, which is going to be the rope is less than zero or cell that
first is greater or equal than N or cell cell, that second is less than zero or cell.
That second is greater or equal.
Then M, N and M are the number of columns or the rows and columns.
Sorry.
But to have them.
So I'll have to pass them as parameters to.
So let's say here I'm going to have end and and end.
All right.
So if this happens, we know this cell is not valid.
So we can just return false either.
Everything's fine.
So we will return.
True.
And this is awesome.
Now, what happens here is that when I have this neighbor, if is valid of neighbor and N and M.
So this neighbor is valid.
And the distance of this neighbor.
So this of neighbor that first.
And Naib board dot second is minus one.
This means all right is valid.
It's not visited yet.
So it's time to update its distance and then pushed into the queue.
So I'll take this.
Copy paste, Yoro.
These neighbors first neighbor DOT second is going to be equal to the distance of not that first and
not that second plus one.
Right.
Because they sell.
I just moved to the neighbor.
I increase it with one step.
And that's basically it, I think.
No, that's not it.
Cue that push of name.
Perfect.
Nope.
I have inserted the neighboring to the cube.
I have updated its distance.
Now I think everything is fine.
So, yeah, now everything should work as planned.
Yeah, I think it should.
So what I have to do here is just return the distance.
Yeah, I think so.
Return these.
All right.
I'll probably have some bugs but let's just send it.
So run code.
Have to sign in.
Oh that's nice.
You haven't seen my password.
So sorry.
Maybe next time.
That's it.
Oh, I have a compile error.
That's nasty.
Let's sell that first cell that Frist.
Frist.
What.
Frist.
I don't eat any frist or time limit exceeded.
That's bad, isn't it?
Ah, come on, Mom.
Why didn't you tell me all this time?
That's bad news.
What I basically don't hear is a rookie mistake, which took me a lot of time to figure out which is
kind of bad.
But you learn from mistakes.
What can I say?
So here what I basically did is that I had my note here.
I process it, but I don't remove it from the cube.
Right.
So cue that, Pop.
I think that should work.
Oh, success.
Faster than forty two percent.
Memory less than 66 percent.
Now, in the last video, I have bragged about how my stats are perfect.
You can check that vidaurre out.
I'm going to put a in somewhere somewhere in the channel.
They were 100 percent, 100 percent.
So this time they are not.
But yours are going to be there are a couple of musicians you can do with Dischord.
And you have to figure out those if you don't, you have two or three of my previous videos in which
I do all that kind of optimizations, so make sure to check it out.
But this is the lesson for today, guys.
I really hope that you enjoy to be a face.
It's quite commonly as that coding interviews like I think I've had two or three interviews where I
was asked exactly what exactly this problem, but the same tricks that we have done to get to the solution.
So make sure you rewind and remember them.
And, of course, make sure to hit the like button.
Make sure you press subscribe and make sure you always, always press the bell button because you will
be notified by me in display to be in quarantine.
I will post, I can say more than usual, because what can you do?
You fight the virus by coding problems.
So subscribe belly button like see on the next one.
This is Endi Helen Isarn.