Watch 6 video solutions for Squirrel Simulation, a medium level problem involving Array, Math. This walkthrough by Aryan Mittal has 714 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integers height and width representing a garden of size height x width. You are also given:
tree where tree = [treer, treec] is the position of the tree in the garden,squirrel where squirrel = [squirrelr, squirrelc] is the position of the squirrel in the garden,nuts where nuts[i] = [nutir, nutic] is the position of the ith 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 <= 100tree.length == 2squirrel.length == 21 <= nuts.length <= 5000nuts[i].length == 20 <= treer, squirrelr, nutir <= height0 <= treec, squirrelc, nutic <= widthProblem 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.
| 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 |