LeetCode: Best Meeting Point

Posted on August 5, 2019July 26, 2020 by braindenny

Best Meeting Point

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

## https://code.dennyzhang.com/best-meeting-point
## Basic Ideas: getmedian
##
##  Manhattan distance = x distance + y distance
##  Decrease one 2D problem into two 1D problems
##
## Complexity: Time O(n*m*log(n*m)), Space O(n*m)
class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        rows, cols = [], []
        n, m = len(grid), len(grid[0])
        points = []
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    rows.append(i)
                    cols.append(j)
                    points.append((i, j))
        rowMedian = rows[int(len(rows)/2)]
        cols.sort()
        colMedian = cols[int(len(cols)/2)]

        res = 0
        for (i, j) in points:
            res += abs(rowMedian-i) + abs(colMedian-j)
        return res

Post Views: 0