Python solution using median


  • 0

    Find median point, calculate distance for each people and sum them up. No need to sort list twice the list for i is naturally sorted.

    class Solution(object):
        def minTotalDistance(self, grid):
            if grid is None or len(grid) == 0:
                return 0
            ilist, jlist, ppl = [], [], []
            for i in xrange(0, len(grid)):
                for j in xrange(0, len(grid[0])):
                    if grid[i][j] == 1:
                        ppl.append((i, j))
                        ilist.append(i)
                        jlist.append(j)
            c = (ilist[len(ilist)/2], sorted(jlist)[len(jlist)/2])
            return sum(map(lambda p: abs(p[0] - c[0]) + abs(p[1] - c[1]), ppl))

Log in to reply
 

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