Watch 4 video solutions for Count Ways to Build Rooms in an Ant Colony, a hard level problem involving Math, Dynamic Programming, Tree. This walkthrough by Happy Coding has 2,977 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are an ant tasked with adding n new rooms numbered 0 to n-1 to your colony. You are given the expansion plan as a 0-indexed integer array of length n, prevRoom, where prevRoom[i] indicates that you must build room prevRoom[i] before building room i, and these two rooms must be connected directly. Room 0 is already built, so prevRoom[0] = -1. The expansion plan is given such that once all the rooms are built, every room will be reachable from room 0.
You can only build one room at a time, and you can travel freely between rooms you have already built only if they are connected. You can choose to build any room as long as its previous room is already built.
Return the number of different orders you can build all the rooms in. Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: prevRoom = [-1,0,1] Output: 1 Explanation: There is only one way to build the additional rooms: 0 → 1 → 2
Example 2:
Input: prevRoom = [-1,0,0,1,2] Output: 6 Explanation: The 6 ways are: 0 → 1 → 3 → 2 → 4 0 → 2 → 4 → 1 → 3 0 → 1 → 2 → 3 → 4 0 → 1 → 2 → 4 → 3 0 → 2 → 1 → 3 → 4 0 → 2 → 1 → 4 → 3
Constraints:
n == prevRoom.length2 <= n <= 105prevRoom[0] == -10 <= prevRoom[i] < n for all 1 <= i < n0 once all the rooms are built.Problem Overview: You are given a tree where each node represents a room and prevRoom[i] indicates which room must be built before room i. Room 0 is already built. The task is to count how many different valid orders exist to build all rooms while respecting these parent dependencies.
Approach 1: DFS and Combinatorics (O(n) time, O(n) space)
Treat the dependency structure as a rooted tree. Each subtree can be built independently once its parent is finished. During a DFS, compute the size of each subtree and the number of valid ways to arrange nodes inside it. When combining children, use combinatorics: if subtrees have sizes s1, s2, ..., the number of ways to interleave them is a multinomial coefficient. Precompute factorials and modular inverses to evaluate combinations under modulo. This approach leverages tree traversal and combinatorics to merge subtree results efficiently.
Approach 2: Dynamic Programming with Tree Representation (O(n) time, O(n) space)
Build an adjacency list from the parent array and run a DFS that returns two values for each node: the number of nodes in its subtree and the number of valid build orders for that subtree. While processing children, accumulate subtree sizes and multiply the child arrangements with combination counts representing interleavings. The DP state essentially captures "ways to build this subtree" while respecting dependencies. This formulation fits naturally with dynamic programming on trees.
Approach 3: Combination Mathematics in Tree (O(n) time, O(n) space)
The mathematical perspective models the problem as counting valid topological orders of a rooted tree. For each node with children subtrees of sizes s1, s2, ..., you place their nodes among s1 + s2 + ... slots. The number of placements equals (s1+s2+...)! / (s1! * s2! * ...). Multiply this with the number of arrangements inside each subtree. Precompute factorials and inverse factorials once, then evaluate each combination in constant time.
Approach 4: Topological Sort with Dynamic Programming (O(n) time, O(n) space)
Interpret the dependency tree as a DAG and process nodes using a topological sort. Maintain DP values representing ways to construct partial subgraphs and combine them when prerequisites are satisfied. Although the structure is still a tree, framing it as a topological ordering problem helps when reasoning about dependency scheduling and incremental state transitions.
Recommended for interviews: DFS with combinatorics is the expected solution. It shows you understand how subtree independence leads to multinomial combinations. A brute-force enumeration of topological orders quickly becomes exponential, while the combinatorial tree DP reduces the problem to linear time with precomputed factorials.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS and Combinatorics | O(n) | O(n) | Best general solution; combines subtree sizes with multinomial coefficients |
| Dynamic Programming on Tree | O(n) | O(n) | When implementing structured subtree DP with explicit states |
| Combination Mathematics in Tree | O(n) | O(n) | When focusing on mathematical formulation of valid interleavings |
| Topological Sort with DP | O(n) | O(n) | Useful for reasoning about dependency ordering in DAG-style problems |