Count Ways to Build Rooms in an Ant Colony LeetCode solution in Python

1
# Runtime: 4732 ms (Top 93.33%) | Memory: 177.5 MB (Top 6.67%)
2
class Solution:
3
    def waysToBuildRooms(self, prevRoom: List[int]) -> int:
4
        mod = 10**9 + 7
5
        n = len(prevRoom)
6

7
        mod_inverses = [1] * (n + 1)
8
        factorials = [1] * (n + 1)
9
        inverse_factorials = [1] * (n + 1)
10

11
        for x in range(
12
            2, n + 1
13
        ):  # Precompute all factorials and inverse factorials needed in O(1) time each
14
            mod_inverses[x] = mod - mod // x * mod_inverses[mod % x] % mod
15
            factorials[x] = (x * factorials[x - 1]) % mod
16
            inverse_factorials[x] = (mod_inverses[x] * inverse_factorials[x - 1]) % mod
17

18
        children = collections.defaultdict(
19
            list
20
        )  # Convert parent list to children lists
21
        for i, x in enumerate(prevRoom[1:], 1):
22
            children[x].append(i)
23

24
        def postorder(curr: int) -> Tuple[int, int]:
25
            if curr not in children:  # Leaf has ways, size both 1
26
                return 1, 1
27
            tot_size = 1
28
            tot_ways = 1
29
            for child in children[curr]:
30
                ways, size_of = postorder(child)
31
                tot_ways *= ways * inverse_factorials[size_of]
32
                tot_size += size_of
33
            tot_ways *= factorials[tot_size - 1]
34
            return tot_ways % mod, tot_size
35

36
        return postorder(0)[0]