As far from land as possible

Array Dynamic Programming Breadth-First Search Matrix

52.2% acceptance

Feb 25, 2026

4265

113

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn max_distance(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    let mut dist = vec![vec![-1i32; n]; n];
    let mut queue = VecDeque::new();
    let mut has_land = false;
    let mut has_water = false;
    for i in 0..n {
      for j in 0..n {
        if grid[i][j] == 1 {
          dist[i][j] = 0;
          queue.push_back((i, j));
          has_land = true;
        } else {
          has_water = true;
        }
      }
    }
    if !has_land || !has_water { return -1; }
    let mut ans = -1;
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    while let Some((r, c)) = queue.pop_front() {
      for (dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < n as i32 && nc >= 0 && nc < n as i32 {
          let (nr, nc) = (nr as usize, nc as usize);
          if dist[nr][nc] == -1 {
            dist[nr][nc] = dist[r][c] + 1;
            ans = ans.max(dist[nr][nc]);
            queue.push_back((nr, nc));
          }
        }
      }
    }
    ans
  }
}