296. Best Meeting Point

Best Meeting Point

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.

Solution

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

        int row = grid.length;
        int column = grid[0].length;

        List<Node> houses = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (grid[i][j] == 1) {
                    houses.add(new Node(i, j));
                }
            }
        }

        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                int currentDistance = 0;
                Node currentNode = new Node(i,j);
                for(Node node:houses) {
                    currentDistance += currentNode.distance(node);
                }

                minDistance = Math.min(minDistance, currentDistance);
            }
        }

        return minDistance;
    }

    private class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int distance(Node other) {
            return Math.abs(other.x - x) + Math.abs(other.y - y);
        }
    }
}