1162. As Far from Land as Possible

Problem Description

In this problem, we are given a two-dimensional array grid of size n x n that represents a map of water and land. The values in the grid can either be 0 or 1. A value of 0 indicates a water cell, while a value of 1 indicates a land cell. Our goal is to find a water cell such that it is as far away as possible from any land cell. This is measured by the Manhattan distance, which is the sum of the absolute differences of their coordinates. In other words, the Manhattan distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|. If the grid contains only land or only water, we are to return -1. Essentially, we are looking for the maximum distance from water to land, and this distance needs to be the shortest path, as calculated by the Manhattan distance.

Intuition

The problem can be approached by using a Breadth-First Search (BFS) algorithm starting from all the land cells simultaneously. This way, we can calculate the distance of each water cell from the nearest land cell. The BFS algorithm works well here because it naturally explores elements level by level, starting with nodes that are closest (in terms of edge count) to the starting nodes. By starting from every land cell, we ensure that the first time we reach a water cell is the shortest distance to land because BFS doesn't revisit nodes that it has already seen.

To implement this, we first create a queue and enqueue all the land cell coordinates. Then, we iterate over the queue in a BFS manner. For each cell that we pop from the queue, we check all of its adjacent (up, down, left, right) cells. If an adjacent cell is water (indicated by a 0), we mark it as visited by changing its value to 1 and then add it to the queue. This process continues until there are no more water cells left to visit.

We keep track of the levels in BFS because each level represents an additional step away from the originally enqueued land cells. Once BFS completes, the last level's distance is the furthest any water cell is from the nearest land cell (the maximum distance). If there are no water cells, or the grid is entirely water, the answer is -1, as per the problem statement.

In the provided solution, the Python function pairwise is used to generate adjacent direction pairs (up, down, left, right) from the dirs list. This is a convenience for traversing the grid.

Learn more about Breadth-First Search and Dynamic Programming patterns.

Solution Approach

The solution uses the Breadth-First Search (BFS) algorithm to efficiently find the maximum distance of a water cell to the nearest land cell. Here is a step-by-step breakdown of how the solution is implemented:

1. A deque, which is a double-ended queue from the collections module in Python, is used because it supports constant time append and pop operations from both ends. This is ideal for a BFS implementation where we need to efficiently add to and remove elements from the queue.

2. The first step is to locate all the land cells and add their coordinates to the queue. This is done with the list comprehension q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j]), which scans the entire grid and enqueues the coordinates of all cells with a value of 1 (land).

3. In the case where the grid is all land or all water, the function immediately returns -1, since it's not possible to have a distance from water to land in these scenarios.

4. The solution introduces a list dirs which holds values (-1, 0, 1, 0, -1). With the pairwise function, each pair from this list will be used to represent the directional vectors (up, down, left, right) for the adjacent cells.

5. As long as the queue is not empty, the BFS process continues. For each cell in the queue, we remove it from the front of the queue, and for each direction (up, down, left, right), we compute the neighboring cell's coordinates.

6. If a neighbor cell is within the bounds of the grid and is water (indicated by a 0), we mark it as visited (by marking it as land with a 1) to prevent re-visitation and enqueue it.

7. After visiting all neighbors of all cells in the current level of the BFS, we increment a counter ans. This counter keeps track of the distance from the initial set of land cells. Each level of the BFS represents moving one step further out from the land cells, so when the last level is reached, ans represents the maximum distance.

The code utilizes a BFS to ensure that we always find the shortest path from any water cell to land because BFS guarantees that the shortest path will be found first before any longer paths. By visiting cells level-by-level and marking visited cells, the algorithm efficiently expands outwards from all pieces of land simultaneously. The final result is the maximum distance to the nearest land for any water cell in the grid.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using a 3x3 grid. Consider the following grid:

1grid = [
2    [0, 0, 1],
3    [0, 1, 0],
4    [1, 0, 0]
5]

Here, 1 denotes land and 0 denotes water.

Step 1: Initialize an empty deque and add all land cells' coordinates to it. Our grid has land cells at coordinates (0,2), (1,1), and (2,0), so the deque will look like this: deque([(0, 2), (1, 1), (2, 0)]).

Step 2: Since the grid contains both land and water, we do not return -1.

Step 3: We use the list dirs = (-1, 0, 1, 0, -1) to help us find adjacent cells.

Step 4: Begin the BFS process. We dequeue (pop from the front) a cell, check its unvisited (0 valued) neighbors, mark them as visited (1), and enqueue their coordinates.

Here's how the BFS process progresses:

• For (0, 2), its unvisited neighbors are (0, 1) and (1, 2). We visit them, mark them as land, and enqueue their coordinates. The grid becomes:

1grid = [
2    [0, 1, 1],
3    [0, 1, 1],
4    [1, 0, 0]
5]

The deque now becomes: deque([(1, 1), (2, 0), (0, 1), (1, 2)]).

• Next, for (1, 1), all neighbors are already visited or are itself, so no new cells are enqueued.

• Then, for (2, 0), its unvisited neighbor is (2, 1). We visit it, mark it, and enqueue it. The grid becomes:

1grid = [
2    [0, 1, 1],
3    [0, 1, 1],
4    [1, 1, 0]
5]

The deque now becomes: deque([(0, 1), (1, 2), (2, 1)]).

• Continue the process for each cell in the deque, then enqueue their unvisited neighbors, marking them as visited, and the next level of BFS begins.

• After processing all the cells in the queue, with no more water cells left to visit, the algorithm stops. We increment ans each time we go deeper into a new level in the queue.

At the end of BFS, before the last water cell at (2, 2) is marked as land, ans = 2, which is the Manhattan distance from this water cell to the nearest land cell. Since this was the last water cell visited, the function would return 2. Note that in the real implementation, we would keep track of whether a cell has been visited differently to conserve the grid's structure and information after finishing the algorithm.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by the while loop that processes each cell of the grid. Assuming the grid is an n x n matrix, the BFS (Breadth-First Search) process will visit each cell at most once. Initially, all the land cells (cells with a value of 1) are added to the queue, and for each land cell, the code iterates over its four neighboring cells. In the worst-case scenario, the queue could contain all the cells of the grid (but not at the same time since the grid gets populated with 1s as the BFS progresses). Hence, the worst-case time complexity is O(n^2), as each cell is processed at most once.

Space Complexity

The space complexity of the code is mainly due to the queue (q) that is used for BFS and the grid itself. The size of the queue can grow up to O(n^2) in a scenario where all cells have to be added before reaching any water cells (cells with a value of 0) because the queue could contain all the cells in the case of a full traversal. However, it is important to note that the queue will not hold all n^2 cells at the same time since cells are continuously being removed and added. Nonetheless, the upper bound for the queue's size is still O(n^2). The grid is also O(n^2) in size, but since it is given as an input and is modified in place, it may not count towards additional space complexity in some analysis models.

Considering only auxiliary space used by the algorithm, and not the input size, the space complexity for the queue would thus be O(n^2) as well, which is the additional space required beyond the input itself.

Learn more about how to find time and space complexity quickly using problem constraints.