Problem

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|.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

Output:
6

Explanation: Visualize the input like grid below. We are given three people living at (0, 0), (0, 4), and (2, 2):

1
2
3
4
5

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0, 2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Solution

Method 1 – Find the Median (1D and 2D Intuition)

Intuition

The optimal meeting point to minimize the total Manhattan distance is at the median of the people’s coordinates. This is because, in 1D, the sum of absolute differences is minimized at the median.

Let’s visualize this in 1D:

1

______A_____P_______B_______

If two people live at A and B, any meeting point P between A and B gives the same total distance: |A-P| + |B-P| = |B-A|. If P is outside [A, B], the total distance increases.

Now, with more people (C, A, B, D):

1

______C_____A_____P_______B______D______

The best meeting point P is between the inner points (A and B), and the total distance is minimized by pairing the outermost points (C with D, A with B, etc.) and summing their distances to the median.

Approach

  1. Collect all row and column indices where people live (grid[i][j] == 1).
  2. Sort the row and column lists.
  3. Find the median row and median column.
  4. Sum the distances from each person’s home to the median row and column.
    • This is equivalent to minimizing the total Manhattan distance in 2D, since the Manhattan distance is separable into x and y components.

In 2D, the same principle applies: the best meeting point is at (median row, median column). The ASCII grid below shows the example:

1
2
3
4
5

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The best meeting point is at (0, 2), the median of the x and y coordinates, with a minimal total distance of 6.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> rows, cols;
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) rows.push_back(i);
        for (int j = 0; j < n; ++j)
            for (int i = 0; i < m; ++i)
                if (grid[i][j] == 1) cols.push_back(j);
        int rowMedian = rows[rows.size() / 2];
        int colMedian = cols[cols.size() / 2];
        int sum = 0;
        for (int r : rows) sum += abs(r - rowMedian);
        for (int c : cols) sum += abs(c - colMedian);
        return sum;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import "sort"
func minTotalDistance(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    rows, cols := []int{}, []int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                rows = append(rows, i)
            }
        }
    }
    for j := 0; j < n; j++ {
        for i := 0; i < m; i++ {
            if grid[i][j] == 1 {
                cols = append(cols, j)
            }
        }
    }
    rowMedian := rows[len(rows)/2]
    colMedian := cols[len(cols)/2]
    sum := 0
    for _, r := range rows {
        sum += abs(r - rowMedian)
    }
    for _, c := range cols {
        sum += abs(c - colMedian)
    }
    return sum
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minTotalDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) rows.add(i);
        for (int j = 0; j < n; j++)
            for (int i = 0; i < m; i++)
                if (grid[i][j] == 1) cols.add(j);
        int rowMedian = rows.get(rows.size() / 2);
        int colMedian = cols.get(cols.size() / 2);
        int sum = 0;
        for (int r : rows) sum += Math.abs(r - rowMedian);
        for (int c : cols) sum += Math.abs(c - colMedian);
        return sum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun minTotalDistance(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val rows = mutableListOf<Int>()
        val cols = mutableListOf<Int>()
        for (i in 0 until m)
            for (j in 0 until n)
                if (grid[i][j] == 1) rows.add(i)
        for (j in 0 until n)
            for (i in 0 until m)
                if (grid[i][j] == 1) cols.add(j)
        val rowMedian = rows[rows.size / 2]
        val colMedian = cols[cols.size / 2]
        var sum = 0
        for (r in rows) sum += kotlin.math.abs(r - rowMedian)
        for (c in cols) sum += kotlin.math.abs(c - colMedian)
        return sum
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        rows, cols = [], []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    rows.append(i)
        for j in range(n):
            for i in range(m):
                if grid[i][j] == 1:
                    cols.append(j)
        row_median = rows[len(rows)//2]
        col_median = cols[len(cols)//2]
        return sum(abs(r - row_median) for r in rows) + sum(abs(c - col_median) for c in cols)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn min_total_distance(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut rows = Vec::new();
        let mut cols = Vec::new();
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 1 {
                    rows.push(i as i32);
                }
            }
        }
        for j in 0..n {
            for i in 0..m {
                if grid[i][j] == 1 {
                    cols.push(j as i32);
                }
            }
        }
        let row_median = rows[rows.len() / 2];
        let col_median = cols[cols.len() / 2];
        rows.iter().map(|&r| (r - row_median).abs()).sum::<i32>() +
        cols.iter().map(|&c| (c - col_median).abs()).sum::<i32>()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minTotalDistance(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        const rows: number[] = [];
        const cols: number[] = [];
        for (let i = 0; i < m; i++)
            for (let j = 0; j < n; j++)
                if (grid[i][j] === 1) rows.push(i);
        for (let j = 0; j < n; j++)
            for (let i = 0; i < m; i++)
                if (grid[i][j] === 1) cols.push(j);
        const rowMedian = rows[Math.floor(rows.length / 2)];
        const colMedian = cols[Math.floor(cols.length / 2)];
        let sum = 0;
        for (const r of rows) sum += Math.abs(r - rowMedian);
        for (const c of cols) sum += Math.abs(c - colMedian);
        return sum;
    }
}

Complexity

  • ⏰ Time complexity: O(mn + k log k), where m and n are the grid dimensions and k is the number of people (1s in the grid). Collecting coordinates is O(mn), and sorting is O(k log k).
  • 🧺 Space complexity: O(k), for storing the row and column indices.