Domain 2MediumMEDIUM

As Far from Land as Possible

LeetCode problem 1162: As Far from Land as Possible (medium).

Domain: medium•Updated: 2026-09-09
#Breadth-first Search#Graph

Problem Breakdown

We are given an N×NN \times N 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 grid of size N×NN \times N.
  • Values restricted to integers 0 and 1.

Outputs:

  • An integer representing the maximum Manhattan distance from a water cell to its nearest land.
  • -1 if 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 (r,c)(r, c) and (r±1,c),(r,c±1)(r \pm 1, c), (r, c \pm 1).
  • Distance Metric: While the problem mentions Manhattan distance ∣x0−x1∣+∣y0−y1∣|x_0 - x_1| + |y_0 - y_1|, 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 only 1s, a valid “water cell” cannot be found relative to a “land”. The problem statement implies returning -1 in 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 O(N2)O(N^2) cells, we might traverse up to O(N2)O(N^2) nodes. Total complexity: O((N×N)2)=O(N4)O((N \times N)^2) = O(N^4).

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:

  1. Initialize a queue with coordinates of all land cells (1). Mark them as “visited” or processed immediately to prevent re-adding them.
  2. Perform BFS layer-by-layer (level-order). Each level increment corresponds to an increase in Manhattan distance from the nearest source.
  3. Track the maximum depth reached during this expansion. If no water exists initially, return -1.

Approach

  1. Initialization: Iterate through the grid once (O(N2)O(N^2)) to collect all coordinates of 1s into a queue and count them. Also check if any 0 exists; if not (all lands), we technically can’t find a water cell, so return -1. If no land exists (queue empty), also return -1.
    • Note: To avoid modifying the input grid strictly for space efficiency in interviews unless necessary, I will use a visited set 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 distance 0. Mark them in a visited set (or modify grid). If we encounter another 1 during 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 level counter 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.
    • Result: Return level or max distance found. If no waters were ever visited (all 1s), return -1.

Complexity Analysis

Time Complexity: O(N2)O(N^2). 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 N×NN \times N nodes. Space Complexity: O(N2)O(N^2) 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