Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1162. As Far from Land as Possible - Leetcode Solution

Problem Description

You are given an n x n binary grid, where each cell is either land (1) or water (0). Your task is to find the water cell that is as far as possible from any land cell, and return the distance to the nearest land cell for this water cell. The distance between two adjacent cells is 1 (using 4-directional movement: up, down, left, right).

If there is no water cell or no land cell in the grid, return -1.

  • Each cell is either 0 (water) or 1 (land).
  • You may not move diagonally or outside the grid.
  • There is at least one cell in the grid.

Thought Process

The brute-force approach would be, for each water cell, to calculate its distance to every land cell, then pick the minimum. Finally, select the water cell with the maximum of these minimum distances. However, this is very inefficient for larger grids because it requires checking every pair of land and water cells.

Instead, we can optimize this by thinking in terms of "waves" spreading out from all land cells at once. This is a classic use case for Breadth-First Search (BFS): starting from all land cells, we expand outwards, marking the distance to each water cell as we reach it. The last water cell we reach will be the farthest from any land.

This approach is much more efficient and avoids redundant calculations.

Solution Approach

We use a multi-source BFS starting from all land cells. Here’s the step-by-step process:

  1. Initialize a queue and add all positions of land cells (1).
  2. Maintain a visited grid to avoid revisiting cells.
  3. From each land cell, perform BFS, expanding to adjacent water cells (0), marking their distance as one more than the current cell.
  4. Continue until there are no more water cells to visit.
  5. The maximum distance found during this process is the answer.
  6. If there is no water or land in the grid, return -1 as required.

This approach ensures each cell is visited at most once, and the BFS guarantees that the first time we reach a water cell, it is through the shortest path from any land cell.

Example Walkthrough

Consider the following grid: 

    [[1,0,1],
     [0,0,0],
     [1,0,1]]
  1. All land cells (corners and middle of edges) are queued as BFS starting points.
  2. BFS expands to adjacent water cells in the first layer, marking them as distance 1.
  3. Next, the center cell (1,1) is reached in the second layer, marking it as distance 2.
  4. No more water cells are left; the farthest water cell is at distance 2.
  5. Return 2 as the answer.

This demonstrates how BFS "waves" from all land cells simultaneously and finds the farthest water cell efficiently.

Time and Space Complexity

  • Brute-force: For every water cell, check distance to every land cell. If there are W water and L land cells, this is O(W * L).
  • Optimized BFS: Each cell is visited at most once, so the time complexity is O(n^2), where n is the grid size. The space complexity is also O(n^2) for the queue and visited grid.

The optimized approach is much faster and more scalable for larger grids.

Summary

The key insight is to treat all land cells as sources and perform a BFS to find the farthest reachable water cell. This avoids redundant distance calculations and leverages the efficiency of BFS for shortest-path problems. The solution is elegant because it uses a single pass over the grid, ensures optimality, and is easy to implement.

Code Implementation

from collections import deque

class Solution:
    def maxDistance(self, grid):
        n = len(grid)
        queue = deque()

        # 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 there are no land or no water cells, return -1
        if len(queue) == 0 or len(queue) == n * n:
            return -1

        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        max_dist = -1

        while queue:
            x, y = queue.popleft()
            for dx, dy in dirs:
                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_dist = max(max_dist, grid[nx][ny] - 1)
                    queue.append((nx, ny))

        return max_dist
      
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int, int>> q;

        // Add all land cells to the queue
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    q.push({i, j});
                }
            }
        }

        // If there are no land or no water cells, return -1
        if (q.empty() || q.size() == n * n) return -1;

        vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        int max_dist = -1;

        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto [dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = grid[x][y] + 1;
                    max_dist = max(max_dist, grid[nx][ny] - 1);
                    q.push({nx, ny});
                }
            }
        }
        return max_dist;
    }
};
      
import java.util.*;

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();

        // Add all land cells to the queue
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1)
                    queue.offer(new int[]{i, j});

        // If there are no land or no water cells, return -1
        if (queue.isEmpty() || queue.size() == n * n)
            return -1;

        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        int maxDist = -1;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = grid[x][y] + 1;
                    maxDist = Math.max(maxDist, grid[nx][ny] - 1);
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        return maxDist;
    }
}
      
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    const n = grid.length;
    const queue = [];

    // Add all land cells to the queue
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1) {
                queue.push([i, j]);
            }
        }
    }

    // If there are no land or no water cells, return -1
    if (queue.length === 0 || queue.length === n * n) return -1;

    const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
    let maxDist = -1;
    let idx = 0;

    while (idx < queue.length) {
        const [x, y] = queue[idx++];
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                grid[nx][ny] = grid[x][y] + 1;
                maxDist = Math.max(maxDist, grid[nx][ny] - 1);
                queue.push([nx, ny]);
            }
        }
    }
    return maxDist;
};