Amazon | SDE-1 | Online Assessment | 2026 Grad | 50Lakhs CTC
Amazon has multiple delivery centers. 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.
The distance between two cells is defined as the maximum absolute difference between their row and column coordinates:
max(∣x1−x2∣,∣y1−y2∣)
For example, the distance between (1,2) and (0,4) is:
max(∣1−0∣,∣2−4∣)=2
The inconvenience of the grid is defined as the maximum distance of any cell marked 0 from its nearest delivery center.
Amazon is planning to open one new delivery center to reduce the inconvenience. You may convert at most one 0 cell into 1, and you must report the minimum possible inconvenience after doing so.
Example
Given:
n=2, m=4
grid =
[0 0 0 1
0 0 0 1]
The optimal choice is to convert cell (0,0) into a delivery center, and the minimum inconvenience becomes 1.


