As Far from Land as Possible

Patrick Leaton

Published: Oct. 18, 2021, 9 p.m.

Problem Description

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. If no land or water exists in the grid, return -1.

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|.

Example 1:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

The description was taken from https://leetcode.com/problems/as-far-from-land-as-possible/.

Problem Solution

#O(N^2) Time, O(N^2) Space

class Solution:

    def maxDistance(self, grid: List[List[int]]) -> int:

        n = len(grid)

        queue, seen = collections.deque(), {}

        

        def in_bounds(row:int, col:int) -> bool:

            if row < 0 or col < 0 or row >=n or col >=n:

                return False

            if (row, col) in seen:

                return False

            if grid[row][col] == 1:

                return False

            return True

        

        def bfs() -> int:

            neighbors = [(0,1), (1,0), (0,-1), (-1,0)]

            distance = 0

            while queue:

                width = len(queue)

                for _ in range(width):

                    row, col = queue.popleft()

                    for neighbor in neighbors:

                        next_row, next_col = row+neighbor[0], col+neighbor[1]

                        if in_bounds(next_row, next_col):

                            seen[(next_row, next_col)] = True

                            queue.append((next_row, next_col))

                if queue:

                    distance += 1

            return distance

        

        for row in range(n):

            for col in range(n):

                if grid[row][col] == 1:

                    queue.append((row, col))

    

        if not queue or len(queue) == n*n:

            return -1

        return bfs()

Problem Explanation

If we are trying to find the maximum distance to the nearest land, we can rephrase this to find the maximum distance from each island.

If we are looking for distances from an origin, a Breadth-First Search is more favorable than Depth-First Search because it will search layer by layer instead of depth by depth.

What we can do is do a scan of the grid and push each island into a heap, then we will continue to push and pop neighbor nodes of each island until we have run out of nodes to put into the heap.

However many layer traversal iterations that have passed during the BFS will be the answer to the maximum distance.

Let's start by caching the length of n so that we don't have to keep rewriting this later.

n = len(grid)

Let's also initialize a queue and a dictionary to track cells that we have seen so that we don't revisit them.

queue, seen = collections.deque(), {}

Next, we will go ahead and make a helper function that will take a row and column to let us know if a cell is within the bounds of our grid.

If it is out of bounds, has already been seen, or is land, it will return false. Otherwise, it will return true.

def in_bounds(row:int, col:int) -> bool: if row < 0 or col < 0 or row >=n or col >=n: return False if (row, col) in seen: return False if grid[row][col] == 1: return False return True

Next, we will make our BFS function.

def bfs() -> int:

We will also want a counter that keeps track of the distance of the path taken to get to the last zero, and a list of neighbor deltas for the right, left, top, and bottom neighbors.

neighbors = [(0,1), (1,0), (0,-1), (-1,0)] distance = 0

Now, we will write our BFS.

While we still have cells in our queue, we will continue searching for the farthest zero.

while queue:

Within our BFS, we will start by calculating the width of the queue because that will let us know how many cells are in the current layer.

width = len(queue)

Then, for each node in the queue, we will pop off it off, get its row and column, get the rows and columns of each of its four neighbors, and if a neighbor hasn't been seen, we will mark it as seen and visit it next.

for _ in range(width): row, col = queue.popleft() for neighbor in neighbors: next_row, next_col = row+neighbor[0], col+neighbor[1] if in_bounds(next_row, next_col): seen[(next_row, next_col)] = True queue.append((next_row, next_col))

Once we have traversed an additional layer, if we still have cell nodes in our queue, we will increment the distance by one.

if queue: distance += 1

Once we have run out of cells to visit, we will return the distance.

return distance

Now that we have our BFS function built, let's traverse the grid and see if we can find any pieces of land. If we do, we will add them to our queue so that we can perform a BFS from them.

for row in range(n): for col in range(n): if grid[row][col] == 1: queue.append((row, col))

When we have finished pushing any pieces of land in the queue, before we actually start the BFS we'll need to make sure we have a valid grid.

If we have no land in the queue, or the queue is made up entirely of land, we will return a negative one.

if not queue or len(queue) == n*n: return -1

Otherwise, we will run our BFS and return the maximum distance we traveled from land to find the last piece of water.

return bfs()