LeetCode 1162 - As Far from Land as Possible

The problem requires finding the water cell in a given n x n grid that is farthest from any land cell, using Manhattan distance. The grid consists only of 0s and 1s, where 0 represents water and 1 represents land.

leetcodemediumarraydynamic-programmingbreadth-first-searchmatrix

LeetCode Problem 1162

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem requires finding the water cell in a given n x n grid that is farthest from any land cell, using Manhattan distance. The grid consists only of 0s and 1s, where 0 represents water and 1 represents land. The Manhattan distance between two cells (x0, y0) and (x1, y1) is defined as |x0 - x1| + |y0 - y1|. The output should be the maximum distance from a water cell to the nearest land cell, or -1 if the grid has only water or only land.

The constraints tell us that n can be up to 100, so a brute-force solution that computes distances from each water cell to every land cell would be computationally expensive. Edge cases to consider include grids that are entirely land, entirely water, or have land clustered in corners, as these could influence distance calculation. The problem guarantees that the input is always a valid square grid.

Approaches

The brute-force approach involves iterating over each water cell and calculating its Manhattan distance to every land cell, taking the minimum distance for that water cell, and then keeping track of the maximum of these minimum distances. This approach works but is inefficient because it requires O(n^4) time for a grid of size n x n, which is not feasible for n = 100.

The optimal approach leverages Breadth-First Search (BFS). By starting BFS simultaneously from all land cells and expanding outward in layers, we can assign each water cell its distance from the nearest land cell efficiently. This approach works because BFS guarantees the first time we reach a water cell is via the shortest path from any land cell. We increment distance level by level until all reachable water cells have been processed.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Check every water cell against every land cell. Too slow for large grids.
BFS from all land cells O(n^2) O(n^2) Multi-source BFS expands level by level, assigning distances efficiently.

Algorithm Walkthrough

  1. Initialize a queue with coordinates of all land cells in the grid. This ensures BFS starts from all land simultaneously.
  2. Initialize a variable max_distance to -1 to keep track of the maximum distance encountered.
  3. Perform BFS from all land cells at once. For each cell dequeued, explore its four neighbors (up, down, left, right).
  4. If a neighbor is water (value 0), update its value to 1 plus the value of the current cell. This effectively records the distance from the nearest land.
  5. Enqueue the neighbor into the BFS queue to continue expanding outward.
  6. After BFS completes, iterate through the grid to find the maximum distance recorded, subtracting 1 because initial land cells are marked as 1.
  7. If the maximum distance remains -1 (no water found), return -1. Otherwise, return the maximum distance.

Why it works: BFS ensures that the first time a water cell is reached, it is reached via the shortest path from land. By updating distances incrementally in layers, we guarantee that each water cell records the minimum distance to any land cell. The maximum among these minimum distances is the correct answer.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = deque()
        
        # Step 1: Add all land cells to the queue
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i, j))
        
        # If no land or no water, return -1
        if len(queue) == 0 or len(queue) == n * n:
            return -1
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        max_distance = -1
        
        # Step 2: BFS from all land cells
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                    grid[nx][ny] = grid[x][y] + 1
                    max_distance = max(max_distance, grid[nx][ny] - 1)
                    queue.append((nx, ny))
        
        return max_distance

The Python implementation first collects all land cells, then uses BFS to propagate distances into water cells. Each water cell receives the distance of its closest land neighbor incremented by 1, ensuring correctness. The max_distance variable tracks the farthest water cell reached.

Go Solution

package main

func maxDistance(grid [][]int) int {
    n := len(grid)
    type Point struct{ x, y int }
    queue := []Point{}
    
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                queue = append(queue, Point{i, j})
            }
        }
    }
    
    if len(queue) == 0 || len(queue) == n*n {
        return -1
    }
    
    directions := []Point{{0,1},{1,0},{0,-1},{-1,0}}
    maxDistance := -1
    
    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        for _, d := range directions {
            nx, ny := p.x + d.x, p.y + d.y
            if nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0 {
                grid[nx][ny] = grid[p.x][p.y] + 1
                if grid[nx][ny]-1 > maxDistance {
                    maxDistance = grid[nx][ny]-1
                }
                queue = append(queue, Point{nx, ny})
            }
        }
    }
    
    return maxDistance
}

The Go version mirrors the Python logic but uses a slice for the queue and a struct Point for coordinates. Go handles integer operations safely and avoids pointer complications since we work with indices.

Worked Examples

Example 1: [[1,0,1],[0,0,0],[1,0,1]]

  1. Land cells: (0,0),(0,2),(2,0),(2,2) are enqueued.
  2. BFS layer 1 updates water cells (0,1),(1,0),(1,2),(2,1) to distance 2.
  3. BFS layer 2 updates (1,1) to distance 3.
  4. Maximum distance = 3 - 1 = 2. Correct.

Example 2: [[1,0,0],[0,0,0],[0,0,0]]

  1. Land cell (0,0) enqueued.
  2. BFS propagates distances to all water cells.
  3. Farthest water cell (2,2) has distance 5 - 1 = 4. Correct.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each cell is visited at most once during BFS.
Space O(n^2) Queue can contain all cells in worst case.

The BFS approach scales efficiently even for n = 100 because each cell is processed only once, and distance updates are done in-place.

Test Cases

# Provided examples
assert Solution().maxDistance([[1,0,1],[0,0,0],[1,0,1]]) == 2  # center water farthest
assert Solution().maxDistance([[1,0,0],[0,0,0],[0,0,0]]) == 4  # bottom-right farthest

# Edge cases
assert Solution().maxDistance([[0,0],[0,0]]) == -1  # all water
assert Solution().maxDistance([[1,1],[1,1]]) == -1  # all land
assert Solution().maxDistance([[1]]) == -1  # single land cell
assert Solution().maxDistance([[0]]) == -1  # single water cell
assert Solution().maxDistance([[1,0],[0,0]]) == 2  # small grid with one land
Test Why
[[1,0,1],[0,0,0],[1,0,1]] Standard case with water surrounded by land
[[1,0,0],[0,0,0],[0,0,0]] Land in a corner, farthest distance from corner
All water Tests handling of no land
All land Tests handling of no water
Single cell Edge case for minimum grid size
Small mixed grid Verifies BFS propagates correctly

Edge Cases

One critical edge case is when the grid is entirely water. A naive BFS would try to start but have no initial land cells, potentially causing errors. The solution correctly returns -1 immediately. Another edge case is an all-land grid, which similarly requires an immediate -1 return