Scale Engineer

Count Ways to Build Rooms in an Ant Colony

Hard
#1749Time: 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.
Patterns
MathDynamic ProgrammingCombinatorics
Algorithms
Topological Sort
Data structures
TreeGraph

Prompt

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.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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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).

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem