573. Squirrel Simulation


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 minimal distance for the squirrel to collect all the nuts and put them under the tree one by one. The squirrel can only take at most one nut at one time and can move in four directions - up, down, left and right, to the adjacent cell. The distance is represented by the number of moves.

Example 1:

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

Note:

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


Solution

Approach #1 Simple Solution [Accepted]

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.

Now, 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.

For 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.

While 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.

Note 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.

Squirrel_Nuts

Complexity Analysis

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

  • Space complexity : . Constant space is used.

Analysis written by: @vinod23

Submit Solution