5ms Java Accepted Solution O(n + m) for searching home, O(klogk) for finding min


  • 0
    Y

    Firstly, the manhattan distance should be calculated for x coordinate and y coordinate separately. Combine the result of x and y, you will get the final result.

    After turning into one dimensional problem. There still one assumption that the optimized point must fall on one of these points. This needs a little bit math and imagination.

    Then when we traverse the coordinate array, we first sort the array. Then, if there is any duplicate element, we do not need calculate twice. The distance is calculate by the prev + i * diff - (len - i) * diff

    Here, i * diff means the first half, (len - i) means the second half.

    public int minTotalDistance(int[][] grid) {
        int m = grid.length;
        if (m <= 0) {
            return 0;
        }
        int n = grid[0].length;
        if (n <= 0) {
            return 0;
        }
        
        int[] xCord = new int[n * m];
        int xLen = 0;
        int[] yCord = new int[n * m];
        int yLen = 0;
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] >= 1) {
                    xCord[xLen++] = i;
                    yCord[yLen++] = j;
                }
            }
        }
    
        return findDist(xCord, xLen) + findDist(yCord, yLen);
    }
    
    // There are one assumptions that hold here.
    // The best point must be one of the point on the line.
    public int findDist(int[] nums, int len) {
        
        Arrays.sort(nums, 0, len);
        int prevNum = nums[0];
        int prev = 0;
        // Calculate the dist for first number.
        for (int i = 1; i < len; i++) {
            prev += nums[i] - prevNum;
        }
        
        for (int i = 1; i < len; i++) {
            int curr = 0;
            int num = nums[i];
            if (prevNum == num) {
                continue;
            }
            
            // The dist from current to previous.
            int diff = num - prevNum;
            curr = prev + i * diff - (len - i) * diff;
            
            if (curr > prev) {
                return prev;    
            }
            
            prev = curr;
            prevNum = num;
        }
        
        return prev;
    }

  • 0

    Title should say "O(n * m)". And what is k? Interestingly, neither your explanation nor your code even contain the letter 'k' at all. I guess it's reeeaaally uncommon in English :-)


  • 1

    The optimal point does not necessarily has to fall on one of the 1's when the number of 1's is even.

    For example,

    1-1-0-0-1-1
    

    You can choose any of the x = 1 to x = 4 points and the total distance is minimized.


  • 0
    Y

    Hi, thanks for the reply. I mean, the optimal points can be multiple and it can fall on 0s. But at least one falls on one of the 1's. That's the assumption.


  • 0
    Y

    Sorry for the misunderstanding. k means number of houses.


Log in to reply
 

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