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

Example 1:

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

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class BestMeetingPoint {
public int minTotalDistance(int[][] grid) {
int n = grid.length;
int m = grid.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