Best Meeting Point Python Solution with Tests

Tested Python solution for LeetCode 296 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 296, Hard. Topics: Array, Math, Matrix, Sorting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 296   # by problem number
lcpy gen -s best_meeting_point   # by problem name

​

Problem

Given an m x n binary grid where each 1 marks the home of one friend, return the minimal total travel distance.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

​

Examples

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 6
Explanation: Given three friends 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.

Input: grid = [[1,1]]
Output: 1

​

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[i][j] is either 0 or 1.
• There will be at least two friends in the grid.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m*n + f log f) where f is the friend count
    # Space: O(f)
    def min_total_distance(self, grid: list[list[int]]) -> int:
        rows: list[int] = []
        cols: list[int] = []
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    rows.append(r)
                    cols.append(c)
        cols.sort()
        median_row = rows[len(rows) // 2]
        median_col = cols[len(cols) // 2]
        return sum(abs(r - median_row) for r in rows) + sum(abs(c - median_col) for c in cols)

​

Complexity

Time	Space
O(m*n + f log f) where f is the friend count	O(f)

​

Tags

NeetCode All.