#1916

Count Ways to Build Rooms in an Ant Colony

candidate master · 1405 · lc hard +32 · verified · 51.1% accepted · 524 likes · top 40%

Description

You are building n rooms numbered 0 to n - 1 for an ant colony. Room 0 is already built. The array prevRoom (where prevRoom[0] = -1) indicates that room prevRoom[i] must be built before room i.

Return the number of distinct build orders modulo 10⁹ + 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

Code

1

2

class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int:

class Solution:
    def waysToBuildRooms(self, prevRoom: List[int]) -> int: