Best Meeting Point

Source

• leetcode: 296

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.

Hint:
Try to solve it in one dimension first. How can this solution apply to the two
dimension case?

Java

public int minTotalDistance(int[][] grid) {
    List<Integer> I = new ArrayList<Integer>();
    List<Integer> J = new ArrayList<Integer>();

    for(int i=0; i<grid.legnth; i++){
        for(int j=0; j<grid[0].length; j++){
            if(grid[i][j]==1){
                I.add(i);
                j.add(j);
            }
        }
    }
    return getMin(I)+getMin(J);
}

public int getMin(List<Integer> list){
    int result=0;

    Collections.sort(list);

    int i=0;
    int j=list.size()-1;
    while(i<j){
        result += list.get(j--)-list.get(i++);
    }
    return result;
}