Watch 10 video solutions for Rabbits in Forest, a medium level problem involving Array, Hash Table, Math. This walkthrough by Pepcoding has 12,306 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |