Quick Overview

Add at most one delivery center to minimize the maximum Chebyshev distance from ordinary grid cells to their nearest center.

Minimize Grid Inconvenience by Adding One Delivery Center

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A binary grid represents delivery coverage: `1` marks a delivery center and `0` marks an ordinary location. The distance between cells `(r1, c1)` and `(r2, c2)` is the Chebyshev distance `max(abs(r1 - r2), abs(c1 - c2))`. The grid's inconvenience is the largest distance from any ordinary location to its nearest delivery center. You may convert at most one `0` cell into a delivery center. Return the minimum possible inconvenience after this optional conversion. ### Function Contract Implement `getMinInconvenience(grid) -> int`, where `grid` is a rectangular integer matrix. Return the optimal inconvenience value, not the position of the new center. ### Constraints and Clarifications - `1 <= number of rows <= 500`. - `1 <= number of columns <= 500`. - Every entry is `0` or `1`. - Existing delivery centers remain in place. - Distances depend only on coordinates; there are no obstacles or path restrictions. - The grid may initially contain no delivery center. In that case, placing one center is allowed and makes the final distances well defined. - As an explicit edge-case convention, a final grid with no ordinary locations has inconvenience `0`. - Adding no center is permitted when the existing arrangement is already optimal. ### Examples ```text grid = [[0, 0, 0, 1], [0, 0, 0, 1]] Output: 1 ``` Converting `(0, 0)` to a center leaves every ordinary location within Chebyshev distance `1` of a center. Zero inconvenience is impossible because ordinary locations remain. ```text grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] Output: 2 ``` Placing the center at `(1, 1)` achieves inconvenience `2`. No single center can be within distance `1` of both the first and last columns. ```hint Focus on locations that existing centers do not cover For a proposed maximum distance, only some ordinary locations still need help. Determine whether one grid position could cover every such location under the stated distance formula. ```

Overview: Add at most one delivery center to minimize the maximum Chebyshev distance from ordinary grid cells to their nearest center.

A binary grid represents delivery coverage. A cell holding `1` is a delivery center and a cell holding `0` is an ordinary location. The distance between cells `(r1, c1)` and `(r2, c2)` is the Chebyshev distance `max(abs(r1 - r2), abs(c1 - c2))`. The inconvenience of a grid is the largest distance from any ordinary location to its nearest delivery center. You may convert at most one `0` cell into a delivery center. Existing delivery centers remain in place, and a converted cell stops being an ordinary location. Return the minimum possible inconvenience after this optional conversion, that is, the optimal inconvenience value itself and not the position of the new center. Two conventions fix the degenerate situations: - As an explicit edge-case convention, a final grid with no ordinary locations has inconvenience `0`. - The grid may initially contain no delivery center. In that case, placing one center is allowed and makes the final distances well defined. Adding no center is permitted when the existing arrangement is already optimal. Distances depend only on coordinates; there are no obstacles or path restrictions. Example 1: ```text grid = [[0, 0, 0, 1], [0, 0, 0, 1]] Output: 1 ``` Converting `(0, 0)` to a center leaves every ordinary location within Chebyshev distance `1` of a center. Zero inconvenience is impossible because ordinary locations remain. Example 2: ```text grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] Output: 2 ``` Placing the center at `(1, 1)` achieves inconvenience `2`. No single center can be within distance `1` of both the first and last columns.

Constraints

  • 1 <= number of rows <= 500.
  • 1 <= number of columns <= 500.
  • grid is a rectangular integer matrix: every row has the same number of columns.
  • Every entry is 0 or 1.
  • At most one 0 cell may be converted into a delivery center; existing delivery centers remain in place.
  • Distances use the Chebyshev formula max(abs(r1 - r2), abs(c1 - c2)); distances depend only on coordinates, and there are no obstacles or path restrictions.
  • The grid may initially contain no delivery center. In that case, placing one center is allowed and makes the final distances well defined.
  • As an explicit edge-case convention, a final grid with no ordinary locations has inconvenience 0.
  • Adding no center is permitted when the existing arrangement is already optimal.
  • The returned value is an integer between 0 and 499 inclusive, so it fits comfortably in a 32-bit signed integer.

Examples

Input: ([[0]],)

Expected Output: 0

Explanation: Minimum valid grid with no center: converting the only cell leaves no ordinary location, so the inconvenience is 0.

Input: ([[1]],)

Expected Output: 0

Explanation: A 1x1 grid that is already a center has no ordinary location, so the inconvenience is 0.

Hints

  1. Under the stated distance formula, the set of cells within distance d of a fixed cell is an axis-aligned square, not a diamond.
  2. Focus on locations that the existing centers do not cover: for a proposed maximum distance, only some ordinary locations still need help.
  3. Rather than deciding where the new center should go, first ask whether a proposed maximum distance is achievable at all, and determine whether one grid position could cover every still-uncovered location under the stated distance formula.

Loading coding console...

Show the approach

Approach

Step 1 - distance to the existing centers. A single Chebyshev step is exactly one move on the 8-neighbour grid graph, so a multi-source breadth-first search seeded with every cell holding 1 computes dist[r][c], the Chebyshev distance from (r, c) to the nearest existing center, in O(rows * cols). When the grid holds no center at all the queue starts empty and every cell keeps the sentinel rows + cols + 1, which is strictly larger than any candidate answer, so those cells always count as uncovered.

Step 2 - decide a target instead of a position. Define feasible(k) to be true when some allowed action (convert one 0 cell, or convert nothing) leaves inconvenience at most k. Let S(k) be the set of ordinary cells whose dist exceeds k.

  • If S(k) is empty, doing nothing already achieves at most k, so feasible(k) is true.
  • Otherwise the one new center at position p must satisfy max(abs(qr - pr), abs(qc - pc)) <= k for every q in S(k), because those cells get no help from the existing centers. The set of positions within Chebyshev distance k of q is the axis-aligned square [qr - k, qr + k] x [qc - k, qc + k], so the admissible positions form the intersection rectangle rows [maxR - k, minR + k] and columns [maxC - k, minC + k], where minR/maxR/minC/maxC are the bounding box of S(k). That rectangle is non-empty exactly when maxR - minR <= 2k and maxC - minC <= 2k.

Two small invariants make the bounding-box test exact rather than merely necessary. First, a non-empty rectangle always meets the grid: its lower bound maxR - k is at most rows - 1 and its upper bound minR + k is at least 0, and likewise for columns, so clipping to the grid can never empty it. Second, every cell x inside the rectangle is guaranteed to hold 0: if x held 1, then every q in S(k) would be within Chebyshev distance k of the existing center x, contradicting dist[q] > k. So the required '0 cell' restriction on the conversion never rules out a rectangle position, and no separate search for a convertible cell is needed.

Conversely, if some action achieves at most k, then either nothing was converted (S(k) is empty) or the converted cell p covers all of S(k) within k, forcing the bounding-box spans to be at most 2k. So feasible(k) is exactly the achievability predicate.

Step 3 - monotonicity and search. As k grows, S(k) shrinks and 2k grows, so feasible is monotone. Binary search over k in [0, max(rows, cols) - 1]; the top of that range is always feasible because any two cells of the grid are within that Chebyshev distance of each other. Each evaluation rescans the grid, giving O(rows * cols * log(max(rows, cols))) time and O(rows * cols) space.

Edge cases. A grid with no center at all keeps every ordinary cell in S(k), so the answer comes purely from the placement, for example an all-zero 3x4 grid gives 2. A grid with no ordinary location (all ones) has S(0) empty and returns 0. A grid whose only ordinary location is consumed by the conversion, such as [[1, 0]], returns 0, which the predicate captures because a singleton S has zero span. Single-row, single-column and 1x1 grids are handled by the same code path: the binary search range collapses and the span tests are taken in one dimension only. Converting is never forced, so cases where no conversion helps simply return the current maximum distance.

Time complexity:
O(rows * cols * log(max(rows, cols)))
Space complexity:
O(rows * cols)