1 line Python, O(nuts) time, O(1) space


  • 0

    This one is little bit tricky. After some observation we find out we need to walk through twice of the distance between nut and the tree for every nut except the first one we choose. And now you can see we transform this problem into find the closest nut to the squirrel.

    class Solution(object):
        def minDistance(self, height, width, tree, squirrel, nuts):
            """
            :type height: int
            :type width: int
            :type tree: List[int]
            :type squirrel: List[int]
            :type nuts: List[List[int]]
            :rtype: int
            """
            return 2 * sum(abs(x-tree[0]) + abs(y-tree[1]) for x,y in nuts) + \
                   min(abs(x-squirrel[0]) + abs(y-squirrel[1]) - abs(x-tree[0]) - abs(y-tree[1]) for x,y in nuts)
    

Log in to reply
 

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