Skip to main content
Talentd

Rabbits in Forest - Solution & Explanation

MediumArrayHash TableMathGreedy10 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

There is a forest with an unknown number of rabbits. We asked n rabbits "How many rabbits have the same color as you?" and collected the answers in an integer array answers where answers[i] is the answer of the ith rabbit.

Given the array answers, return the minimum number of rabbits that could be in the forest.

 

Example 1:

Input: answers = [1,1,2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit that answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Example 2:

Input: answers = [10,10,10]
Output: 11

 

Constraints:

  • 1 <= answers.length <= 1000
  • 0 <= answers[i] < 1000

Approach Overview

Problem Overview: Each rabbit reports how many other rabbits share its color. Given these answers in an array, compute the minimum number of rabbits that could exist in the forest.

Approach 1: Greedy Grouping Approach (O(n) time, O(n) space)

The key observation: if a rabbit says x, it belongs to a color group of size x + 1. Multiple rabbits can give the same answer, but only up to x + 1 of them can belong to the same group. Count frequencies of each answer using a hash map from the hash table pattern. For each value x with frequency f, divide rabbits into groups of size x + 1. The number of groups required is ceil(f / (x + 1)). Multiply the number of groups by the group size to get the total rabbits contributed by that answer.

This works because rabbits reporting the same value may represent several separate color groups. The greedy step is packing as many rabbits as possible into each valid group before starting another. Time complexity is O(n) for one pass counting and one pass over unique answers, with O(n) space for the frequency map.

Approach 2: Bucket Counting Approach (O(n) time, O(n) space)

Instead of computing groups directly from frequencies, simulate filling groups while iterating through the array. Maintain a map where each answer x tracks how many rabbits have already filled the current bucket of size x + 1. When a new rabbit with answer x appears, either place it in an existing bucket or start a new bucket if the current one is full. Each time a new bucket is created, immediately add x + 1 rabbits to the total.

This approach mirrors the grouping logic but processes rabbits sequentially. It uses simple counting and conditional checks, which makes it intuitive during implementation. The algorithm still runs in O(n) time and uses O(n) space for tracking partially filled groups. The idea fits naturally with greedy reasoning and counting techniques often used in array problems.

Recommended for interviews: The Greedy Grouping approach is what interviewers typically expect. It shows that you understand the mathematical constraint that each answer defines a fixed group size and that frequencies may require multiple groups. Explaining why ceil(f / (x + 1)) groups are needed demonstrates both greedy reasoning and careful counting.

Approach 1: Greedy Grouping Approach

This approach involves using a greedy strategy to group rabbits based on their answers. The idea is to minimize the new groups formed by properly counting how many times each answer is reported. For an answer 'x', at most 'x + 1' rabbits can share the same color including the answering rabbit. You should calculate the number of groups required to accommodate rabbits with the same answer.

This Python solution first counts the frequency of each answer using a Counter. For each unique answer 'x', it calculates how many groups of size 'x + 1' are needed to account for all rabbits that gave this answer. It then accumulates this into the total count of rabbits.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), where n is the length of the answers array. Because we maintain a frequency count with a dictionary and process the results.

Space Complexity: O(n), which is the space required to store the counter dictionary.

Try this approach in the editor →

Approach 2: Bucket Counting Approach

In this approach, we use discrete buckets to count the occurrences of each answer. By directly iterating and placing rabbits in their respective buckets based on their answer, we can calculate the minimum number needed. This approach optimizes space and iteration by leveraging mathematical group handling of repeated counts.

This Java implementation also utilizes a hashmap to count the occurrences of each distinct answer. By calculating the minimal groups necessary with a simple ceiling division, the method aggregates the total rabbits needed.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n), iterating through the array and the map.

Space Complexity: O(n), storing frequencies in the hashmap.

Try this approach in the editor →

Approach 3: Greedy + Hash Map

According to the problem description, rabbits that give the same answer may belong to the same color, while rabbits that give different answers cannot belong to the same color.

Therefore, we use a hash map cnt to record the number of occurrences of each answer. For each answer x and its occurrence v, we calculate the minimum number of rabbits based on the principle that each color has x + 1 rabbits, and add it to the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array answers.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Grouping Approach

Time Complexity: O(n), where n is the length of the answers array. Because we maintain a frequency count with a dictionary and process the results.

Space Complexity: O(n), which is the space required to store the counter dictionary.

Bucket Counting Approach

Time Complexity: O(n), iterating through the array and the map.

Space Complexity: O(n), storing frequencies in the hashmap.

Greedy + Hash Map—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Grouping ApproachO(n)O(n)Best general solution; directly converts answer frequencies into minimum group counts.
Bucket Counting ApproachO(n)O(n)Useful when processing rabbits sequentially and simulating group filling logic.

Video Solution

Rabbits in Forest (Leetcode 781) | Hashmap Interview Question Playlist • Pepcoding • 12,403 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Rabbits in Forest easy or hard?
Rabbits in Forest is classified as a medium problem. The challenge comes from recognizing that identical answers may belong to multiple color groups and applying a greedy grouping formula. Once the grouping insight is clear, the implementation is straightforward.
How to solve Rabbits in Forest in O(n)?
Count how many times each answer x appears using a hash table. Each group for that answer must contain exactly x + 1 rabbits. Compute the number of required groups as ceil(f / (x + 1)) and multiply by x + 1 to add the minimum rabbits contributed by that answer. Summing across all unique answers gives the result in O(n) time.
What is the best approach for Rabbits in Forest?
The greedy grouping approach is the most efficient and commonly expected solution. Count how many rabbits report each value x, then form groups of size x + 1. The number of groups needed is ceil(f / (x + 1)) where f is the frequency of that answer. This runs in O(n) time with O(n) space using a hash map.
What data structure is used in Rabbits in Forest?
The core data structure is a hash map (dictionary) used to count how many rabbits give the same answer. This frequency map enables grouping rabbits into valid color groups efficiently. Some implementations also use simple counters or buckets to track partially filled groups.
What is the time complexity of Rabbits in Forest?
The optimal solution runs in O(n) time because the algorithm iterates through the answers once to build frequencies and once more to compute group counts. Space complexity is O(n) due to the hash map storing counts of each answer value.
Rabbits in Forest Python or Java solution approach
Both Python and Java solutions typically implement the greedy frequency approach. Use a dictionary or HashMap to count occurrences of each answer, compute groups using ceil(f / (x + 1)), and accumulate the total rabbits. The logic stays identical across languages with O(n) time complexity.
Is Rabbits in Forest asked at Google, Amazon, or Meta?
Rabbits in Forest is a common medium-level interview problem focusing on greedy reasoning and counting. Variants of grouping-by-constraints problems appear in interviews at companies like Amazon, Google, and Meta because they test mathematical reasoning and hash map usage.

Ready to solve this problem?

Practice Rabbits in Forest with our built-in code editor and test cases.

Practice on FleetCode
Previous

Group the People Given the Group Size They Belong To