LeetCode Problem 3648

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

The problem gives an n × m grid where each cell is identified by coordinates (r, c). A sensor can be placed on any cell, and its coverage is defined using Chebyshev distance. Specifically, a sensor at (r, c) covers every cell (r2, c2) such that max(|r - r2|, |c - c2|) ≤ k.

This means each sensor covers a square region centered at its position, extending k cells in all four directions, forming a square of side length 2k + 1, clipped by the grid boundaries.

The task is to determine the minimum number of sensors needed so that every cell in the grid is covered by at least one sensor.

The input consists of three integers: n and m define the grid dimensions, and k defines the sensor range. The output is a single integer representing the minimum number of sensors required.

The constraints 1 <= n, m <= 1000 and 0 <= k <= 1000 indicate that the grid can be large, so any solution that tries to simulate placement cell by cell or uses exhaustive search will be too slow. This strongly suggests a mathematical or greedy tiling insight is required.

Important edge cases include k = 0, where each sensor covers only one cell, requiring n * m sensors, and cases where k is large enough that a single sensor can cover the entire grid. Another subtle case is when the grid dimensions are not multiples of the coverage size 2k + 1, requiring careful handling of partial coverage at boundaries.

Approaches

Brute Force Approach

A brute-force strategy would treat this as a set cover problem. Each possible sensor placement defines a square coverage region, and the goal would be to select the smallest subset of these placements such that all grid cells are covered. This can be modeled as trying all combinations of sensor positions and checking coverage.

While correct in principle, this approach is computationally infeasible. The number of possible sensor placements is n × m, and choosing subsets leads to exponential complexity. Even greedy simulation per cell would be too slow at the upper constraints.

Key Insight and Optimal Approach

The key observation is that each sensor covers a fixed (2k + 1) × (2k + 1) square region. This transforms the problem into a deterministic geometric tiling problem.

Instead of thinking about arbitrary placements, we can observe that the optimal strategy is to partition the grid into disjoint squares of side length 2k + 1. Placing one sensor per such block ensures full coverage, because every cell in a block is within Chebyshev distance k of the block’s sensor.

This reduces the problem to counting how many such blocks are needed to tile an n × m grid, which is simply:

• Number of rows of blocks: ceil(n / (2k + 1))
• Number of columns of blocks: ceil(m / (2k + 1))

Multiplying these gives the minimum number of sensors.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(nm) or more	Tries all sensor subsets as set cover
Optimal	O(1)	O(1)	Uses geometric tiling with fixed coverage squares

Algorithm Walkthrough

1. First compute the effective coverage length of a single sensor in one dimension, which is side = 2k + 1. This represents how far a sensor can extend in all directions, forming a square region.
2. Determine how many full coverage blocks are needed along the vertical dimension. This is computed as ceil(n / side). Each block of height side can be fully covered by one sensor placed appropriately inside it.
3. Similarly, compute how many blocks are needed along the horizontal dimension as ceil(m / side).
4. Multiply the number of vertical blocks by the number of horizontal blocks. Each block intersection corresponds to one sensor placement, ensuring full coverage of the grid.
5. Return this product as the final answer.

The reasoning for integer ceiling division is implemented using (x + side - 1) // side, which ensures correct rounding up without floating-point operations.

Why it works

This approach works because Chebyshev distance coverage forms perfect axis-aligned squares. Any cell within a (2k + 1) × (2k + 1) region is guaranteed to be covered by a single sensor placed anywhere inside that region. By partitioning the grid into minimal disjoint such squares, we ensure full coverage with no redundancy, and any attempt to reduce the number of sensors would leave at least one uncovered region. The problem requires finding the minimum number of sensors needed to cover an n × m grid. Each sensor placed at a cell (r, c) covers all cells within Chebyshev distance k. The Chebyshev distance is defined as max(|r1 - r2|, |c1 - c2|), which means a sensor covers a square region centered on its location with side length 2k + 1.

In other words, the sensor's coverage is a square of side 2k + 1, and our goal is to place as few sensors as possible to cover the entire grid.

The inputs are the integers n (number of rows), m (number of columns), and k (coverage radius). The output is a single integer: the minimum number of sensors needed to cover every cell.

Key constraints include 1 <= n, m <= 10^3 and 0 <= k <= 10^3. These constraints indicate that the grid can be large, but a solution must avoid checking every cell individually with every possible sensor position, as that would be too slow.

Important edge cases include:

1. k = 0, where each sensor only covers a single cell, so every cell needs a sensor.
2. k >= n or k >= m, where one sensor can cover the entire grid.
3. Small grids like 1x1 or 1xN/Nx1 to ensure coverage calculations handle single rows or columns.

Approaches

Brute Force

The brute-force method would attempt to place sensors in every possible combination and check if the entire grid is covered. While this guarantees a correct answer, the approach is infeasible for large grids due to the combinatorial explosion. For example, checking every possible subset of cells in a 1000x1000 grid is computationally impossible.

Key Insight for Optimal Solution

The key observation is that each sensor covers a square of side length 2k + 1. Therefore, we can tile the grid with non-overlapping or minimally overlapping squares of size 2k + 1 to cover all cells. This turns the problem into a tiling problem, where the minimum number of sensors corresponds to the minimum number of ceil(n / (2k + 1)) rows and ceil(m / (2k + 1)) columns of squares needed to cover the grid.

This approach works because placing a sensor in each square region of size 2k + 1 guarantees complete coverage with minimal overlap, which ensures the minimum number of sensors.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(n*m))	O(n*m)	Attempts every combination of sensor placements; impractical
Optimal	O(1)	O(1)	Direct calculation using grid tiling and ceiling division

Algorithm Walkthrough

1. Calculate the size of the square that one sensor covers. Since Chebyshev distance k means the sensor covers 2k + 1 cells in both dimensions, store this value as cover_size = 2 * k + 1.
2. Compute the number of sensors required along the rows. Since each sensor covers cover_size rows, the minimum number of sensors needed for all rows is ceil(n / cover_size).
3. Compute the number of sensors required along the columns. Similarly, each sensor covers cover_size columns, so the minimum number of sensors needed for all columns is ceil(m / cover_size).
4. Multiply the number of sensors along the rows by the number along the columns. This gives the total minimum number of sensors required to cover the entire grid.

Why it works: This algorithm guarantees that every cell is within a cover_size square from at least one sensor. By tiling the grid with these squares, we ensure full coverage, and using ceiling division ensures that partially filled edges of the grid are still covered.

Python Solution

class Solution:
    def minSensors(self, n: int, m: int, k: int) -> int:
        side = 2 * k + 1
        
        rows = (n + side - 1) // side
        cols = (m + side - 1) // side
        
        return rows * cols

The implementation first computes the coverage side length induced by a sensor. It then calculates how many such segments are needed to cover the grid dimensions using ceiling division. Finally, it multiplies the two values to determine how many sensors are required in total, corresponding to one sensor per block in the optimal tiling. import math

class Solution: def minSensors(self, n: int, m: int, k: int) -> int: cover_size = 2 * k + 1 rows_needed = math.ceil(n / cover_size) cols_needed = math.ceil(m / cover_size) return rows_needed * cols_needed

The implementation first computes the `cover_size` of each sensor. Then it uses `math.ceil` to determine how many sensors are required along rows and columns to ensure full coverage, and finally multiplies these counts to get the total number of sensors.

## Go Solution

```go
func minSensors(n int, m int, k int) int {
    side := 2*k + 1

    rows := (n + side - 1) / side
    cols := (m + side - 1) / side

    return rows * cols
}

The Go implementation mirrors the Python logic exactly. Integer arithmetic in Go naturally performs floor division, so ceiling division is implemented using the same (x + side - 1) / side pattern. No additional data structures are needed. import "math"

func minSensors(n int, m int, k int) int { coverSize := 2*k + 1 rowsNeeded := int(math.Ceil(float64(n) / float64(coverSize))) colsNeeded := int(math.Ceil(float64(m) / float64(coverSize))) return rowsNeeded * colsNeeded }

In Go, `math.Ceil` requires converting integers to `float64`, then casting the result back to `int`. Otherwise, the algorithm is identical to the Python solution, using the same tiling principle.

## Worked Examples

### Example 1: n = 5, m = 5, k = 1

Here `side = 2 * 1 + 1 = 3`.

We compute:

- rows = ceil(5 / 3) = 2
- cols = ceil(5 / 3) = 2

So total sensors = 2 × 2 = 4.

The grid is effectively divided into four 3×3 regions (with boundary truncation), and each region needs one sensor.

### Example 2: n = 2, m = 2, k = 2

Here `side = 2 * 2 + 1 = 5`.

We compute:

- rows = ceil(2 / 5) = 1
- cols = ceil(2 / 5) = 1

So total sensors = 1 × 1 = 1.

A single sensor placed anywhere covers the entire grid since its coverage exceeds grid dimensions.
`cover_size = 2 * 1 + 1 = 3`

`rows_needed = ceil(5 / 3) = 2`

`cols_needed = ceil(5 / 3) = 2`

Total sensors = `2 * 2 = 4`

### Example 2: n = 2, m = 2, k = 2

`cover_size = 2 * 2 + 1 = 5`

`rows_needed = ceil(2 / 5) = 1`

`cols_needed = ceil(2 / 5) = 1`

Total sensors = `1 * 1 = 1`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(1) | Only a few arithmetic operations are performed |
| Space | O(1) | No auxiliary data structures are used |

The solution is constant time because it reduces the problem to a direct mathematical formula independent of grid size beyond arithmetic computation.
| Time | O(1) | Only a few arithmetic operations and ceiling calculations are performed |
| Space | O(1) | Only a few integer variables are stored; no additional data structures needed |

The algorithm is highly efficient because it reduces the problem to simple arithmetic based on grid size and sensor coverage.

## Test Cases

assert Solution().minSensors(5, 5, 1) == 4 # basic tiling case assert Solution().minSensors(2, 2, 2) == 1 # single sensor covers entire grid assert Solution().minSensors(1, 1, 0) == 1 # single cell, zero range assert Solution().minSensors(10, 10, 0) == 100 # no coverage expansion assert Solution().minSensors(10, 10, 1) == 16 # 3x3 blocks over 10x10 grid assert Solution().minSensors(1000, 1000, 1000) == 1 # huge coverage

Provided examples

assert Solution().minSensors(5, 5, 1) == 4 # Standard 5x5 grid with k=1 assert Solution().minSensors(2, 2, 2) == 1 # Small grid fully covered by one sensor

Edge cases

assert Solution().minSensors(1, 1, 0) == 1 # Single cell, k=0 assert Solution().minSensors(1, 1000, 0) == 1000 # Row of length 1000, k=0 assert Solution().minSensors(1000, 1, 0) == 1000 # Column of length 1000, k=0 assert Solution().minSensors(1000, 1000, 1000) == 1 # Large grid, k covers entire grid

Other cases

assert Solution().minSensors(10, 15, 2) == 6 # General rectangle assert Solution().minSensors(7, 7, 3) == 1 # k large enough to cover entire grid assert Solution().minSensors(6, 8, 1) == 6 # Rectangle requiring multiple sensors

| Test | Why |
| --- | --- |
| (5,5,1) | verifies standard multi-block tiling |
| (2,2,2) | checks full grid coverage by one sensor |
| (1,1,0) | minimal grid with zero radius |
| (10,10,0) | ensures degenerate case becomes n*m |
| (10,10,1) | checks partial tiling and ceiling behavior |
| (1000,1000,1000) | stress test for large k dominance |

## Edge Cases

One important edge case is when `k = 0`. In this scenario, each sensor only covers its own cell, since the Chebyshev distance constraint reduces to zero. The algorithm correctly handles this because `side = 1`, and thus both `ceil(n/1)` and `ceil(m/1)` produce `n` and `m`, resulting in `n × m` sensors.

Another edge case occurs when `k` is large enough that `2k + 1` exceeds both `n` and `m`. In this case, the entire grid fits within a single coverage square, and the formula correctly returns `1` due to ceiling division of both dimensions by a value larger than the grid.

A third edge case is when grid dimensions are not divisible by `2k + 1`. In such cases, naive multiplication of integer division results would underestimate coverage. The use of ceiling division ensures that even partial leftover strips of the grid are accounted for as additional sensor regions, preventing uncovered cells at the boundaries.
| (5,5,1) | Basic case to validate correct tiling calculation |
| (2,2,2) | Small grid fully covered by one sensor |
| (1,1,0) | Minimum grid and zero coverage radius |
| (1,1000,0) | Single row with zero coverage |
| (1000,1,0) | Single column with zero coverage |
| (1000,1000,1000) | Large grid fully covered by one sensor |
| (10,15,2) | Rectangular grid where multiple sensors are required |
| (7,7,3) | Large k covering grid completely |
| (6,8,1) | Non-square grid requiring careful tiling |

## Edge Cases

**1. Zero coverage (k=0)**

When `k=0`, each sensor only covers its own cell. Any naive solution that assumes coverage over multiple cells would fail. Our implementation correctly handles this because `cover_size = 1` and each cell is effectively counted individually.

**2. Large k covering the entire grid**

If `k >= n` or `k >= m`, a single sensor can cover the entire grid. Our formula naturally handles this, since `ceil(n / cover_size)` and `ceil(m / cover_size)` will both equal 1 when `cover_size` is larger than the respective dimension.

**3. Non-square grids**

Grids where `n != m` require independent tiling along rows and columns. The algorithm accounts for this by computing rows and columns separately and multiplying them to get the total number of sensors, ensuring no cells are left uncovered.