296. Best Meeting Point

[TODO] bucket sort 其实可以优化成O(mn) 譬如直接用y的顺序add y values / bucket sort(extra space) 但是代码没有这样的简洁 有空可写
Version #1 Sorting the points

一刷
另外一个简化

// hi - mid +  mid - lo = hi - lo

感觉不这么写也可以，就是效率稍微低一点

关于为什么median是best meeting point 的证明
For two points, any position between those two points is OK. Since the sum of their path is always the distance between those two.
For 3 points, the sum distance for the two edge points are always the same. However the meeting point's position will influence the middle point's journey. So the best point is the middle point.

For even number of points, any position between the two middle point is fine.
For odd number of points, the median point is the best position.

So we can always use the number at List.size() / 2, as the meeting point.

28.01 %
class Solution {
    public int minTotalDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return -1;
        int rows = grid.length;
        int cols = grid[0].length;
        List<Integer> xSet = new ArrayList<>();
        List<Integer> ySet = new ArrayList<>();
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (grid[x][y] == 1) {
                    xSet.add(x);
                    ySet.add(y);
                }
            }
        }
     
        int xMedian = xSet.get(xSet.size() / 2);
        Collections.sort(ySet);
        int yMedian = ySet.get(ySet.size() / 2);
        return sumUp(xSet, xMedian) + sumUp(ySet, yMedian);  
    }
    private int sumUp(List<Integer> set, int median) {
        int sum = 0;
        for (Integer n : set) {
            sum += Math.abs(n - median);
        }
        return sum;
    }
}
二刷
用了优化的方法，assume there's a median point but do not actually calculate it
After we sort the list, we know that the 1st half of points are less than the median point and the 2nd half of points are larger than the median point
Use the property that, for every pair of points in the list, diff = mid - start + end - mid = end - start
55.49 %

class Solution {
    public int minTotalDistance(int[][] grid) {
     
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
        // Find the median of all x positions / all y positions
        int rows = grid.length;
        int cols = grid[0].length;
        List<Integer> xValues = new ArrayList<>();
        List<Integer> yValues = new ArrayList<>();
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (grid[x][y] == 1) {
                    xValues.add(x);
                    yValues.add(y);
                }
            }
        }
        //xValues is already sorted
        Collections.sort(yValues);
        return countDiff(xValues) + countDiff(yValues);
     
    }
    private int countDiff(List<Integer> list) {
        int sum = 0;
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            sum += list.get(end--) - list.get(start++);
        }
        return sum;
    }
}

Version #2 no sorting

分两次扫描全图，第一次outer loop是x++，这样保证x是按顺序递增的

第二次outer loop是y++，保证y是按顺序递增的

就可以避免sorting

可以将time complexity从O(mnlog(mn)) 优化到O(mn)

看了discussion发现另外一个优化是用int array instead of array list, use two pointers instead of calculation of size / 2. 可以使运算速度变快

三刷

Runtime: 3 ms, faster than 71.47% of Java online submissions for Best Meeting Point.

Memory Usage: 38.4 MB, less than 85.05% of Java online submissions for Best Meeting Point.

class Solution {

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

        List<Integer> xs = new ArrayList<>();

        List<Integer> ys = new ArrayList<>();

        for (int i = 0; i < grid.length; i++) {

            for (int j = 0; j < grid[0].length; j++) {

                if (grid[i][j] == 1) {

                    // add the x value

                    xs.add(i);

                }

            }

        }

        for (int j = 0; j < grid[0].length; j++) {

            for (int i = 0; i < grid.length; i++) {

                if (grid[i][j] == 1) {

                    // add the y value

                    ys.add(j);

                }

            }

        }

        int dist = 0;

        // 0, 1 size = 2

        // i = 0

        for (int i = 0; i < xs.size() / 2; i++) {

            dist += xs.get(xs.size() - 1 - i) - xs.get(i);

        }

        for (int j = 0; j < ys.size() / 2; j++) {

            dist += ys.get(ys.size() - 1 - j) - ys.get(j);

        }

        return dist;

    }

}