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;
}
14ms java solution


I noticed that. However that is going to introduce an extra logic into minTotalDistance. People might wonder why I just sort J not I or both. Although it is not hard to figure out, I still want to keep the logic of minTotalDistance as simple as possible, even sacrificing a little bit of performance. Another minor reason, it is just my personal preference. If you just sort J but do not sort I , it will be making the code not symmetrically neat. I would rather trade a little bit of performance for symmetric neatness.

Thanks for your great solution. We can reduce run time from
O(mnlogmn)
toO(mn)
by removing sorting. Here is my 6ms solution:
public int minTotalDistance(int[][] grid) { int m = grid.length, n = grid[0].length; List<Integer> I = new ArrayList<Integer>(); List<Integer> J = new ArrayList<Integer>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { I.add(i); } } } for (int j = 0; j < n; j++) { for (int i = 0; i < m; i ++) { if (grid[i][j] == 1) { J.add(j); } } } return minTotalDistance(I) + minTotalDistance(J); } public int minTotalDistance(List<Integer> grid) { int i = 0, j = grid.size()  1, sum = 0; while (i < j) { sum += grid.get(j)  grid.get(i++); } return sum; }

Firstly, I do not think coming from O(nlogn + mlogm) to O(mn) is always an optimization. It really depends on test cases. Try to compare the test case where m = n = 10 and the case where m = 1000 and n =1, you will understand what I am saying. If your code is tested with the test case where m = n, its performance will not be as good as the solution with sorting in theory. So the optimization you meant is really conditional. It could be performance degradation under some certain circumstances. Secondly,O(nlogn + mlogm) is the time complexity for the worstcase scenario where all elements in grid are '1' , i.e, generally speaking, the performance of sorting is better than O(nlogn + mlogm). However O(mn) is guaranteed time complexity for your solution since you need to traverse the whole grid for the second time to gather J. So even if you want to compare the performance of those 2 solutions you need to reason your logic.

Thanks for your detailed analysis. I've edited my answer. I think the time complexity for your algorithm is actually
O(mnlogmn)
, because you have to traverse the m * n elements and sort them. I think the length of your array I & J should bem * n
. Let's compare:
T(yours) = 1 traverse + 2 sorts + 2 traverses = 3mn + 2mn log(mn)

T(mine) = 2 traverses + 2 traverses = 4mn

T(yours)  T(mine) = 2mn log(mn)  mn = mn [2 log(mn)  1]
For any m >= 1 and n >= 1, I guess time complexity for your algorithm is not optimized enough. The bottleneck is sorting.


@yavinci, sorry, my bad, I read some wrong, you wrote O(mnlogm), I thought it was (mlogm + nlogn), back then I was in the middle of another question which is very similar to this one. Yeah, you are right, in worstcase scenario, traversing the whole grid again to gather J will outperform the solution with sorting. However. I still think it is really depends on test cases. To me, It is not convincing to compare the worstcase scenario of one solution with the general case of another. One extreme example is what if all elements in the grid are '0'.

No problem. I understand your concern. You know generally sorting takes
O(nlogn)
(besides bucket sort). Starting fromcount = 0
(grid all '0'), tocount = mn
(grid all '1'), sorting is doing from nearly the same to worse and worse. Let's takecount = 100
,O(mn)
is nearly 4~6 times faster thanO(mnlogmn)
.

@yanggao As long as you have different numbers of people on your left and on your right, moving a little to the side with more people decreases the sum of distances. So to minimize it, you must have equally many people on your left and on your right.

@yanggao said in 14ms java solution:
I am not very clear about why the opt point should be median. Can someone give some proof, mathematically, that shows that median is the optimal solution given both oddlength array and evenlength array
Same thought process as in  https://leetcode.com/problems/minimummovestoequalarrayelementsii/
Go to the median.