Problem Breakdown
We are given an grid containing binary values: 0 (water) and 1 (land). The goal is to identify a specific water cell that maximizes the distance to its nearest land cell, then return this maximum distance. If no such configuration exists (e.g., if there are no lands or no waters), we must return -1.
Inputs:
- A 2D list
gridof size . - Values restricted to integers
0and1.
Outputs:
- An integer representing the maximum Manhattan distance from a water cell to its nearest land.
-1if no valid solution exists (no lands or no waters).
Implicit Constraints & Edge Cases:
- Connectivity: The grid is implicitly connected for traversal purposes; we treat all cells as nodes in an unweighted graph where edges exist between adjacent coordinates and .
- Distance Metric: While the problem mentions Manhattan distance , in a grid without obstacles, this is equivalent to BFS depth. Since we can traverse through both land and water cells (treating them as traversable nodes for propagation), standard Multi-Source BFS applies perfectly here.
- Empty/Uniform Grids: If the grid contains only
0s or only1s, a valid “water cell” cannot be found relative to a “land”. The problem statement implies returning-1in these scenarios (specifically if no land exists).
Intuition
A naive brute-force approach would iterate through every water cell and run a separate BFS/Dijkstra search from that specific point to find the nearest 1. This is inefficient because for each of cells, we might traverse up to nodes. Total complexity: .
Key Insight: Instead of running BFS from every water cell to the lands, run a Multi-Source BFS. We treat all land cells (1) as simultaneous starting points (sources). Imagine dropping stones into an ocean at every island location simultaneously. The waves expand outward in concentric rings. Any wavefront reaching a new unvisited water cell represents that distance from its nearest source. Since we want the maximum such distance, this is simply the depth of the last visited node during a full traversal where all reachable cells are covered by these expanding fronts.
Optimal Approach:
- Initialize a queue with coordinates of all land cells (
1). Mark them as “visited” or processed immediately to prevent re-adding them. - Perform BFS layer-by-layer (level-order). Each level increment corresponds to an increase in Manhattan distance from the nearest source.
- Track the maximum depth reached during this expansion. If no water exists initially, return
-1.
Approach
- Initialization: Iterate through the grid once () to collect all coordinates of
1s into a queue and count them. Also check if any0exists; if not (all lands), we technically can’t find a water cell, so return-1. If no land exists (queueempty), also return-1.- Note: To avoid modifying the input grid strictly for space efficiency in interviews unless necessary, I will use a
visitedset or modify the queue logic. However, since we need to distinguish between “land” (source) and “water visited”, marking land cells as processed is crucial so they don’t expand into each other unnecessarily if that counts as distance 0? Actually, standard BFS treats all nodes equally once added to queue. - Refined Logic: Add all
1s to the queue with initial distance0. Mark them in a visited set (or modify grid). If we encounter another1during expansion, it’s already processed or irrelevant for “water cell” maximization? Actually, if two lands are adjacent, their distance is 0. We only care about water cells getting assigned distances > 0. - BFS Loop: While the queue is not empty:
- Process all nodes currently in the queue (one level). Increment
levelcounter at start of each batch? Or just track max depth when we push a new node to queue that was previously unvisited water. - For current cell
(r, c), check 4 neighbors. - If neighbor is within bounds and not visited:
- Mark as visited (distance
current_dist + 1). - Update global max distance if this node represents a valid target (i.e., it was water). Since we start with lands, any newly added cell to the queue during BFS will be a water cell. The last such addition determines the answer? Not necessarily; but since grid is connected and unweighted, the maximum depth reached in the traversal corresponds exactly to the furthest point from any source.
- Mark as visited (distance
- Process all nodes currently in the queue (one level). Increment
- Result: Return
levelor max distance found. If no waters were ever visited (all 1s), return-1.
- Note: To avoid modifying the input grid strictly for space efficiency in interviews unless necessary, I will use a
Complexity Analysis
Time Complexity: . We visit each cell in the grid exactly once during the BFS traversal. The queue operations are constant time per node, and there are at most nodes. Space Complexity: to store the coordinates of all land cells initially (worst case: half lands) plus the visited set/queue overhead in a grid graph context.
Solution
from collections import deque
def maxDistance(grid):
n = len(grid)
# Queue for BFS, initialized with all land cells
queue = deque()
water_exists = False
# Populate initial sources and check edge cases
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
queue.append((r, c))
else:
water_exists = True
# If no land exists or no water exists (all cells are same), return -1
if not queue or not water_exists:
return -1
max_dist = 0
while queue:
level_size = len(queue)
for _ in range(level_size):
r, c = queue.popleft()
# Directions: Up, Down, Left, Right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
# Found a water cell reachable from nearest land
max_dist += 1
queue.append((nr, nc))
return max_dist
# Example usage (uncomment for testing)
# print(maxDistance([[1,0,1],[0,0,0],[1,0,1]]))) # Output: 2