Minimum sensors to cover grid

Math

68.7% acceptance

Feb 25, 2026

You are given n x m grid and an integer k. A sensor placed on cell (r, c) covers all cells whose Chebyshev distance from (r, c) is at most k. The Chebyshev distance between two cells (r1, c1) and (r2, c2) is max(|r1-r2|, |c1-c2|). Your task is to return the minimum number of sensors required to cover every cell of the grid.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_sensors(n: i32, m: i32, k: i32) -> i32 {
    // A sensor at (r, c) covers a (2k+1) x (2k+1) square.
    // We need to cover all n x m cells.
    // Greedy tiling: place sensors at (k, k), (k, 3k+1), (k, 5k+2), ...
    // i.e., step of (2k+1) in each dimension.
    // Number of sensors = ceil(n / (2k+1)) * ceil(m / (2k+1))
    let side = 2 * k + 1;
    let rows_needed = (n + side - 1) / side;
    let cols_needed = (m + side - 1) / side;
    rows_needed * cols_needed
  }
}