< Previous
Next >
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
.
Example:
Input:
1 - 0 - 0 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
Output: 6
Explanation: Given three people living at (0,0)
, (0,4)
, and (2,2)
:
The point (0,2)
is an ideal meeting point, as the total travel distance
of 2+2+2=6 is minimal. So return 6.
[Sort]
[Math]
Similar Questions
- Shortest Distance from All Buildings (Hard)
- Minimum Moves to Equal Array Elements II (Medium)
Hints
Hint 1
Try to solve it in one dimension first. How can this solution apply to the two dimension case?