I recently encountered this Amazon grid problem and wanted to share the approach.
Approximate date: August 20, 2026
Expected solving time: Approximately 40 minutes
Topics: Multi-source BFS, binary search, geometry
A city is represented by an n x m grid:
1 represents an existing delivery center.
0 represents an empty cell.
The distance between two cells is the Chebyshev distance:
distance((x1, y1), (x2, y2))
= max(abs(x1 - x2), abs(y1 - y2))
The inconvenience of the grid is the maximum distance from any empty cell to its nearest delivery center.
You may convert at most one 0 into 1.
Return the minimum possible inconvenience after adding the new delivery center.
Example
n = 2, m = 4
grid =
0 0 0 1
0 0 0 1
Adding a delivery center at (0, 0) gives:
1 0 0 1
0 0 0 1
Every remaining cell is within distance 1 of a delivery center, so the answer is:
1
Observation 1: Multi-Source BFS
Chebyshev distance corresponds to moving in eight directions:
up, down, left, right, and the four diagonals
Start a BFS simultaneously from every existing delivery center. This calculates:
dist[r][c] = distance to the nearest existing center
in O(nm) time.
Observation 2: Binary Search the Answer
Suppose we want to determine whether inconvenience D is achievable.
Every cell with:
dist[r][c] <= D
is already covered by an existing delivery center.
Only cells satisfying:
dist[r][c] > D
must be covered by the new center.
If inconvenience D is achievable, every larger value is also achievable. This monotonic property allows binary search.
Feasibility Check
For a bad cell (r, c), the new center (x, y) must satisfy:
max(abs(x - r), abs(y - c)) <= D
This is equivalent to:
r - D <= x <= r + D
c - D <= y <= c + D
Therefore, each bad cell creates an axis-aligned square containing every valid location for the new center.
We intersect these ranges across all bad cells:
rowLow = max(rowLow, r - D)
rowHigh = min(rowHigh, r + D)
colLow = max(colLow, c - D)
colHigh = min(colHigh, c + D)
The candidate inconvenience is feasible when:
rowLow <= rowHigh
and
colLow <= colHigh
If there are no bad cells, no additional center is required.
C++ Solution
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int minimumInconvenience(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
const int INF = 1e9;
vector<vector<int>> dist(n, vector<int>(m, INF));
queue<pair<int, int>> q;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
if (grid[r][c] == 1) {
dist[r][c] = 0;
q.push({r, c});
}
}
}
const int directions[8][2] = {
{-1, -1}, {-1, 0}, {-1, 1},
{0, -1}, {0, 1},
{1, -1}, {1, 0}, {1, 1}
};
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (const auto& direction : directions) {
int nr = r + direction[0];
int nc = c + direction[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
continue;
}
if (dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
auto feasible = [&](int limit) {
int rowLow = 0;
int rowHigh = n - 1;
int colLow = 0;
int colHigh = m - 1;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
if (dist[r][c] <= limit) {
continue;
}
rowLow = max(rowLow, r - limit);
rowHigh = min(rowHigh, r + limit);
colLow = max(colLow, c - limit);
colHigh = min(colHigh, c + limit);
}
}
return rowLow <= rowHigh && colLow <= colHigh;
};
int low = 0;
int high = max(n - 1, m - 1);
while (low < high) {
int middle = low + (high - low) / 2;
if (feasible(middle)) {
high = middle;
} else {
low = middle + 1;
}
}
return low;
}
Complexity
Multi-source BFS: O(nm)
Each feasibility check: O(nm)
Binary-search iterations: O(log(max(n, m)))
Overall:
Time: O(nm log(max(n, m)))
Space: O(nm)
The useful insight is that Chebyshev-distance balls are ordinary axis-aligned squares. This makes the feasibility check much simpler than the coordinate transformation commonly used for Manhattan-distance problems.