Count Ways to Build Rooms in an Ant Colony - Problem

Math Dynamic Programming Tree Graph Topological Sort Combinatorics Hard

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 10⁹ + 7.

Input & Output

Example 1 — Basic Tree

$ Input: prevRoom = [-1,0,1,2]

› Output: 1

💡 Note: Only one valid order: build rooms in sequence 0→1→2→3 since each room depends on the previous one

Example 2 — Multiple Children

$ Input: prevRoom = [-1,0,0,1,2]

› Output: 8

💡 Note: Room 0 has children 1,2. Room 1 has children 3,4. Multiple valid orders exist like: 0→1→2→3→4, 0→1→3→2→4, etc.

Example 3 — Single Path

$ Input: prevRoom = [-1,0]

› Output: 1

💡 Note: Only two rooms: 0 is already built, then build room 1. Only one possible order.

Constraints

1 ≤ n ≤ 10⁵
prevRoom[0] == -1
0 ≤ prevRoom[i] ≤ n - 1 for all 1 ≤ i ≤ n - 1
prevRoom represents a valid tree

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18 a Amazon 15 F Facebook 12

The key insight is to recognize this as a tree combinatorics problem. Convert the dependency array into a tree structure, then use multinomial coefficients to count arrangements. For each node with subtrees of sizes [s1, s2, ..., sk], the number of ways is (s1+s2+...+sk)!/(s1!×s2!×...×sk!). Best approach uses DFS with mathematical formula. Time: O(n), Space: O(n)

Common Approaches

✓ Hash Map

⏱️ Time: N/A Space: N/A

Brute Force - Generate All Permutations

⏱️ Time: O(n!) Space: O(n)

Try every possible permutation of rooms 1 to n-1 and check if each order respects the dependency constraints. For each permutation, verify that every room is built after its prerequisite room.

DFS with Tree Structure

⏱️ Time: O(n²) Space: O(n)

Convert the prevRoom array into a tree structure, then use DFS to calculate the number of ways to arrange each subtree. For each node, multiply the arrangements of all subtrees and apply multinomial coefficient.

Mathematical Combinatorics Formula

⏱️ Time: O(n) Space: O(n)

For each node in the tree, calculate the number of ways to arrange its subtrees using the multinomial coefficient formula. The total ways is the product of multinomial coefficients for all internal nodes.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100000
#define MOD 1000000007

static int* children[MAX_NODES];
static int child_count[MAX_NODES];
static long long fact[MAX_NODES + 1];

long long pow_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

long long inv_mod(long long x) {
    return pow_mod(x, MOD - 2, MOD);
}

struct DFSResult {
    int size;
    long long ways;
};

struct DFSResult dfs(int node) {
    struct DFSResult result;
    
    if (child_count[node] == 0) {
        result.size = 1;
        result.ways = 1;
        return result;
    }
    
    int total_size = 1;
    long long total_ways = 1;
    int child_sizes[1000]; // Reasonable limit for children per node
    int num_children = child_count[node];
    
    for (int i = 0; i < child_count[node]; i++) {
        int child = children[node][i];
        struct DFSResult child_result = dfs(child);
        total_size += child_result.size;
        total_ways = (total_ways * child_result.ways) % MOD;
        child_sizes[i] = child_result.size;
    }
    
    // Calculate multinomial coefficient
    long long numerator = fact[total_size - 1];
    long long denominator = 1;
    for (int i = 0; i < num_children; i++) {
        denominator = (denominator * fact[child_sizes[i]]) % MOD;
    }
    
    long long multinomial = (numerator * inv_mod(denominator)) % MOD;
    total_ways = (total_ways * multinomial) % MOD;
    
    result.size = total_size;
    result.ways = total_ways;
    return result;
}

long long solution(int* prevRoom, int n) {
    // Initialize
    for (int i = 0; i < n; i++) {
        child_count[i] = 0;
        children[i] = NULL;
    }
    
    // First pass: count children for each node
    for (int i = 1; i < n; i++) {
        int parent = prevRoom[i];
        child_count[parent]++;
    }
    
    // Allocate memory for children arrays
    for (int i = 0; i < n; i++) {
        if (child_count[i] > 0) {
            children[i] = (int*)malloc(child_count[i] * sizeof(int));
        }
        child_count[i] = 0; // Reset for second pass
    }
    
    // Second pass: build adjacency list for children
    for (int i = 1; i < n; i++) {
        int parent = prevRoom[i];
        children[parent][child_count[parent]] = i;
        child_count[parent]++;
    }
    
    // Precompute factorials
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i-1] * (long long)i) % MOD;
    }
    
    struct DFSResult result = dfs(0);
    
    // Clean up memory
    for (int i = 0; i < n; i++) {
        if (children[i] != NULL) {
            free(children[i]);
        }
    }
    
    return result.ways;
}

int main() {
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    int prevRoom[MAX_NODES];
    int n = 0;
    
    char* ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    ptr++; // skip '['
    
    while (*ptr && *ptr != ']') {
        while (*ptr && (*ptr == ' ' || *ptr == '\t' || *ptr == '\n')) ptr++;
        if (*ptr == ']') break;
        
        char* endptr;
        int val = (int)strtol(ptr, &endptr, 10);
        prevRoom[n++] = val;
        ptr = endptr;
        
        while (*ptr && (*ptr == ' ' || *ptr == '\t' || *ptr == '\n')) ptr++;
        if (*ptr == ',') ptr++;
    }
    
    long long result = solution(prevRoom, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen