Python solution with comments that beats 90%


  • 0
    L
    # solve it in x and y dimension, and min == min(x) + min(y)
    class Solution(object):
    
        def get_min(self, proj, count, points):
            # calculate the value of meeting at point 0 first
            min_d = 0
            for k, v in proj.items():
                # skip the first index
                if k == 0:
                    continue
                min_d += k * v
    
            # for a given point p (start from 0), l_val and r_val hold total
            # distance of all points on left and right side of p respectively.
            # l_count and r_count represent the number of points on left and right
            # side of p respectively.
            l_val, r_val = 0, min_d
            l_count, r_count = 0, count - proj.get(0, 0)
    
            # iterate through each possible meet point.
            # Update left count and increment total distance of all left points by 1.
            # Decrement total distance of all right points by 1 and update right count.
            for i in range(1, points):
                # for left pt, we update count first, then update val
                # for right pt, we update val then update count
                l_count += proj.get(i - 1, 0)
                l_val += l_count
    
                r_val -= r_count
                r_count -= proj.get(i, 0)
    
                min_d = min(min_d, l_val + r_val)
    
            # when meeting point is at the last index
            l_count += proj.get(points - 1, 0)
            l_val += l_count
            min_d = min(min_d, l_val)
    
            return min_d
    
        def minTotalDistance(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            if len(grid) == 0 or len(grid[0]) == 0:
                return 0
    
            # x, y contains projections of 1s in each dimension
            x = {}
            y = {}
            count = 0
            for i, r in enumerate(grid):
                for j, v in enumerate(r):
                    if v != 1:
                        continue
                    count += 1
                    x[i] = x.get(i, 0) + 1
                    y[j] = y.get(j, 0) + 1
            min_x = self.get_min(x, count, len(grid))
            min_y = self.get_min(y, count, len(grid[0]))
            return min_x + min_y
    

Log in to reply
 

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