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.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
int m, n;
vector> dist;
bool can(int D)
{
int uLow = -1000000000;
int uHigh = 1000000000;
int vLow = -1000000000;
int vHigh = 1000000000;
bool hasBad = false;
for (int r = 0; r < m; r++)
{
for (int c = 0; c < n; c++)
{
if (dist[r][c] > D)
{
hasBad = true;
int u = r + c;
int v = r - c;
uLow = max(uLow, u - D);
uHigh = min(uHigh, u + D);
vLow = max(vLow, v - D);
vHigh = min(vHigh, v + D);
}
}
}
if (!hasBad)
return true;
if (uLow > uHigh || vLow > vHigh)
return false;
for (int r = 0; r < m; r++)
{
int lowC = max(0, max(uLow - r, r - vHigh));
int highC = min(n - 1, min(uHigh - r, r - vLow));
if (lowC <= highC)
return true;
}
return false;
}
public:
int minimize_inconvenience(const vector>& grid)
{
m = grid.size();
n = grid[0].size();
dist.assign(m, vector(n, -1));
queue> q;
for (int r = 0; r < m; r++)
{
for (int c = 0; c < n; c++)
{
if (grid[r][c] == 1)
{
dist[r][c] = 0;
q.push({r, c});
}
}
}
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int maxDist = 0;
while (!q.empty())
{
auto [r, c] = q.front();
q.pop();
maxDist = max(maxDist, dist[r][c]);
for (int k = 0; k < 8; k++)
{
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= m || nc < 0 || nc >= n)
continue;
if (dist[nr][nc] != -1)
continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
int left = 0;
int right = maxDist;
while (left < right)
{
int mid = left + (right - left) / 2;
if (can(mid))
right = mid;
else
left = mid + 1;
}
return
Answer by Coderka14
#include
using namespace std;
class Solution
{
int rows, cols;
vector> dist;
bool can(int D)
{
int minRow = rows;
int maxRow = -1;
int minCol = cols;
int maxCol = -1;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (dist[r][c] > D)
{
minRow = min(minRow, r);
maxRow = max(maxRow, r);
minCol = min(minCol, c);
maxCol = max(maxCol, c);
}
}
}
if (maxRow == -1)
return true;
return maxRow - minRow <= 2 * D &&
maxCol - minCol <= 2 * D;
}
public:
int minimize_inconvenience(const vector>& grid)
{
rows = grid.size();
cols = grid[0].size();
dist.assign(rows, vector(cols, -1));
queue> q;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (grid[r][c] == 1)
{
dist[r][c] = 0;
q.push({r, c});
}
}
}
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int maxDist = 0;
while (!q.empty())
{
auto [r, c] = q.front();
q.pop();
maxDist = max(maxDist, dist[r][c]);
for (int k = 0; k < 8; k++)
{
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols)
continue;
if (dist[nr][nc] != -1)
continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
int left = 0;
int right = maxDist;
while (left < right)
{
int mid = left + (right - left) / 2;
if (can(mid))
right = mid;
else
left = mid + 1;
}
return left;
}
};
right = mid;
else
left = mid + 1;
}
return left;
}
};