One More Hub
HardGraphs ยท Amazon
grid marks each cell 1 if it holds a hub and 0 if it is empty. The distance between cells (r1, c1) and (r2, c2) is max(|r1 - r2|, |c1 - c2|).
The worst distance of a grid is the largest distance from any empty cell to its nearest hub, or 0 if no cell is empty. You may turn at most one empty cell into a hub. Return the smallest worst distance you can reach.
Example 1
- Input:
- grid = [[1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1]]
- Output:
- 3
- Explanation
- The worst distance starts at 4. A new hub at
(2, 3)brings every empty cell within 3 of a hub, and no single cell does better.
Example 2
- Input:
- grid = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
- Output:
- 2
- Explanation
- The four corners are 2 from the centre hub, and one new hub can fix at most one of them.
Example 3
- Input:
- grid = [[1, 0, 0, 0, 0, 0, 0, 0, 0]]
- Output:
- 3
Constraints
1 <= grid.length <= 1001 <= grid[r].length <= 100, and every row has the same lengthgrid[r][c]is0or1- At least one cell is
1