LeetCode 296: Best Meeting Point Solution in Python – A Step-by-Step Guide

What Is LeetCode 296: Best Meeting Point?

In LeetCode 296: Best Meeting Point, you’re given a 2D grid where 1s mark people’s locations (e.g., [[1,0,0],[0,1,0],[0,0,1]]), and 0s are empty spots. Your task is to find a meeting point (row, col) that minimizes the total Manhattan distance—the sum of horizontal and vertical steps—for everyone to reach it. Manhattan distance means no diagonals, just straight moves. For example, with points (0,0), (1,0), and (0,1), the spot (0,0) might work, but we need the best one. This problem tests your optimization skills, feeling a bit like LeetCode 286: Walls and Gates but focused on distance sums.

Problem Statement

• Input: A 2D integer array grid with 0s (empty) and 1s (people).
• Output: An integer—the minimum total Manhattan distance to a meeting point.
• Rules: Use Manhattan distance (|x1-x2| + |y1-y2|); meeting point can be anywhere; grid has at least one 1.

Constraints

• Grid size: m x n, where 1 ≤ m, n ≤ 200.
• Values: 0 or 1.
• At least one 1 in the grid.

Examples

• Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
• Output: 6
• Input: grid = [[1,0,1]]
• Output: 1
• Input: grid = [[1]]
• Output: 0

Understanding the Problem: Finding the Shortest Walk

To solve LeetCode 296: Best Meeting Point in Python, we need to pick a spot (r, c) in the grid that makes the total Manhattan distance—sum of |r - r_i| + |c - c_i| for all people at (r_i, c_i)—as small as possible. For [[1,0,1]], people are at (0,0) and (0,2)—where should they meet? A naive way is to try every spot, but that’s slow. Instead, we’ll use:

• Best Solution (Median-Based Manhattan Distance): O(m + n) time, O(m + n) space—fast and smart.
• Alternative Solution (Brute-Force Search): O(m * n * k) time—simple but slow (k = number of people).

Let’s dive into the median solution with a friendly breakdown that’s easy to follow.

Best Solution: Median-Based Manhattan Distance

Why This Is the Best Solution

The median-based approach is the top choice for LeetCode 296 because it’s super efficient—O(m + n) time to find coordinates and O(m + n) space to store them—using a mathematical trick: in a 1D line, the median minimizes total distance, and Manhattan distance lets us split 2D into two 1D problems (rows and columns). It’s like finding the middle ground for a group—quick and perfect for this grid!

How It Works

Let’s imagine this like planning a meetup:

• Step 1: Gather Locations:
• Scan the grid to list all people’s row and column coordinates—like (0,0), (1,0), (2,2).
• Step 2: Split into Rows and Columns:
• Make two lists: rows = [0, 1, 2], cols = [0, 0, 2].
• Manhattan distance = sum of row distances + sum of column distances.
• Step 3: Find the Median:
• Sort both lists: rows = [0, 1, 2], cols = [0, 0, 2].
• For odd count, median is the middle; for even, any point between the two middle values works (we’ll pick one).
• Rows: median = 1 (middle of 0, 1, 2).
• Cols: median = 0 (middle-ish of 0, 0, 2).
• Step 4: Calculate Total Distance:
• Row distance: |0-1| + |1-1| + |2-1| = 1 + 0 + 1 = 2.
• Col distance: |0-0| + |0-0| + |2-0| = 0 + 0 + 2 = 2.
• Total = 2 + 2 = 4.
• Step 5: Why It Works:
• In 1D, the median minimizes total absolute distance (math fact!).
• Manhattan distance separates into row and column sums, so median works for each.

It’s like picking the middle of a tug-of-war—everyone’s walk is shortest!

Step-by-Step Example

Example: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]

• Step 1: Find Points:
• (0,0), (0,4), (2,2).
• Step 2: Split:
• Rows = [0, 0, 2], Cols = [0, 4, 2].
• Step 3: Sort and Median:
• Rows = [0, 0, 2], median = 0 (middle-ish).
• Cols = [0, 2, 4], median = 2 (middle).
• Step 4: Distances:
• Rows: |0-0| + |0-0| + |2-0| = 0 + 0 + 2 = 2.
• Cols: |0-2| + |4-2| + |2-2| = 2 + 2 + 0 = 4.
• Total = 2 + 4 = 6.
• Result: 6.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        # Step 1: Get grid size
        m, n = len(grid), len(grid[0])

        # Step 2: Collect row and column coordinates
        rows, cols = [], []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:  # Found a person
                    rows.append(i)  # Add row
                    cols.append(j)  # Add column

        # Step 3: Sort (rows already sorted due to scan order)
        cols.sort()  # Sort columns

        # Step 4: Find medians (middle index for odd count)
        row_median = rows[len(rows) // 2]  # Middle row
        col_median = cols[len(cols) // 2]  # Middle col

        # Step 5: Calculate total Manhattan distance
        total = 0
        for r in rows:
            total += abs(r - row_median)  # Row distance
        for c in cols:
            total += abs(c - col_median)  # Col distance

        return total

• Line 4: Get grid dimensions (m rows, n cols).
• Line 7-12: Scan grid:
• If grid[i][j] = 1, add i to rows, j to cols.
• Rows are sorted naturally (top-to-bottom scan).
• Line 14: Sort cols (left-to-right isn’t sorted).
• Line 17-18: Get medians:
• Middle index (len // 2) works for odd or even (median property holds).
• Line 20-23: Sum distances:
• Add |r - row_median| for each row.
• Add |c - col_median| for each column.
• Line 25: Return total.

• Time Complexity: O(m*n) to scan, O(k log k) to sort (k = people), total ~O(m*n).
• Space Complexity: O(m + n)—stores coordinates.

This is like a quick meetup planner—middle spot wins!

Alternative Solution: Brute-Force Search

Why an Alternative Approach?

The brute-force search tries every grid spot—O(m * n * k) time, O(k) space (k = people). It’s slow but intuitive, like testing every café in town to see which is closest overall—great for understanding but not practical here.

How It Works

Let’s imagine checking every spot:

• Step 1: List all people’s coordinates.
• Step 2: For each grid cell (i, j), calculate total distance to all people.
• Step 3: Pick the minimum total.

It’s like a trial-and-error hunt for the best spot!

Step-by-Step Example

Example: grid = [[1,0,1]]

• Points: (0,0), (0,2).
• Test (0,0): |0-0| + |0-0| + |0-0| + |2-0| = 0 + 2 = 2.
• Test (0,1): |0-0| + |1-0| + |0-0| + |1-2| = 1 + 1 = 2.
• Test (0,2): |0-0| + |2-0| + |0-0| + |2-2| = 2 + 0 = 2.
• Min: 2 (corrected: actual min is 1 at (0,1), see below).

Code for Brute-Force Approach

Copy codeclass Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        people = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    people.append((i, j))

        min_dist = float('inf')
        for i in range(m):
            for j in range(n):
                dist = 0
                for r, c in people:
                    dist += abs(r - i) + abs(c - j)
                min_dist = min(min_dist, dist)

        return min_dist

• Time Complexity: O(m * n * k)—k people, m*n spots.
• Space Complexity: O(k)—stores people.

It’s a slow sweep but works.

Comparing the Two Solutions

• Median (Best):
• Pros: O(m*n) time, O(m + n) space, fast.
• Cons: Needs median insight.
• Brute-Force (Alternative):
• Pros: O(m * n * k) time, O(k) space, simple.
• Cons: Too slow.

Median wins big.

Additional Examples and Edge Cases

• [[1]]: 0.
• [[0,1]]: 1.
• [[1,0],[0,1]]: 2.

Median’s faster.

Complexity Breakdown

• Median: Time O(m*n), Space O(m + n).
• Brute-Force: Time O(m * n * k), Space O(k).

Median rules.

Key Takeaways

• Median: Middle minimizes—smart!
• Brute-Force: Try all—slow!
• Grids: Math beats loops.
• Python Tip: Lists rock—see [Python Basics](/python/basics).

Final Thoughts: Meet in the Middle

LeetCode 296: Best Meeting Point in Python is a clever grid puzzle. The median solution zips to the answer, while brute-force shows the grind. Want more? Try LeetCode 286: Walls and Gates or LeetCode 317: Shortest Distance from All Buildings. Ready to gather? Head to Solve LeetCode 296 on LeetCode and find that spot today!