#1162

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

As Far from Land as Possible

Find the farthest water cell from land in a grid and return the Manhattan distance using state transition dynamic programming.

array dynamic programming breadth first search matrix

Problem Statement

You are given an n x n grid where each cell is either land (1) or water (0). Your task is to find a water cell such that its distance to the nearest land cell is maximized. Return the maximum distance, or -1 if no land or water exists.

In this problem, the distance is calculated using the Manhattan distance formula, which is the sum of the absolute differences of their x and y coordinates: |x0 - x1| + |y0 - y1|.

Examples

Example 1

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]

Output: 2

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

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

Solution Approach

State Transition Dynamic Programming

Start by thinking in terms of distances from land to water. Instead of computing each water cell's distance directly, reverse the problem: calculate the distance from all land cells to every other cell using BFS. This ensures an optimal solution, where the distance is calculated incrementally from the nearest land.

Breadth-First Search (BFS)

BFS can be applied to propagate the distance values from all land cells to water cells. By processing all land cells simultaneously, we can minimize the number of steps needed to update the water cells with the correct maximum distance. This ensures that the water cell's distance is the farthest possible from land.

Grid Traversal and Distance Calculation

For each water cell, BFS explores neighboring cells and updates their distances based on the Manhattan distance. This traversal is key to ensuring that the maximum distance is achieved, and any water cell not directly adjacent to land will accumulate the correct distance after BFS completes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depends on the final implementation. BFS typically has O(n^2) time complexity as it processes every cell, while the space complexity is O(n^2) for storing distance values in a grid. Optimizations may reduce space usage, but the time complexity remains tied to grid size.

What Interviewers Usually Probe

Can the candidate apply dynamic programming to transform the problem into a state transition problem?
Is the candidate able to connect BFS with dynamic programming techniques?
Does the candidate understand how BFS can propagate distance calculations efficiently across a grid?

Common Pitfalls or Variants

Common pitfalls

Failing to apply BFS from all land cells at once, resulting in incorrect or incomplete distance values.
Overcomplicating the problem by calculating distances individually for each water cell, instead of propagating distances from land to water.
Not accounting for edge cases, such as when there are no land or no water cells in the grid.

Follow-up variants

Handling grids with more complex obstacles or barriers between land and water.
Extending the problem to include diagonal movement (chebyshev distance) instead of Manhattan distance.
Modifying the problem to find the nearest water cell to each land cell instead of the farthest water cell.

FAQ

How do I use BFS to solve the 'As Far from Land as Possible' problem?

You use BFS to propagate distances from all land cells to water cells. Start by treating all land cells as starting points, then use BFS to compute distances incrementally.

Can dynamic programming be applied to this problem?

Yes, dynamic programming is applied by thinking of the problem as state transitions from land to water cells. BFS can efficiently calculate the maximum distance from land to water using dynamic programming principles.

What is the key idea behind the 'As Far from Land as Possible' problem?

The key idea is to calculate the maximum distance from any water cell to the nearest land cell, which can be achieved by reversing the problem and using BFS to propagate distances from land cells.

What should I do if my grid has no land or no water?

If there is no land or no water, return -1 as no valid distance can be computed.

How does the BFS algorithm ensure optimality in this problem?

BFS ensures optimality by updating all water cells' distances based on the shortest path to any land cell, ensuring that the maximum distance is correctly calculated.

terminal

Solution

Solution 1: BFS

We can add all land cells to the queue $q$. If the queue is empty, or the number of elements in the queue equals the number of cells in the grid, it means that the grid contains only land or ocean, so return $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])
        ans = -1
        if len(q) in (0, n * n):
            return ans
        dirs = (-1, 0, 1, 0, -1)
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
                        grid[x][y] = 1
                        q.append((x, y))
            ans += 1
        return ans

Continue Practicing

#773 sliding puzzle #542 01 matrix #329 longest increasing path in a matrix