Problem Statement

You are given m x n matrix containing 1 and 0 digits only, where each 1 represents the home of one friend, return the minimum total travel distance.

The minimal total travel distance is defined as a sum of distances between each friend's house and meeting point. Here, you need to find the meeting point such that it should have minimal distance from the home of each friend.

The distance is calculated as the Manhattan distance, which is the sum of the absolute differences in the horizontal and vertical coordinates (distance(a1, a2) = |a2.x - a1.x| + |a2.y - a1.y|).

Example

Example 1:

• Input:

[[1,0],
 [0,1]]

• Expected Output: 2
• Justification: There are two people located at the top-left and bottom-right corners. The best meeting point is either of the two empty cells, each resulting in a total distance of 2.

Example 2:

• Input:

[[1,0,1],
 [0,1,0],
 [1,0,1]]

• Expected Output: 8
• Justification: The grid has four people at the corners and one in the center. The best meeting points are the four cells adjacent to the center cell (either horizontally or vertically), each resulting in a total distance of 8.

Example 3:

• Input:

[[1,1,0],
 [0,0,1],
 [0,0,1]]

• Expected Output: 6
• Justification: People are located at the top two corners and the bottom two cells of the rightmost column. The optimal meeting point is the cell in the second row, center, or rightmost column, with a total distance of 6. This point is vertically central and at the horizontal edge, closest to the majority of people.

Try it yourself

Try solving this question here: