Is Squirrel Simulation easy or hard?

Squirrel Simulation is rated Medium because the challenge is recognizing the mathematical shortcut. The implementation is simple once you realize that every nut normally costs 2 * dist(nut, tree) and only the first trip changes the total distance.

Squirrel Simulation Python/Java solution

Both Python and Java implementations follow the same logic: compute the base distance 2 * dist(nut, tree) for all nuts, track the maximum saving dist(nut, tree) - dist(squirrel, nut), and add that adjustment to the total. The algorithm runs in O(n) time with constant extra space.

How to solve Squirrel Simulation in O(n)?

First compute the base total distance as the sum of 2 * dist(nut, tree) for all nuts. Then iterate through the nuts and calculate the adjustment value dist(nut, tree) - dist(squirrel, nut). The nut with the maximum saving should be collected first. Add this adjustment to the base total to get the minimum distance.

What is the best approach for Squirrel Simulation?

The optimal approach uses a greedy mathematical observation. First compute the baseline cost assuming the squirrel starts at the tree, which is 2 * Manhattan distance from each nut to the tree. Then adjust the total by choosing the nut that maximizes the saving dist(nut, tree) - dist(squirrel, nut). This reduces the problem to a single O(n) scan.

Is Squirrel Simulation asked at Google/Amazon/Meta?

Squirrel Simulation is a medium-level grid and distance optimization problem commonly seen in interview preparation platforms like LeetCode. Variations of Manhattan distance optimization and greedy selection appear in interviews at large tech companies including Google and Amazon.

What data structure is used in Squirrel Simulation?

The problem primarily uses arrays or lists to store nut coordinates. The main computation relies on Manhattan distance math and a linear scan through the array of nuts, so no advanced data structures are required.

What is the time complexity of Squirrel Simulation?

The optimal solution runs in O(n) time where n is the number of nuts. Each nut is processed once to compute its distance to the tree and to the squirrel. Space complexity is O(1) since only a few running variables are needed.

Description Hints 5 Solution Video 12:20

573. Squirrel Simulation

Medium57.1% acceptance1 companyPremium elsewhere, free here

You are given two integers height and width representing a garden of size height x width. You are also given:

an array tree where tree = [tree_r, tree_c] is the position of the tree in the garden,
an array squirrel where squirrel = [squirrel_r, squirrel_c] is the position of the squirrel in the garden,
and an array nuts where nuts[i] = [nut_{i_r}, nut_{i_c}] is the position of the i^th nut in the garden.

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.

Return the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one.

The distance is the number of moves.

Example 1:

Input: height = 5, width = 7, tree = [2,2], squirrel = [4,4], nuts = [[3,0], [2,5]]
Output: 12
Explanation: The squirrel should go to the nut at [2, 5] first to achieve a minimal distance.

Example 2:

Input: height = 1, width = 3, tree = [0,1], squirrel = [0,0], nuts = [[0,2]]
Output: 3

Constraints:

1 <= height, width <= 100
tree.length == 2
squirrel.length == 2
1 <= nuts.length <= 5000
nuts[i].length == 2
0 <= tree_r, squirrel_r, nut_{i_r} <= height
0 <= tree_c, squirrel_c, nut_{i_c} <= width

Asked at 1 company

Square

Topics

Array Math

Hints open one at a time

Hint 1

Will Brute force solution works here? What will be its complexity?

Hint 2

Brute force definitely won't work here. Think of some simple solution. Take some example and make some observations.

Hint 3

Will order of nuts traversed by squirrel is important or only first nut traversed by squirrel is important?

Hint 4

Are there some paths which squirrel have to cover in any case? If yes, what are they?

Hint 5

Did you notice only first nut traversed by squirrel matters? Obviously squirrel will choose first nut which will result in minimum distance.

12:20

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

5
7
[2,2]
[4,4]
[[3,0], [2,5]]

Input

1
3
[0,1]
[0,0]
[[0,2]]

Your code is saved on this device.Solution