Solution


Approach 1: Simple Solution

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