Optimal Central Warehouse
Google● MediumINTERNONSITE INTERVIEWProblem statement
You are given an n x m binary matrix grid. A cell containing 1 is a warehouse, and a cell containing 0 is empty land.
Choose any cell inside the matrix as a central warehouse. You may choose either an empty cell or an existing warehouse.
The Manhattan distance between cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|. Minimize the sum of these distances from the chosen cell to every warehouse.
Return the zero-based coordinates of the chosen cell as [row, column]. If several cells give the same minimum total distance, return the one with the smallest row; if there is still a tie, choose the smallest column.
Function
optimalWarehouse(grid: int[][]) → int[]Examples
Example 1
grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]return = [0,2]The warehouses are at (0, 0), (0, 4), and (2, 2). Choosing the empty cell (0, 2) gives distances 2, 2, and 2, for the minimum total 6.
Example 2
grid = [[1,0,0],[0,0,0],[0,0,1]]return = [0,0]Every cell in this matrix has total distance 4 to the two warehouses. The tie-breaking rule chooses [0,0].
Example 3
grid = [[0,0],[0,1]]return = [1,1]Choosing the only existing warehouse gives total distance 0.
Constraints
1 <= n, m <= 500gridis rectangular, and every entry is0or1.- There is at least one warehouse.