package com.fishercoder.solutions;

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

/**
 * 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 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,16 +115,46 @@
 t;%0A%0A/**%0A
+ * 296: Best Meeting Point%0A *%0A
  * A gro
@@ -231,16 +231,19 @@
 istance.
+%0A *
  You are
@@ -329,16 +329,19 @@
 e group.
+%0A *
  The dis
@@ -740,16 +740,50 @@
  _296 %7B%0A
+%09public static class Solution1 %7B%0A%09
 %09public 
@@ -817,24 +817,25 @@
 %5D grid) %7B%0A%09%09
+%09
 int m = grid
@@ -843,16 +843,17 @@
 length;%0A
+%09
 %09%09int n 
@@ -871,16 +871,17 @@
 ength;%0A%0A
+%09
 %09%09List%3CI
@@ -912,16 +912,17 @@
 t(m);%0A%09%09
+%09
 List%3CInt
@@ -952,16 +952,17 @@
 (n);%0A%0A%09%09
+%09
 for (int
@@ -983,16 +983,17 @@
  i++) %7B%0A
+%09
 %09%09%09for (
@@ -1021,16 +1021,17 @@
 ) %7B%0A%09%09%09%09
+%09
 if (grid
@@ -1050,16 +1050,17 @@
  %7B%0A%09%09%09%09%09
+%09
 I.add(i)
@@ -1061,16 +1061,17 @@
 add(i);%0A
+%09
 %09%09%09%09%09J.a
@@ -1085,20 +1085,24 @@
 %09%09%09%09
+%09
 %7D%0A
+%09
 %09%09%09%7D%0A%09%09
+%09
 %7D%0A%0A
+%09
 %09%09re
@@ -1129,20 +1129,22 @@
 Min(J);%0A
+%09
 %09%7D%0A%0A
+%09
 %09private
@@ -1179,16 +1179,17 @@
 st) %7B%0A%09%09
+%09
 int ret 
@@ -1194,16 +1194,17 @@
 t = 0;%0A%0A
+%09
 %09%09Collec
@@ -1222,16 +1222,17 @@
 list);%0A%0A
+%09
 %09%09int i 
@@ -1238,16 +1238,17 @@
  = 0;%0A%09%09
+%09
 int j = 
@@ -1266,16 +1266,17 @@
  - 1;%0A%09%09
+%09
 while (i
@@ -1283,16 +1283,17 @@
  %3C j) %7B%0A
+%09
 %09%09%09ret +
@@ -1327,19 +1327,21 @@
 i++);%0A%09%09
+%09
 %7D%0A%0A
+%09
 %09%09return
@@ -1346,13 +1346,17 @@
 rn ret;%0A
+%09%09%7D%0A
 %09%7D%0A%7D%0A

refactor 296