package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 296: 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.
 */
public class _296 {
	public static class Solution1 {
		public int minTotalDistance(int[][] grid) {
			int m = grid.length;
			int n = grid[0].length;

			List<Integer> I = new ArrayList(m);
			List<Integer> J = new ArrayList(n);

			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (grid[i][j] == 1) {
						I.add(i);
						J.add(j);
					}
				}
			}

			return getMin(I) + getMin(J);
		}

		private int getMin(List<Integer> list) {
			int ret = 0;

			Collections.sort(list);

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

			return ret;
		}
	}
}

@@ -115,638 +115,32 @@
 t;%0A%0A
-/**%0A * 296: Best Meeting Point%0A *%0A * A group of two or more people wants to meet and minimize the total travel distance.%0A * You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group.%0A * The distance is calculated using Manhattan Distance, where distance(p1, p2) = %7Cp2.x - p1.x%7C + %7Cp2.y - p1.y%7C.%0A%0A For example, given three people living at (0,0), (0,4), and (2,2):%0A%0A 1 - 0 - 0 - 0 - 1%0A %7C   %7C   %7C   %7C   %7C%0A 0 - 0 - 0 - 0 - 0%0A %7C   %7C   %7C   %7C   %7C%0A 0 - 0 - 1 - 0 - 0%0A The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.%0A */%0Apublic class _296 %7B%0A%09
+public class _296 %7B%0A    
 publ
@@ -167,18 +167,24 @@
 tion1 %7B%0A
-%09%09
+        
 public i
@@ -215,27 +215,36 @@
 %5D%5B%5D grid) %7B%0A
-%09%09%09
+            
 int m = grid
@@ -252,19 +252,28 @@
 length;%0A
-%09%09%09
+            
 int n = 
@@ -289,19 +289,28 @@
 ength;%0A%0A
-%09%09%09
+            
 List%3CInt
@@ -337,19 +337,28 @@
 ist(m);%0A
-%09%09%09
+            
 List%3CInt
@@ -386,19 +386,28 @@
 st(n);%0A%0A
-%09%09%09
+            
 for (int
@@ -428,20 +428,32 @@
  i++) %7B%0A
-%09%09%09%09
+                
 for (int
@@ -474,21 +474,36 @@
  j++) %7B%0A
-%09%09%09%09%09
+                    
 if (grid
@@ -521,62 +521,143 @@
 ) %7B%0A
-%09%09%09%09%09%09I.add(i);%0A%09%09%09%09%09%09J.add(j);%0A%09%09%09%09%09%7D%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%0A%09%09%09
+                        I.add(i);%0A                        J.add(j);%0A                    %7D%0A                %7D%0A            %7D%0A%0A            
 retu
@@ -682,23 +682,35 @@
 Min(J);%0A
-%09%09%7D%0A%0A%09%09
+        %7D%0A%0A        
 private 
@@ -742,19 +742,28 @@
 list) %7B%0A
-%09%09%09
+            
 int ret 
@@ -768,19 +768,28 @@
 t = 0;%0A%0A
-%09%09%09
+            
 Collecti
@@ -809,25 +809,43 @@
 );%0A%0A
-%09%09%09int i = 0;%0A%09%09%09
+            int i = 0;%0A            
 int 
@@ -865,19 +865,28 @@
 () - 1;%0A
-%09%09%09
+            
 while (i
@@ -897,12 +897,24 @@
 ) %7B%0A
-%09%09%09%09
+                
 ret 
@@ -951,34 +951,61 @@
 +);%0A
-%09%09%09%7D%0A%0A%09%09%09return ret;%0A%09%09%7D%0A%09
+            %7D%0A%0A            return ret;%0A        %7D%0A    
 %7D%0A%7D%0A

refactor 296