Question

Formatted question description: https://leetcode.ca/all/296.html

Given an m x n binary grid 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|.

Example 1:

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.

Example 2:

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.

Algorithm

First look at the situation where there are two points A and B in one dimension.

______A_____P_______B_______

It can be found that as long as the meeting is that the location P is in the interval [A, B], no matter where it is, the sum of the distances is the distance between A and B. If P is not between [A, B], then the sum of the distances is Will be greater than the distance between A and B, now add two more points C and D:

______C_____A_____P_______B______D______

The best position of point P is in the interval [A, B], so that the sum of the distances from the four points is the AB distance plus the CD distance.

Just sort the positions, then subtract the first coordinate from the last coordinate, which is the CD distance, and subtract the second coordinate from the penultimate, the second coordinate, which is the AB distance. And so on, until the middle stop.

The one-dimensional situation is analyzed, and the two-dimensional situation is the addition of two one-dimensional results.

Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Best_Meeting_Point {

    public static void main(String[] args) {
        Best_Meeting_Point out = new Best_Meeting_Point();
        Solution s = out.new Solution();

        System.out.println(s.minTotalDistance(new int[][] { {1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0} }));
    }

    public class Solution {
        public int minTotalDistance(int[][] grid) {

            // empty, null check

            List<Integer> ipos = new ArrayList<>();
            List<Integer> jpos = new ArrayList<>();

            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        ipos.add(i);
                        jpos.add(j);
                    }
                }
            }

            int sum = 0;

            // ipos already sorted, since above it's iterating over grid via i index
            int iMid = ipos.get(ipos.size() / 2);
            for(Integer pos : ipos){
                sum += Math.abs(pos - iMid);
            }

            Collections.sort(jpos);
            int jMid = jpos.size() / 2;
            for (int j = 0; j < jpos.size(); j++) {
                sum += Math.abs(jpos.get(jMid) - jpos.get(j));
            }

            return sum;
        }
    }
}

############

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);
                    cols.add(j);
                }
            }
        }
        Collections.sort(cols);
        int i = rows.get(rows.size() >> 1);
        int j = cols.get(cols.size() >> 1);
        return f(rows, i) + f(cols, j);
    }

    private int f(List<Integer> arr, int x) {
        int s = 0;
        for (int v : arr) {
            s += Math.abs(v - x);
        }
        return s;
    }
}

// OJ: https://leetcode.com/problems/best-meeting-point/
// Time: O(MN^2)
// Space: O(MN)
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), ans = INT_MAX, dist[201][201] = {}, up[201][201] = {}, down[201][201] = {}, cnt[201] = {};
        for (int i = 0; i < M; ++i) {
            int sum = 0, left = 0, right = 0;
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                sum += j;
                right++;
            }
            for (int j = 0; j < N; ++j) {
                dist[i][j] = sum;
                if (A[i][j]) ++left, --right;
                sum += left - right;
            }
            cnt[i] = left;
        }
        int c = cnt[0];
        for (int i = 1; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                int mn = INT_MAX;
                for (int k = 0; k < N; ++k) {
                    mn = min(mn, dist[i - 1][k] + (abs(j - k) + 1) * c);
                }
                up[i][j] = up[i - 1][j] + mn;
            }
            c += cnt[i];
        }
        c = cnt[M - 1];
        for (int i = M - 2; i >= 0; --i) {
            for (int j = 0; j < N; ++j) {
                int mn = INT_MAX;
                for (int k = 0; k < N; ++k) {
                    mn = min(mn, dist[i + 1][k] + (abs(j - k) + 1) * c);
                }
                down[i][j] = down[i + 1][j] + mn;
            }
            c += cnt[i];
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                ans = min(ans, dist[i][j] + up[i][j] + down[i][j]);
            }
        }
        return ans;
    }
};

'''
>>> sum(a for a in range(6))
15
>>> sum([a for a in range(6)])
15
'''
class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        def f(arr, x):
            return sum(abs(v - x) for v in arr)

        rows, cols = [], []
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v:
                    rows.append(i)
                    cols.append(j)
        cols.sort()
        row_mid_val = rows[len(rows) >> 1]
        col_mid_val = cols[len(cols) >> 1]
        return f(rows, row_mid_val) + f(cols, col_mid_val)

############

class Solution(object):
  def minTotalDistance(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    iList, jList, ppl = [], [], []
    for i in range(0, len(grid)):
      for j in range(0, len(grid[0])):
        if grid[i][j] == 1:
          ppl.append((i, j))
          iList.append(i)
          jList.append(j)
    jList.sort()
    m = (iList[len(iList) / 2], jList[len(jList) / 2])
    return sum(map(lambda p: abs(p[1] - m[1]) + abs(p[0] - m[0]), ppl))

func minTotalDistance(grid [][]int) int {
	rows, cols := []int{}, []int{}
	for i, row := range grid {
		for j, v := range row {
			if v == 1 {
				rows = append(rows, i)
				cols = append(cols, j)
			}
		}
	}
	sort.Ints(cols)
	i := rows[len(rows)>>1]
	j := cols[len(cols)>>1]
	f := func(arr []int, x int) int {
		s := 0
		for _, v := range arr {
			s += abs(v - x)
		}
		return s
	}
	return f(rows, i) + f(cols, j)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

296 - Best Meeting Point

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions