14ms java solution


  • 85
    L
    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;
    }

  • 0

    Actually I like your solution better than mine, yours is much easier to read :)


  • 8

    You could sort J outside of getMin instead, as I doesn't need to be sorted.


  • 3
    L

    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.


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 0

    Ok, good points. Neat way to sum the distances, btw, I didn't know that before and I used it in some of my solutions now.


  • 49

    Thanks for your great solution. We can reduce run time from O(mnlogmn) to O(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;
    }

  • 0
    L

    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 worst-case 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.


  • 5

    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 be m * n. Let's compare:

    1. T(yours) = 1 traverse + 2 sorts + 2 traverses = 3mn + 2mn log(mn)

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

    3. 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.


  • 0
    L
    This post is deleted!

  • 0
    S

    If all elements in the grid are 1's, then both I and J would be arrays of length MN; sorting the arrays takes O(MNlogMN) time, so the original algorithm takes indeed O(MNlogMN) time. Reducing it to O(MN) looks like a very legit optimization to me.


  • 0
    L

    @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 worst-case 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 worst-case scenario of one solution with the general case of another. One extreme example is what if all elements in the grid are '0'.


  • 0

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


  • 0
    Z

    Very impressive solution.


  • 0
    L
    This post is deleted!

  • 1
    Y

    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 odd-length array and even-length array


  • 6

    @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.


  • 1
    M

    I recommend you the famous book : Cracking the coding interview. It stats that the opt point should be median


  • 0

    @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 odd-length array and even-length array

    Same thought process as in - https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
    Go to the median.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.