Best Meeting Point

This page explains Java solution to problem Best Meeting Point using Array data structure.

Problem Statement

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

Input:
[
        1 0 0 0 1
        0 0 0 0 0
        0 0 1 0 0
]
Output: 6
Explanation:
Given three people living at (0,0), (0,4), and (2,2):
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

package com.vc.hard;

class BestMeetingPoint {
    public int minTotalDistance(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[] row = new int[n];
        int[] col = new int[m];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1) {
                    row[i] += 1;
                    col[j] += 1;
                }
            }
        }

        int minDistanceRow = minDistance(row);
        int minDistanceCol = minDistance(col);

        return minDistanceRow + minDistanceCol;
    }

    private int minDistance(int[] r) {
        int i = -1;
        int j = r.length;
        int left = 0;
        int right = 0;

        int d = 0;
        while(i < j) {
            if(left < right) {
                d += left;
                left += r[++i];
            }
            else {
                d += right;
                right += r[--j];
            }
        }
        return d;
    }
}

Time Complexity

O(M * N) Where
M is total number of rows in an input array
N is total number of cols in an input array

Space Complexity

O(M + N) Where
M is total number of rows in an input array
N is total number of cols in an input array