package com.fishercoder.solutions;

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

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;
        }
    }
}

@@ -167,16 +167,129 @@
 tion1 %7B%0A
+        /**%0A         * Credit: https://leetcode.com/problems/best-meeting-point/solution/ Approach 3%0A         */%0A
         
@@ -401,17 +401,16 @@
 length;%0A
-%0A
         
@@ -427,17 +427,20 @@
 nteger%3E 
-I
+rows
  = new A
@@ -451,10 +451,11 @@
 List
+%3C%3E
 (
-m
 );%0A 
@@ -479,17 +479,20 @@
 nteger%3E 
-J
+cols
  = new A
@@ -503,14 +503,14 @@
 List
+%3C%3E
 (
-n
 );%0A
-%0A
     
@@ -660,17 +660,20 @@
         
-I
+rows
 .add(i);
@@ -697,17 +697,20 @@
         
-J
+cols
 .add(j);
@@ -756,33 +756,32 @@
 %7D%0A            %7D%0A
-%0A
             retu
@@ -780,300 +780,419 @@
     
-return getMin(I) + getMin(J);%0A        %7D%0A%0A        private int getMin(List%3CInteger%3E list) %7B%0A            int ret = 0;%0A%0A            Collections.sort(list);%0A%0A            int i = 0;%0A            int j = list.size() - 1;%0A            while (i %3C j) %7B%0A                ret += list.get(j--) - list.get(i++
+int rowMedian = rows.get(rows.size() / 2);%0A            Collections.sort(cols);%0A            int colMedian = cols.get(cols.size() / 2);%0A            return minDistance1D(rows, rowMedian) + minDistance1D(cols, colMedian);%0A        %7D%0A%0A        private int minDistance1D(List%3CInteger%3E points, int median) %7B%0A            int distance = 0;%0A            for (int i : points) %7B%0A                distance += Math.abs(i - median
 );%0A 
@@ -1196,33 +1196,32 @@
 ;%0A            %7D%0A
-%0A
             retu
@@ -1223,19 +1223,24 @@
  return 
-ret
+distance
 ;%0A      
@@ -1239,20 +1239,21 @@
 ;%0A        %7D%0A
+%0A
     %7D%0A%7D%0A

refactor 296