296.Best Meeting Point

Tags: [math], [median], [trick]

Com: {t}

Hard: [###]

Link: https://leetcode.com/problems/best-meeting-point/\#/description

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

For example, given three people living at(0,0),(0,4), and(2,2):

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.

Better Solution: Median

public class Solution {
    public int minTotalDistance(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        if (rows == 0 || cols == 0) {
            return 0;
        }

        List<Integer> rowCollection = new ArrayList<>();
        for (int r = 0; r < rows; r ++) {
            for (int c = 0; c < cols; c ++) {
                if (grid[r][c] == 1) {
                    rowCollection.add(r);
                }
            }
        }

        List<Integer> colCollection = new ArrayList<>();
        for (int c = 0; c < cols; c ++) {
            for (int r = 0; r < rows; r ++) {
                if (grid[r][c] == 1) {
                    colCollection.add(c);
                }
            }
        }

        int rMedian = getMedian(rowCollection);
        int cMedian = getMedian(colCollection);

        int distance = 0;
        for (int r = 0; r < rows; r ++) {
            for (int c = 0; c < cols; c ++) {
                if (grid[r][c] == 1) {
                    distance += getDistance(rMedian, cMedian, r, c);
                }
            }
        }
        return distance;
    }

    private int getMedian(List<Integer> nums) {
        int size = nums.size();
        return (nums.get((size - 1) / 2) + nums.get((size / 2))) / 2;
    }

    private int getDistance(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }
}

Revelation:

• Knowledge: If in the 1-D, 2-D or 3-D or hight level dimension, we want to find one point has the smallest distance to other points, we can calculate the median.
• If we have an array, start(index), and end(index), the left middle index is (end - start) / 2, the right middle index is (end - start + 1) / 2.

Note:

• Time complexity = O(rows * cols), rows is the number of rows of the given grid, cols is the number of cols of the given grid.

Naive Solution:

public class Solution {
    public int minTotalDistance(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        if (rows == 0 || cols == 0) {
            return 0;
        }

        int[][] distanceGrid = new int[rows][cols];
        for (int r = 0; r < rows; r ++) {
            for (int c = 0; c < cols; c ++) {
                if (grid[r][c] != 1) {
                    continue;
                }

                calculateDistance(grid, rows, cols, r, c, distanceGrid);
            }
        }

        int minDistance = Integer.MAX_VALUE;
        for (int r = 0; r < rows; r ++) {
            for (int c = 0; c < cols; c ++) {
                if (distanceGrid[r][c] < minDistance) {
                    minDistance = distanceGrid[r][c];
                }
            }
        }
        return minDistance;
    }

    private void calculateDistance(int[][] grid, int rows, int cols, int row, int col, int[][] distanceGrid) {
        for (int r = 0; r < rows; r ++) {
            for (int c = 0; c < cols; c ++) {
                distanceGrid[r][c] += getDistance(row, col, r, c);
            }
        }
    }

    private int getDistance(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }
}

Revelation:

• This problem looks like a graph problem, and looks like we should use BFS, but this problem is not, because there is no obstacles, and we can cross other home to achieve the goal, and it is not necessary have the meeting in the '0's, we can have meeting at someone's home.

Note:

• Time complexity = O((rows * cols) ^ 2).