⚡Flashcard Drill➔
NeetCode #943LC-296HardMath & Geometry
← Back to All Problems

#943 · #296 · Best Meeting Point(最佳的碰头地点)

📌 Problem Statement & Constraints

Given an m x n binary grid, find a meeting point at any integer coordinate that minimises the total Manhattan distance to every cell containing a 1, and return that minimum total distance. Constraints: 1 <= m, n <= 200.

💡 Core Algorithmic Approaches

  1. Manhattan distance separates into independent x and y problems: sum |xi - X| + sum |yi - Y|.
  2. For one dimension, the point minimising sum |xi - X| is the median of the coordinates.
  3. So take the median of the x-coordinates and the median of the y-coordinates separately, then sum the absolute deviations.
  4. The median result also shows why the answer does not depend on obstacles — there are none in this problem.

💻 Benchmark Python3 Implementation

class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        xs = [i for i in range(m) for j in range(n) if grid[i][j]]
        ys = [j for i in range(m) for j in range(n) if grid[i][j]]
        xs.sort()
        ys.sort()
        mx = xs[len(xs) // 2]        # median x
        my = ys[len(ys) // 2]        # median y
        return sum(abs(x - mx) for x in xs) + sum(abs(y - my) for y in ys)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n + k log k): collecting the coordinates plus sorting them (k is the number of ones).
💾 Space Complexity
O(k): the coordinate lists.

⚠️ Interview Pitfalls & Follow-ups

  • Using the centroid or mean: the sum of Manhattan distances is minimised by the median, not the mean.
  • Running a 2-D search or BFS: that turns an O(k log k) problem into something far worse.
  • Insisting the meeting point be on a 1: the median point may lie on a 0, but the total distance is unchanged.
  • Mixing up the coordinate sources: xs comes from row indices i and ys from column indices j.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems