Minimize Delivery-Grid Inconvenience
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
# Minimize Delivery-Grid Inconvenience
A binary grid marks delivery centers with 1 and all other cells with 0. The distance between two cells is Chebyshev distance: the maximum of their absolute row and column differences. Grid inconvenience is the greatest, over all zero cells, of the distance to its nearest center. Convert at most one zero cell to one and minimize the resulting inconvenience.
### Function Signature
```text
minimize_inconvenience(grid: list[list[int]]) -> int
```
### Valid Input Domain
The grid is rectangular and nonempty, contains only zero and one, and has at least one existing delivery center.
### Exact Output Semantics
Return the minimum achievable inconvenience as an integer. If no zero cell remains, inconvenience is 0. Only the minimum value is returned, so multiple equally good center locations require no tie-break.
### Constraints
- 1 <= rows, columns <= 1,000.
- rows * columns <= 1,000,000.
- At most one zero may be converted; choosing none is allowed.
### Public Examples
#### Example 1
Input: grid = [[0, 0, 0, 1], [0, 0, 0, 1]]
Output: 1
Opening a center at the upper-left cell makes every cell at most distance 1 from a center.
#### Example 2
Input: grid = [[1]]
Output: 0
There are no zero cells, so the inconvenience is already zero.
### Hints
- For a proposed maximum distance, characterize which cells are still too far from every existing center.
- Chebyshev-distance constraints can be expressed through row-plus-column and row-minus-column bounds.
Overview: Practice placing one additional center in a binary grid to minimize the maximum Chebyshev distance to service.
A rectangular binary grid marks delivery centers with 1 and all other cells with 0. The distance between two cells is Chebyshev distance: the maximum of the absolute row difference and absolute column difference. Grid inconvenience is the greatest, over all zero cells, of the distance to its nearest center. Convert at most one zero cell to 1, including the option to make no conversion, and return the minimum achievable inconvenience. If no zero cell remains, return 0. Only the minimum value is returned; equally optimal center locations need no tie-break.
Constraints
- The grid is rectangular and nonempty, contains only 0 and 1, and has at least one existing delivery center.
- 1 <= rows, columns <= 1,000.
- rows * columns <= 1,000,000.
- At most one zero cell may be converted to one; choosing none is allowed.
- Distance is Chebyshev distance: max(abs(row difference), abs(column difference)).
- Return 0 when no zero cell remains; otherwise return the exact minimum possible maximum distance.
Examples
Input: ([[1]],)
Expected Output: 0
Explanation: The one cell is already a center, so no zero cell remains.
Input: ([[1,1,1],[1,1,1]],)
Expected Output: 0
Explanation: An all-center rectangle has inconvenience zero.
Hints
- For a proposed maximum distance, focus on the cells that are still too far from every existing center.
- A single new center must satisfy all row and column distance bounds imposed by those remaining cells.