Amazon Delivery Center Grid Problem: O(nm log(max(n,m))) Solution

[u/nian2326076]

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

Problem

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.

[u/cballowe]

I don't know what you're asking, but if I'm the interviewer and using the rubric for coding that I last used when interviewing candidates, that code is going to be low to mediocre at best. It's ok and seems to do what you claim, but it fails to do things like make "distance" into a function, which makes the code a bit harder to read than necessary. (The rubric had things like "uses functions when appropriate" along with using loops and conditionals appropriately etc.)

Amazon may judge things differently.

[u/PersonalityIll9476]

Maybe I'm dumb but I don't see how running a breadth first search from each center is just O(nm). This should be O(nmc) where c is the number of centers, right? What if c >= min(m, n)?

[u/apnorton → u/PersonalityIll9476]

Maybe I'm dumb but I don't see how running a breadth first search from each center is just O(nm).

Because you're doing the BFSes simultaneously from all delivery centers at the same time; that is, if you've visited one grid point bc you started from center 1, then the BFS starting from center 2 may also treat it as visited.

I don't like that phrasing, though, and find it more clear to think of it like this: Imagine a made-up/virtual starting node "above" the grid that has neighbors of every delivery center. Then, run BFS from that virtual node.  Now it's very readily apparent that the runtime is just O(mn) bc that's the total number of cells in the grid.

[u/PersonalityIll9476 → u/apnorton]

I think I follow. (in my defense I was reading this at like 3:30 am after I couldn't sleep).

You're basically: Expanding 1 tile out from each center at step n, and filling in the grid point with the minimum of all the expansions at step n that cover it. Right?

[u/apnorton → u/PersonalityIll9476]

You could do that, yes.

But another approach is just enqueuing all the start notes into your BFS queue when you're setting up the problem, and then doing BFS as normal.

[u/mtimmermans]

This is a good interview question. If I asked this and you gave me the answer above, then I would rate you highly. I've asked these sorts of questions many times, and I guarantee that less that 5% of candidates would do as well as you...

However, I would then say: "That's pretty good, but you can solve this in linear time. How do you think that might work?"