LeetCode [296] Best Meeting Point

 296. Best Meeting Point

Hard

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:

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

class Solution { public boolean canTransform(String start, String end) { if (!start.replace("X", "").equals(end.replace("X", ""))) return false; int p1 = 0; int p2 = 0; while(p1 < start.length() && p2 < end.length()){ // get the non-X positions of 2 strings while(p1 < start.length() && start.charAt(p1) == 'X'){ p1++; } while(p2 < end.length() && end.charAt(p2) == 'X'){ p2++; } //if both of the pointers reach the end the strings are transformable if(p1 == start.length() && p2 == end.length()){ return true; } // if only one of the pointer reach the end they are not transformable if(p1 == start.length() || p2 == end.length()){ return false; } if(start.charAt(p1) != end.charAt(p2)){ return false; } // if the character is 'L', it can only be moved to the left. p1 should be greater or equal to p2. if(start.charAt(p1) == 'L' && p2 > p1){ return false; } // if the character is 'R', it can only be moved to the right. p2 should be greater or equal to p1. if(start.charAt(p1) == 'R' && p1 > p2){ return false; } p1++; p2++; } return true; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public int minTotalDistance(int[][] grid) { List<Integer> iList = new ArrayList<>(); List<Integer> jList = new ArrayList<>(); for(int i=0; i<grid.length; ++i){ for(int j=0; j<grid[0].length; ++j){ if(grid[i][j]==1){ iList.add(i); jList.add(j); } } } return getMin(iList) + getMin(jList); } int getMin(List<Integer> list){ Collections.sort(list); int n = list.size(), i = 0, j = n-1, r = 0; while(i<j){ r += (list.get(j--))-list.get(i++); } return r; } }