Challenge
Challenge
Problem
Solutions
Submissions
Challenge Points: 30
Level: HardYou are constructing an ant colony with n rooms, labeled from 0 to n-1.
The building plan is described using an array prevRoom, where each room i can only be built after room prevRoom[i] has already been constructed. Room 0 is the starting point, so prevRoom[0] = -1.
The rooms form a connected structure once everything is built, and at any moment you are allowed to construct only one room at a time. You may freely move between any rooms that are already connected.
You must count how many different valid sequences of construction exist, following all dependency rules.
Since the result can be very large, return it modulo 1,000,000,007.
Input: prevRoom = [-1, 0, 1]
Output: 1
Explanation:
Room 0 → Room 1 → Room 2 is the only valid order.
Input: prevRoom = [-1, 0, 0, 2]
Output: 3
Explanation:
Valid sequences include: 0 → 1 → 2 → 3 0 → 2 → 3 → 1 0 → 1 → 3 → 2
Accepted:
Submission:
Report an issue
Code
You need toto run or submitYou need toto run or submit
Test Case
Test Result