Squirrel Simulation - Solution & Explanation
Problem Statement
You are given two integers height and width representing a garden of size height x width. You are also given:
- an array
treewheretree = [treer, treec]is the position of the tree in the garden, - an array
squirrelwheresquirrel = [squirrelr, squirrelc]is the position of the squirrel in the garden, - and an array
nutswherenuts[i] = [nutir, nutic]is the position of theithnut 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 <= 100tree.length == 2squirrel.length == 21 <= nuts.length <= 5000nuts[i].length == 20 <= treer, squirrelr, nutir <= height0 <= treec, squirrelc, nutic <= width
Approach Overview
Problem Overview: A squirrel starts at a given position in a grid and must collect several nuts, dropping each one at a tree. The squirrel can only carry one nut at a time. Normally every nut trip starts and ends at the tree, except the very first trip which starts from the squirrel’s initial position. The task is to compute the minimum total Manhattan distance needed to collect all nuts.
Approach 1: Brute Force First-Nut Choice (O(n²) time, O(1) space)
Every nut except the first effectively costs 2 * dist(nut, tree) because the squirrel goes from the tree to the nut and back. The first nut is different since the squirrel starts at its initial position. One brute-force strategy is to try each nut as the first nut collected. For each candidate, compute the total cost by summing dist(squirrel, nut_i) + dist(nut_i, tree) for the first nut and 2 * dist(nut_j, tree) for the rest. This requires recomputing distances for every candidate, leading to O(n²) time with constant space.
Approach 2: Greedy Math Optimization (O(n) time, O(1) space)
The key observation: if the squirrel started at the tree, the total cost would simply be the sum of 2 * dist(nut, tree) for every nut. The only difference in the real scenario is the first nut. Instead of traveling tree → nut → tree, the squirrel travels squirrel → nut → tree. The change in cost is dist(squirrel, nut) - dist(nut, tree). Iterate through all nuts and find the nut that minimizes this extra cost (or equivalently maximizes the saving dist(nut, tree) - dist(squirrel, nut)). Compute the base cost for all nuts, then adjust it using the best candidate. Distances are simple Manhattan calculations on coordinates stored in an array. This turns the problem into a single linear scan using straightforward math and a small greedy decision.
Recommended for interviews: The greedy mathematical approach is what interviewers expect. It shows you can reduce repeated work by reasoning about the baseline cost and adjusting only the first move. Mentioning the brute-force idea first demonstrates understanding of the movement rules, while the optimized O(n) solution shows strong problem decomposition and distance analysis.
Solution
Observing the squirrel's movement path, we can see that the squirrel will first move to the position of a nut, then move to the position of the tree. After that, the total movement path of the squirrel is equal to "the sum of the distances from the remaining nuts to the tree" multiplied by 2.
Therefore, we only need to select a nut as the squirrel's first target, such that the sum of its distance to the tree is minimized, to obtain the shortest path.
The time complexity is O(n), where n is the number of nuts. The space complexity is O(1).
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force First-Nut Simulation | O(n²) | O(1) | Useful for reasoning about the problem or verifying correctness with small inputs |
| Greedy Mathematical Optimization | O(n) | O(1) | Best choice for interviews and production; computes base distance once and adjusts using the optimal first nut |
Video Solution
LC Premium 573. Squirrel Simulation | One Pass | Two Pass | O(n) time • Aryan Mittal • 734 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Squirrel Simulation easy or hard?
Squirrel Simulation Python/Java solution
How to solve Squirrel Simulation in O(n)?
What is the best approach for Squirrel Simulation?
Is Squirrel Simulation asked at Google/Amazon/Meta?
What data structure is used in Squirrel Simulation?
What is the time complexity of Squirrel Simulation?
Ready to solve this problem?
Practice Squirrel Simulation with our built-in code editor and test cases.
Practice on FleetCode