01 matrix

Array Dynamic Programming Breadth-First Search Matrix

53.4% acceptance

Feb 19, 2026

10676

451

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two cells sharing a common edge is 1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;
impl Solution {
  pub fn update_matrix(mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = mat.len();
    let n = mat[0].len();
    let mut dist = vec![vec![i32::MAX; n]; m];
    let mut queue = VecDeque::new();
    for i in 0..m {
      for j in 0..n {
        if mat[i][j] == 0 { dist[i][j] = 0; queue.push_back((i, j)); }
      }
    }
    let dirs: [(i32,i32); 4] = [(-1,0),(1,0),(0,-1),(0,1)];
    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 < m as i32 && nc >= 0 && nc < n as i32 {
          let (nr, nc) = (nr as usize, nc as usize);
          if dist[nr][nc] > dist[r][c] + 1 {
            dist[nr][nc] = dist[r][c] + 1;
            queue.push_back((nr, nc));
          }
        }
      }
    }
    dist
  }
}