There are n rooms you need to visit, labeled from 0 to n - 1. Each day is labeled, starting from 0. You will go in and visit one room a day.
Initially on day 0, you visit room 0. The order you visit the rooms for the coming days is determined by the following rules and a given 0-indexed array nextVisit of length n:
i,i an odd number of times (including the current visit), on the next day you will visit a room with a lower or equal room number specified by nextVisit[i] where 0 <= nextVisit[i] <= i;i an even number of times (including the current visit), on the next day you will visit room (i + 1) mod n.Return the label of the first day where you have been in all the rooms. It can be shown that such a day exists. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nextVisit = [0,0] Output: 2 Explanation: - On day 0, you visit room 0. The total times you have been in room 0 is 1, which is odd. On the next day you will visit room nextVisit[0] = 0 - On day 1, you visit room 0, The total times you have been in room 0 is 2, which is even. On the next day you will visit room (0 + 1) mod 2 = 1 - On day 2, you visit room 1. This is the first day where you have been in all the rooms.
Example 2:
Input: nextVisit = [0,0,2] Output: 6 Explanation: Your room visiting order for each day is: [0,0,1,0,0,1,2,...]. Day 6 is the first day where you have been in all the rooms.
Example 3:
Input: nextVisit = [0,1,2,0] Output: 6 Explanation: Your room visiting order for each day is: [0,0,1,1,2,2,3,...]. Day 6 is the first day where you have been in all the rooms.
Constraints:
n == nextVisit.length2 <= n <= 1050 <= nextVisit[i] <= iThe key challenge in #1997 First Day Where You Have Been in All the Rooms is determining the earliest day when every room has been visited at least once while following the movement rules defined by the nextVisit array. A brute-force simulation can become inefficient because revisiting rooms creates repeated patterns.
A more efficient solution uses dynamic programming. Let dp[i] represent the first day when you reach room i for the first time. The transition depends on the previous room and the rule that determines whether you move forward or jump back to nextVisit[i]. By analyzing how many days it takes to return and move forward again, you can build a recurrence that accumulates the required days while avoiding repeated simulation.
Since the number of days can grow large, results are computed using modulo arithmetic. This approach processes each room once, resulting in O(n) time complexity and O(n) space complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with prefix recurrence | O(n) | O(n) |
ThePrimeTime
Use these hints if you're stuck. Try solving on your own first.
The only way to get to room i+1 is when you are visiting room i and room i has been visited an even number of times.
After visiting room i an odd number of times, you are required to visit room nextVisit[i] where nextVisit[i] <= i. It takes a fixed amount of days for you to come back from room nextVisit[i] to room i. Then, you have visited room i even number of times.nextVisit[i]
Can you use Dynamic Programming to avoid recomputing the number of days it takes to visit room i from room nextVisit[i]?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving arrays and dynamic programming patterns similar to this one are common in FAANG-style interviews. While the exact problem may vary, understanding recurrence relations and optimized state transitions is frequently tested.
A simple array is sufficient to store dynamic programming values for each room. The dp array keeps track of the earliest day each room is first reached, allowing efficient reuse of previously computed results.
The optimal approach uses dynamic programming to track the first day each room is visited. Instead of simulating every move, it derives a recurrence based on previously computed days and the nextVisit index. This avoids repeated traversal patterns and runs in linear time.
Dynamic programming helps avoid repeatedly simulating the same back-and-forth movements between rooms. By storing the first visit day for each room, the algorithm can directly compute the next state using previously solved subproblems.