FastPrepBest Starting Cell for Restaurant Distance

Best Starting Cell for Restaurant Distance

DoorDash logoDoorDash● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given a binary matrix grid. A cell containing 1 is a restaurant. Choose a starting cell that minimizes the total Manhattan distance to all restaurants.

For this exercise, any cell may be chosen, including a restaurant cell. There are no obstacles. The distance from (r, c) to (x, y) is |r - x| + |c - y|, and the objective is the sum of these distances.

Return [row, column, totalDistance] using zero-based coordinates. If several cells have the same total, choose the smallest row, then the smallest column. If there are no restaurants, return [0, 0, 0].

Function

bestStartingCell(grid: int[][]) → int[]

Examples

Example 1

grid = [[1,0,0],[0,0,1],[1,0,0]]return = [1,0,4]

From (1,0), the distances to restaurants (0,0), (1,2), and (2,0) are 1, 2, and 1. Their sum is 4, the minimum.

Example 2

grid = [[1,0,1],[0,0,0]]return = [0,0,2]

Every cell in row 0 from column 0 through 2 has total distance 2. The tie rule selects (0,0), which is itself a restaurant.

Example 3

grid = [[0,0],[0,0]]return = [0,0,0]

With no restaurants, every total is zero and the specified result is [0,0,0].

Constraints

  • 1 <= grid.length <= 200
  • 1 <= grid[i].length <= 200
  • 0 <= grid[i][j] <= 1
  • All rows have the same length.

More DoorDash problems

All DoorDash interview questionsSee DoorDash hiring insights
Saved
public int[] bestStartingCell(int[][] grid) {
    // Write your code here.
}
Checking account…