Share my 3ms O(MN) Solution, JAVA


  • 1

    The idea is the expand the question from 1-D to 2-D, using the same observation:

    • It will cost less distance if the meeting point is near the "major population".
    • How the find the meeting point? -> Two pointer
    • How to do it 2-D? -> Find horizontal, then vertical.
    public class Solution {
        public int minTotalDistance(int[][] grid) {
            if(grid.length==0 || grid[0].length==0) return 0;
            int[] row = new int[grid.length];
            int[] col = new int[grid[0].length];
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[0].length;j++){
                    row[i]+=grid[i][j];
                    col[j]+=grid[i][j];
                }
            }
            return helper(row) + helper(col);
        }
        public int helper(int[] nums){
            if(nums.length==0) return 0;
            int left = 0, right = 0, lo = 0, hi = nums.length-1;
            while(lo<hi)
                if(left+nums[lo]<=right+nums[hi]) left+=nums[lo++];
                else right+=nums[hi--];
            int ret = 0;
            for(int i=0;i<nums.length;i++) ret += nums[i] * Math.abs(lo-i);
            return ret;
        }
    }
    

  • 0
    S

    I think this is O(mn) time and O(m+n) space?
    I used another helper with 2ms:

    private int helper(int[] T) {
            int lo = 0;
            int hi = T.length-1;
            int sum = 0;
            while(lo<hi){
                if(T[lo]<T[hi]){
                    sum += T[lo];
                    T[lo+1] += T[lo];
                    lo++;
                }else{
                    sum += T[hi];
                    T[hi-1] += T[hi];
                    hi--;
                }
            }
            return sum;
        }
    

  • 0

    @SidneyFan You're right. It is O(MN), since we need to at least traverse every cell in the matrix.


Log in to reply
 

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