We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Ways to Build Rooms in an Ant Colony

Difficulty: Hard

Problem Description

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^9 + 7.

Key Insights

  • Each room can only be built if its prerequisite room is already built.
  • The problem can be modeled as a tree where room 0 is the root.
  • The number of ways to build the rooms depends on the structure of the tree and the number of ways to arrange subtrees.
  • The order of building rooms can be determined using combinatorial mathematics, specifically calculating permutations of groups of rooms.

Space and Time Complexity

Time Complexity: O(n) - We traverse each room and its dependencies once. Space Complexity: O(n) - We store the tree structure and additional information for calculations.

Solution

The problem can be solved using a depth-first search (DFS) to explore the tree structure formed by the rooms. For each room, we can calculate the number of permutations of its children using combinatorial formulas. The key data structure used is an adjacency list to represent the dependencies between rooms. The algorithm involves recursively calculating the number of ways to build each subtree and combining these results to find the total number of valid room-building orders.

Code Solutions

def countOrders(prevRoom):
    from collections import defaultdict
    from math import factorial
    
    MOD = 10**9 + 7
    n = len(prevRoom)
    tree = defaultdict(list)
    
    for i in range(1, n):
        tree[prevRoom[i]].append(i)
    
    def dfs(node):
        total_ways = 1
        total_children = 0
        
        for child in tree[node]:
            child_ways, child_count = dfs(child)
            total_ways = total_ways * child_ways % MOD
            total_children += child_count
        
        total_children += 1  # count the current node
        
        # Compute the number of ways to arrange the children
        total_ways = total_ways * factorial(total_children - 1) % MOD
        
        return total_ways, total_children
    
    return dfs(0)[0]

# Example usage
print(countOrders([-1, 0, 0, 1, 2]))  # Output: 6
← Back to All Questions