This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

There's a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the

**Example 1:**

Input:Height : 5 Width : 7 Tree position : [2,2] Squirrel : [4,4] Nuts : [[3,0], [2,5]]Output:12Explanation:

**Note:**

- All given positions won't overlap.
- The squirrel can take at most one nut at one time.
- The given positions of nuts have no order.
- Height and width are positive integers. 3 <= height * width <= 10,000.
- The given positions contain at least one nut, only one tree and one squirrel.

b'

\n## Solution

\n

\n#### Approach #1 Simple Solution [Accepted]

\n

\n

'
\n\n

\n\n

**Algorithm**

We know, the distance between any two points(tree, squirrel, nut) is given by the absolute difference between the corresponding x-coordinates and the corresponding y-coordinates.

\nNow, in order to determine the required minimum distance, we need to observe a few points. Firstly, the order in which the nuts are picked doesn\'t affect the final result, except one of the nuts which needs to be visited first from the squirrel\'s starting position. For the rest of the nuts, it is mandatory to go from the tree to the nut and then come back as well.

\nFor the first visited nut, the saving obtained, given by , is the difference between the distance between the tree and the current nut & the distance between the current nut and the squirrel. This is because for this nut, we need not travel from the tree to the nut, but need to travel an additional distance from the squirrel\'s original position to the nut.

\nWhile traversing over the array and adding the to-and-fro distance, we find out the saving, , which can be obtained if the squirrel goes to the current nut first. Out of all the nuts, we find out the nut which maximizes the saving and then deduct this maximum saving from the sum total of the to-and-fro distance of all the nuts.

\nNote that the first nut to be picked needs not necessarily be the nut closest to the squirrel\'s start point, but it\'s the one which maximizes the savings.

\n\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . We need to traverse over the whole array once. refers to the size of array.

\n \n - \n
Space complexity : . Constant space is used.

\n \n

\n

Analysis written by: @vinod23

\n