Decoding the BFS Questions (Part 1b)

I will be continuing where I left off in the previous post. You can read the previous part here: https://medium.com/decoding-leetcode/decoding-the-bfs-questions-57dafb2fc6b

So we will be continuing with the Type 1 of questions: The grid based questions in graphs

AS FAR FROM LAND AS POSSIBLE

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1

So we will be working along the same lines to help you understand and memorize the patterns and see how easily these questions can be cracked. Read the previous post (highly recommended)

As Far from Land as Possible - LeetCode

1. So our water is → 0 and our land is → 1 . What we need to find is that, the water cell which is the farthest away from land. We simply need to return this distance.
2. The distance we need to consider is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
3. Fair enough, we understand the question as simply finding some point in a large sea which is farthest away from the land, and obviously we need to find that distance, we don’t actually need to worry about that distance equation, let’s see why with the help of some examples:

Getting farthest from land

The first example: We have 5 sea cells, 4 of them have adjacent lands, so they are only 1 distance away from land. But look at the cell in the middle of grid (2,2) it has got no land cells around it! Think of it going one step now in all the four directions ( we need to find the maximum path it can travel).

In this case, no matter where it goes, it will reach a cell that is adjacent to land, hence its value becomes 2! Because land comes after 2 steps no matter what it can not take any more steps, it will fall into a land always.

The second example: We have 8 sea sells! Well that is too many! We will walk the same way, (0,1) and (1,0) have adjacent lands so → 1 is the answer for them.

Lets move ahead now, (0,2) ,(2,0), (1,1) can take one step extra so →2 is the answer for them.

And so on and hence forth we can compute the answer till we reach (2,2) which will have a distance of 4 at max! (You can check it yourself)

Note: Here you might think that reaching from (2,2) to (0,0) can be done in many ways and instead of taking just 4 steps you could’ve taken way more steps by going from: (1,2) →(0,2) →(0,1) →(1,1) →(1,2) →(2,0) →(1,0) →(0,0) . But that would not be the MANHATTAN DISTANCE as asked in the question. We just noticed a pattern and we need to work on that only :)

Initial Thoughts: Okay so after all the analysis I guess I will need to pickup all the sea cells, but wait, they are always going to be way too many, can we instead look for land cells and keep searching in outward levels to find sea? Well apparently, yes we can!

Thanks to leetcode user: 1961, for these beautiful illustrations.

Take a good look at the pictures above, and try to understand this line: LOOK AT THE OUTER LEVEL FOR A GIVEN CELL. This is nothing but LEVEL ORDER TRAVERSAL! And this my dear friend, is the basic root of BFS.

So as it is a BFS, we will need a queue to store land cells, and also we can safely say all land cells have a max distance of 0 from land (fair enough?)

Now maybe we just need to explore each land cell in all 4 dirs (look at the previous post for more info) if there is a sea convert it to land and to the list! (Mutate and Append logic from the previous post!) look outwards, each time you step a level up, increase your distance value and finally keep track of the global max distance value.

ALGORITHM:

1. Put all land cells into the queue, distance to themselves is a sweet 0.
2. maxDistance needs to be calculated as the final result, so keep updating it as you explore the graph via the standard BFS algorithm.
3. Pick up a land (pop from queue), get its distance value(d), look around that land mass, if you find land or hit a boundary just ignore and move ahead, otherwise: MUTATE AND APPEND
4. Mutate meaning, change the water cell to land cell! and its distance value will be 1+ the value(d) you got from the cell you’re processing
5. Append meaning, now that this guy is a land, put it into the queue to explore it later! And looks like we are done!

Before I give in the code lets talk about the structure of queue that I have used here:

lands = collections.deque()
lands.append([(i,j), 0])

This is nothing fancy just a queue of lists. Each list has two elements. First one is a tuple (location of cell) , second one is an integer (distance)

So here’s the final code, I hope there won’t be anything that you won’t understand, still feel free to post the queries in the comment section below :)

FINAL CODE:

Hope this was helpful. Next I will be picking up an AMAZON INTERVIEW QUESTION, I believe we are ready enough to say it will be a cake walk when we see it. Till then, try to understand this and the previous question to your best ability, don’t worry the concepts will sink in with time, its a slow and steady process, hold tight!

Any suggestions are welcome :)