FastPrep
Problem · Matrix

Minimum Delivery Center Inconvenience

● MediumAmazonFULLTIMENEW GRADOA
See Amazon hiring insights

Quick note: This problem is not ready for practice yet. I'll come back and work on it later. Have a lovely day! 🐥

Amazon has multiple delivery centers all over the world. A city is given in the form of a grid where the delivery centers are marked as 1 and all other places are marked as 0. Distance between two cells is defined as the maximum absolute distance between x coordinates and y coordinates. For example, distance between (1, 2) and (0, 4) is max(|1 - 0|, |2 - 4|) = 2. The inconvenience of the grid is defined as the maximal distance of any place marked 0 from its nearest delivery center.

Amazon is planning to open a new delivery center to reduce the inconvenience of the grid. Minimize the inconvenience of the grid by converting at most one 0 (any place) to 1 (a delivery center) and report this minimum value.

Examples
01 · Example 1
grid = [[0,0,0,1],[0,0,0,1]]
return = 1

Given n = 2 rows, m = 4 columns, and grid = [[0, 0, 0, 1], [0, 0, 0, 1]]:

0001
0001

Distances to nearest delivery centers are shown below. The initial inconvenience of the grid is 3.

3210
3210

It is optimal to convert (0, 0) to a delivery center, resulting in:

1001
0001

Now the inconvenience is 1, with distances as:

0110
1110
Constraints
  • 1 <= n, m <= 300
  • 0 <= grid[i][j] <= 1

Updated on June 27, 2026: today's source lists the grid size limit as 300, so I updated this constraint to match it. 🐣

More Amazon problems
drafts saved locally
public int minimizeInconvenience(int[][] grid) {
  // write your code here
}
grid[[0,0,0,1],[0,0,0,1]]
expected1
checking account