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 <= 10000 <= answers[i] < 1000Problem 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.
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.
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.
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.
Java
JavaScript
Time Complexity: O(n), iterating through the array and the map.
Space Complexity: O(n), storing frequencies in the hashmap.
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.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Grouping Approach | O(n) | O(n) | Best general solution; directly converts answer frequencies into minimum group counts. |
| Bucket Counting Approach | O(n) | O(n) | Useful when processing rabbits sequentially and simulating group filling logic. |
Rabbits in Forest (Leetcode 781) | Hashmap Interview Question Playlist • Pepcoding • 12,306 views views
Watch 9 more video solutions →Practice Rabbits in Forest with our built-in code editor and test cases.
Practice on FleetCode