LeetCode link

Intuition

  • Actually there’s no relation with algorithm, it’s more like some common-sense.The best point is just the middle of the locations in horizon and vertical.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minTotalDistance(int[][] grid) {
        ArrayList<Integer> rows = new ArrayList<>();
        ArrayList<Integer> cols = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        Collections.sort(rows);
        Collections.sort(cols);
        int rowMid = rows.get(rows.size() / 2);
        int colsMid = cols.get(cols.size() / 2);
        int result = 0;
        for (int i = 0; i < rows.size(); i++) {
            result += (Math.abs(rows.get(i) - rowMid) + Math.abs(cols.get(i) - colsMid));
        }
        return result;
    }
}