FastPrepBest Meeting Point
Problem · Array

Best Meeting Point

Learn this problem
● HardWalmart logoWalmartFULLTIMEOA

Problem statement

You are given a rectangular binary grid. Each cell containing 1 is a home, and each cell containing 0 is empty.

Choose any grid cell as a meeting point. A person at (r, c) travels to (x, y) with Manhattan distance |r - x| + |c - y|.

Return the minimum possible sum of travel distances from every home to one meeting point.

Function

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

Examples

Example 1

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

Meeting at row 0, column 2 gives distances 2, 2, and 2.

Example 2

grid = [[1,1]]return = 1

Either cell is an optimal meeting point.

Constraints

  • 1 <= grid.length, grid[0].length <= 200.
  • Every cell is 0 or 1.
  • The grid contains at least one home.

More Walmart problems

drafts saved locally
public int minTotalDistance(int[][] grid) {
    // write your code here
}
grid[[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
expected6
checking account