# Count Ways to Build Rooms in an Ant Colony
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-ways-to-build-rooms-in-an-ant-colony)
Canonical: https://scaleengineer.com/dsa/problems/count-ways-to-build-rooms-in-an-ant-colony
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Tree, Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-ways-to-build-rooms-in-an-ant-colony/image0.JPG) 

**Input:** prevRoom = [-1,0,1]
**Output:** 1
**Explanation:** There is only one way to build the additional rooms: 0 → 1 → 2

**Example 2:**

**![](https://assets.glich.co/dsa/count-ways-to-build-rooms-in-an-ant-colony/image1.JPG)** 

**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.length`
* `2 <= n <= 105`
* `prevRoom[0] == -1`
* `0 <= prevRoom[i] < n` for all `1 <= i < n`
* Every room is reachable from room `0` once all the rooms are built.

# Approaches
## Brute Force by Generating All Permutations
This approach generates every possible build order (permutation) of the `n-1` rooms and checks if each order is valid. A valid order requires that for any room, its prerequisite room is built before it.
**Time:** O(n * (n-1)!) - There are `(n-1)!` permutations to generate. For each permutation, we perform a validation check that takes O(n) time. · **Space:** O(n) - To store the current permutation, the recursion stack, and the set of built rooms.
**Pros:** Simple to understand and implement the logic.
**Cons:** Extremely inefficient due to factorial time complexity.; Not feasible for the problem constraints where `n` can be up to 10^5.
### Explanation
The most straightforward but naive way to solve this problem is to explore all possible sequences of building the rooms. Since room 0 is already built, we need to decide the order for the remaining `n-1` rooms. The total number of such orders is `(n-1)!`.

We can generate each of these `(n-1)!` permutations and, for each one, verify if it represents a valid building plan. A plan is valid if, for every room in the sequence, its direct prerequisite has been built earlier in the sequence. We can maintain a set of built rooms, initially containing just room 0, and iterate through the permutation, checking the prerequisite condition at each step.

```java
import java.util.*;

class Solution {
    int count = 0;
    int n;
    int[] prevRoom;
    long MOD = 1_000_000_007;

    public int countWays(int[] prevRoom) {
        this.n = prevRoom.length;
        this.prevRoom = prevRoom;
        List<Integer> roomsToBuild = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            roomsToBuild.add(i);
        }
        permute(roomsToBuild, 0);
        return count;
    }

    private void permute(List<Integer> arr, int k) {
        if (k == arr.size()) {
            if (isValid(arr)) {
                count = (count + 1) % (int)MOD;
            }
            return;
        }
        for (int i = k; i < arr.size(); i++) {
            Collections.swap(arr, i, k);
            permute(arr, k + 1);
            Collections.swap(arr, k, i); // backtrack
        }
    }

    private boolean isValid(List<Integer> permutation) {
        Set<Integer> built = new HashSet<>();
        built.add(0);
        for (int room : permutation) {
            if (!built.contains(prevRoom[room])) {
                return false;
            }
            built.add(room);
        }
        return true;
    }
}
```
This approach is only practical for very small values of `n` (e.g., `n <= 12`).
### Algorithm
- Generate all permutations of the rooms from 1 to `n-1`.
- For each permutation `P`:
  - Initialize a set `built_rooms` containing only room `0`.
  - Iterate through the rooms `r` in the permutation `P`.
  - For each room `r`, check if its prerequisite `prevRoom[r]` is in `built_rooms`.
  - If the prerequisite is not present, the permutation is invalid. Break and check the next permutation.
  - If the prerequisite is present, add `r` to `built_rooms`.
  - If the entire permutation is processed without invalidating, it's a valid build order. Increment a counter.
- The final count is the answer.

## Backtracking with Memoization (Bitmask DP)
This approach improves upon brute force by building valid construction sequences step-by-step using backtracking. At each step, it only considers building rooms whose prerequisites have already been met. This prunes the search space by avoiding the generation of invalid sequences. Memoization is used to store the results for subproblems, turning the backtracking into a dynamic programming solution.
**Time:** O(n * 2^n) - There are `2^n` possible states (masks). For each state, we iterate through up to `n` rooms to find the next valid room to build. · **Space:** O(2^n) - For the memoization table to store results for each subset of built rooms.
**Pros:** Much more efficient than generating all permutations as it prunes invalid search paths early.; With memoization, it avoids recomputing results for the same subproblem.
**Cons:** The state space is `2^n`, which is too large for `n = 10^5`.; This approach will lead to Time Limit Exceeded and Memory Limit Exceeded for the given constraints.
### Explanation
Instead of generating a full permutation and then checking its validity, we can build the sequence one room at a time, ensuring that we only add rooms that are valid to build at that moment. This is a classic backtracking approach.

The state of our search can be defined by the set of rooms that have already been built. We can represent this set using a bitmask. We then write a recursive function that, given a set of built rooms, calculates the number of ways to build the remaining rooms.

To make this efficient, we use memoization (or dynamic programming) to store the results for each state (each bitmask), so we don't recompute the answer for the same set of built rooms multiple times.

```java
import java.util.Arrays;

class Solution {
    long[] memo;
    int n;
    int[] prevRoom;
    long MOD = 1_000_000_007;

    public int countWays(int[] prevRoom) {
        this.n = prevRoom.length;
        this.prevRoom = prevRoom;
        // This approach is only feasible for small n (e.g., n <= 20)
        // due to the 2^n state space.
        if (n > 20) { 
            // This is a placeholder; the actual efficient solution is needed.
            return 0; 
        }
        this.memo = new long[1 << n];
        Arrays.fill(memo, -1);
        // Start with room 0 already built (mask = 1)
        return (int) solve(1);
    }

    private long solve(int builtMask) {
        // Base case: if all rooms are built, we found one complete valid sequence.
        if (builtMask == (1 << n) - 1) {
            return 1;
        }
        // Return memoized result if available
        if (memo[builtMask] != -1) {
            return memo[builtMask];
        }

        long count = 0;
        // Find rooms that can be built now
        for (int i = 0; i < n; i++) {
            // If room i is not built yet
            if ((builtMask & (1 << i)) == 0) {
                // And its prerequisite is built
                if ((builtMask & (1 << prevRoom[i])) != 0) {
                    count = (count + solve(builtMask | (1 << i))) % MOD;
                }
            }
        }
        return memo[builtMask] = count;
    }
}
```
### Algorithm
- Define a recursive function, say `countValidOrders(built_mask)`.
- The `built_mask` is a bitmask representing the set of built rooms.
- Use a memoization table `memo[built_mask]` to store results and avoid recomputation.
- Base Case: If all rooms are built (`built_mask` has all `n` bits set), we have found one valid way. Return 1.
- Recursive Step:
  - Initialize `ways = 0`.
  - Iterate through all rooms `i` from 1 to `n-1`.
  - If room `i` is not yet built but its prerequisite `prevRoom[i]` is built (checked using the bitmask), it's a candidate for the next room to build.
  - Recursively call `countValidOrders` with an updated mask where bit `i` is set, and add the result to `ways`.
- The initial call would be `countValidOrders(1)` (mask for room 0 being built).

## Combinatorial Approach using DFS on Tree
This problem can be modeled as counting topological sorts on a tree, which lends itself to a combinatorial solution. By viewing the rooms and their prerequisites as a tree rooted at 0, we can use Dynamic Programming on the tree. A Depth First Search (DFS) traversal allows us to compute the size of each subtree and the number of ways to construct it. The results from children's subtrees are combined using combinatorial formulas, specifically combinations, to account for all possible interleavings of their construction sequences.
**Time:** O(N) - Building the tree takes O(N). Precomputation of factorials and their inverses takes O(N + log MOD). The DFS traversal visits each node and edge exactly once, performing O(1) work at each step (as `nCr` is O(1) with precomputation). · **Space:** O(N) - For the adjacency list representation of the tree, the recursion stack for DFS (up to O(N) in the worst case of a skewed tree), and the precomputed factorial arrays.
**Pros:** Highly efficient with linear time complexity, making it suitable for large constraints.; Provides an elegant mathematical solution to the problem.
**Cons:** Requires understanding of combinatorics (multinomial coefficients/combinations), modular arithmetic (modular inverse), and tree algorithms.; The implementation is more complex than the brute-force approaches.
### Explanation
The most efficient approach reframes the problem from generating sequences to a combinatorial counting problem on a tree. The `prevRoom` array describes a tree where `prevRoom[i]` is the parent of `i`.

The total number of ways to build all rooms is the number of ways to topologically sort the nodes of this tree, starting from the already-built root, 0.

Let's define a function `dfs(u)` that returns a pair of values for the subtree rooted at `u`: `(size, ways)`, where `size` is the number of nodes in the subtree and `ways` is the number of valid relative orderings to build the nodes in that subtree (assuming `u` itself is already built).

For a node `u`, we first recursively find the `(size, ways)` for all its children subtrees. Then, we combine them. If `u` has children `v1, v2, ...`, we are essentially merging the construction sequences of their subtrees. The number of ways to do this can be calculated using combinations. If we have already processed some children and have a partial subtree of size `s`, and now we are merging a new child subtree of size `s_child`, we have `s-1` nodes to arrange from the current partial subtree and `s_child` nodes from the new one. The number of ways to interleave them is `C(s-1 + s_child, s_child)`. We multiply this with the internal ways of each subtree.

This process is done recursively from the leaves up to the root using a DFS. All calculations are performed modulo `10^9 + 7`, which requires precomputing factorials and their modular inverses for calculating combinations `nCr` efficiently.

```java
import java.util.*;

class Solution {
    private static final int MOD = 1_000_000_007;
    private List<Integer>[] adj;
    private long[] fact;
    private long[] invFact;

    public int countWays(int[] prevRoom) {
        int n = prevRoom.length;
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            adj[prevRoom[i]].add(i);
        }

        precomputeFactorials(n);

        long[] result = dfs(0);
        return (int) result[1];
    }

    // Returns a pair: {subtree_size, num_ways}
    private long[] dfs(int u) {
        long size = 1;
        long ways = 1;

        for (int v : adj[u]) {
            long[] childResult = dfs(v);
            long childSize = childResult[0];
            long childWays = childResult[1];

            // We are merging the child's sequence of `childSize` nodes
            // with our current sequence of `size - 1` nodes.
            // The number of ways to interleave them is C(size - 1 + childSize, childSize).
            long combinations = nCr_mod_p(size - 1 + childSize, childSize);

            ways = (ways * childWays) % MOD;
            ways = (ways * combinations) % MOD;
            
            size += childSize;
        }
        return new long[]{size, ways};
    }

    private void precomputeFactorials(int n) {
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        invFact[n] = power(fact[n], MOD - 2);
        for (int i = n - 1; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private long nCr_mod_p(long n, long r) {
        if (r < 0 || r > n) return 0;
        long num = fact[(int)n];
        long den = (invFact[(int)r] * invFact[(int)(n - r)]) % MOD;
        return (num * den) % MOD;
    }
}
```
### Algorithm
- First, represent the `prevRoom` array as a tree structure, with room 0 as the root. An adjacency list is a good choice.
- The problem is now to find the number of ways to build the tree, which is equivalent to finding the number of ways to interleave the build sequences of subtrees.
- We need to perform calculations with factorials modulo a prime, so we precompute factorials and their modular inverses up to `n`.
- Use a DFS (post-order traversal) function, say `dfs(u)`, that computes two values for the subtree rooted at `u`: the total number of nodes in the subtree (`size`) and the number of ways to build that subtree (`ways`).
- In `dfs(u)`:
  - Base Case: If `u` is a leaf, its size is 1, and there's 1 way to build it (do nothing). Return `{1, 1}`.
  - Recursive Step: Initialize `size = 1` and `ways = 1` for node `u` itself.
  - For each child `v` of `u`:
    - Recursively call `dfs(v)` to get `child_size` and `child_ways`.
    - The total ways to build the combined structure of `u`'s current subtree and `v`'s subtree involves arranging `child_size` nodes among the `size - 1` already existing nodes. The number of ways to choose positions is given by the combination `C(size - 1 + child_size, child_size)`.
    - Update `ways = (ways * child_ways * C(size - 1 + child_size, child_size)) % MOD`.
    - Update `size = size + child_size`.
  - Return the final computed `size` and `ways` for the subtree at `u`.
- The final answer is the `ways` component returned by `dfs(0)`.

# Solutions
### Java

```java
class Solution {
  static final int MODULO = 1000000007;
public
  int waysToBuildRooms(int[] prevRoom) {
    int n = prevRoom.length;
    int[] degree = new int[n];
    for (int i = 0; i < n; i++) {
      if (prevRoom[i] >= 0)
        degree[prevRoom[i]]++;
    }
    int[] fac = new int[n + 1];
    Arrays.fill(fac, 1);
    int[] inv = new int[n + 1];
    Arrays.fill(inv, 1);
    for (int i = 2; i <= n; i++)
      fac[i] = (int)((long)i * fac[i - 1] % MODULO);
    for (int i = 2; i <= n; i++)
      inv[i] = (int)power(fac[i], MODULO - 2);
    Queue<Integer> queue = new LinkedList<Integer>();
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 0; i < n; i++) {
      if (degree[i] == 0)
        queue.offer(i);
    }
    int[] sizes = new int[n];
    Arrays.fill(sizes, 1);
    while (!queue.isEmpty()) {
      int u = queue.poll();
      dp[u] = (int)((long)dp[u] * fac[sizes[u] - 1] % MODULO);
      int v = prevRoom[u];
      if (v < 0)
        continue;
      sizes[v] += sizes[u];
      if (--degree[v] == 0)
        queue.offer(v);
      dp[v] = (int)((long)dp[v] * inv[sizes[u]] % MODULO * dp[u] % MODULO);
    }
    return dp[0];
  }
public
  long power(long x, int n) {
    long pow = 1;
    for (int i = n; i != 0; i /= 2) {
      if (i % 2 == 1)
        pow = pow * x % MODULO;
      x = x * x % MODULO;
    }
    return pow;
  }
}

```

### Python

```python
class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int: modulo = 10 ** 9 + 7 ingoing = defaultdict(set) outgoing = defaultdict(set) for i in range(1, len(prevRoom)): ingoing[i]. add(prevRoom[i]) outgoing[prevRoom[i]]. add(i) ans = [1] def recurse(i): if len(outgoing[i]) == 0: return 1 nodes_in_tree = 0 for v in outgoing[i]: cn = recurse(v) if nodes_in_tree != 0: ans[0] *= comb(nodes_in_tree + cn, cn) ans[0] %= modulo nodes_in_tree += cn return nodes_in_tree + 1 recurse(0) return ans[0] % modulo

```