Map of highest peak

Array Breadth-First Search Matrix

75.7% acceptance

Feb 25, 2026

1548

112

You are given an integer matrix isWater of size m x n that represents a map of land and water cells. If isWater[i][j] == 0, cell (i, j) is a land cell. If isWater[i][j] == 1, cell (i, j) is a water cell. You must assign each cell a height such that water cells have height 0, and adjacent cells differ by at most 1. Find an assignment of heights such that the maximum height in the matrix is maximized. Return an integer matrix height of size m x n.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;

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