Best Meeting Point


One potential optimization for Solution #3: since we only care about the median value, we could use "find kth smallest element" to find the median of column in O(N).
C++ STL has nth_element which rearranges the elements in the range in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. So the time complexity of Solution #3 would be O(mn) I think.
AC C++ code in the pic attached.

@jonsnow1984 Because when you append elements in
rows
, it is already sorted. In other words, you are inserting the row index of every element. For example, you always insert 0's, then insert 1's inrows
.

O(mn) time O(m+n) space:
class Solution { public int minTotalDistance(int[][] grid) { if (grid == null  grid.length == 0) { return 0; } int m = grid.length; int n = grid[0].length; if (n == 0) { return 0; } int k = 0; int[] x = new int[m]; int[] y = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { x[i]++; y[j]++; k++; } } } int m_x = getMedium(x, k/2); int m_y = getMedium(y, k/2); return getDist(x, m_x) + getDist(y, m_y); } private int getMedium(int[] nums, int m) { int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (sum > m) { return i; } } return 0; } private int getDist(int[] nums, int m) { int dist = 0; for (int i = 0; i < nums.length; i++) { dist += nums[i] * Math.abs(i  m); } return dist; } }

O(mn) time O(1) space:
class Solution { public int minTotalDistance(int[][] grid) { if (grid == null  grid.length == 0) { return 0; } int m = grid.length; int n = grid[0].length; if (n == 0) { return 0; } int k = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { k++; } } } int count = 0; int m_x = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { count++; } if (count > k / 2) { m_x = i; break; } } if (m_x != 1) { break; } } count = 0; int m_y = 1; for (int j = 0; j < n; j++) { for (int i = 0; i < m; i++) { if (grid[i][j] == 1) { count++; } if (count > k / 2) { m_y = j; break; } } if (m_y != 1) { break; } } int dist = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { dist += Math.abs(i  m_x) + Math.abs(j  m_y); } } } return dist; } }