Squirrel Simulation - Practice Coding Problems

Squirrel Simulation - Problem

Array Math Medium

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 = [treer, treec] is the position of the tree in the garden
An array squirrel where squirrel = [squirrelr, squirrelc] is the position of the squirrel in the garden
An array 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.

Input & Output

Example 1 — Basic Garden

$ Input: height = 5, width = 7, tree = [2,2], squirrel = [4,4], nuts = [[3,0], [2,5]]

› Output: 12

💡 Note: Squirrel collects nut at [3,0] first (distance 5), brings to tree (distance 3), then goes to [2,5] (distance 3), and brings back (distance 3). Total: 5+3+3+3 = 14. But optimal is 12 by choosing [2,5] first.

Example 2 — Single Nut

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

› Output: 3

💡 Note: Squirrel at [0,0] goes to nut at [0,2] (distance 2), then to tree at [0,1] (distance 1). Total: 2+1 = 3.

Example 3 — Multiple Nuts Close Together

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

› Output: 6

💡 Note: Base distance is 2×(1+1+1) = 6. Best savings comes from choosing optimal first nut, but all have same savings of 0. Total remains 6.

Constraints

1 ≤ height, width ≤ 100
tree.length == 2
squirrel.length == 2
1 ≤ nuts.length ≤ 5000
nuts[i].length == 2
0 ≤ treer, squirrelr, nutir ≤ height
0 ≤ treec, squirrelc, nutic ≤ width

Visualization

Tap to expand

Understanding the Visualization

Input Setup

Garden with squirrel, tree, and multiple nuts at different positions

Collection Process

Squirrel moves to nut, picks it up, brings to tree, repeats for all nuts

Optimization

Find order that minimizes total Manhattan distance traveled

Key Takeaway

🎯 Key Insight: Only the first nut collection matters for optimization since squirrel ends up at tree afterward

Asked in

G Google 15 a Amazon 8 f Facebook 6

The key insight is that only the first nut collection order matters for optimization - after collecting the first nut, the squirrel is at the tree, making subsequent order irrelevant. The optimal approach uses mathematical analysis: calculate base distance (2 × sum of all nut-to-tree distances) then subtract maximum savings from choosing the best first nut. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Optimization	O(n)	O(1)	Use mathematical insight: only the first nut collection matters for optimization
Brute Force - Try All Orders	O(n! × n)	O(n!)	Generate all possible orders of collecting nuts and find minimum total distance

Mathematical Optimization — Algorithm Steps

Calculate base distance: sum of all (nut to tree) distances × 2
For each nut, calculate savings if collected first
Choose nut with maximum savings

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Distance

Calculate 2 × (distance from each nut to tree)

Find Savings

For each nut, calculate savings = tree→nut - squirrel→nut

Optimal Choice

Choose nut with maximum savings as first collection

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int manhattanDistance(int* p1, int* p2) {
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]);
}

int solution(int height, int width, int* tree, int* squirrel, int** nuts, int nutsSize) {
    // Base distance: sum of all nut-to-tree distances × 2
    int totalDistance = 0;
    for (int i = 0; i < nutsSize; i++) {
        totalDistance += manhattanDistance(nuts[i], tree) * 2;
    }
    
    // Find maximum savings by choosing optimal first nut
    int maxSavings = INT_MIN;
    for (int i = 0; i < nutsSize; i++) {
        // Savings = (tree to nut) - (squirrel to nut)
        int savings = manhattanDistance(tree, nuts[i]) - manhattanDistance(squirrel, nuts[i]);
        if (savings > maxSavings) {
            maxSavings = savings;
        }
    }
    
    return totalDistance - maxSavings;
}

int main() {
    int height, width;
    scanf("%d", &height);
    scanf("%d", &width);
    
    int tree[2], squirrel[2];
    char buffer[1000];
    
    scanf("%s", buffer);
    sscanf(buffer, "[%d,%d]", &tree[0], &tree[1]);
    
    scanf("%s", buffer);
    sscanf(buffer, "[%d,%d]", &squirrel[0], &squirrel[1]);
    
    // For demo purposes, using fixed size
    int nutsSize = 3;
    int** nuts = (int**)malloc(nutsSize * sizeof(int*));
    for (int i = 0; i < nutsSize; i++) {
        nuts[i] = (int*)malloc(2 * sizeof(int));
        // Would need proper JSON parsing here
        nuts[i][0] = i;
        nuts[i][1] = i + 1;
    }
    
    int result = solution(height, width, tree, squirrel, nuts, nutsSize);
    printf("%d\n", result);
    
    for (int i = 0; i < nutsSize; i++) {
        free(nuts[i]);
    }
    free(nuts);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through all nuts to find maximum savings

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

425 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler