# First Day Where You Have Been in All the Rooms
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/first-day-where-you-have-been-in-all-the-rooms)
Canonical: https://scaleengineer.com/dsa/problems/first-day-where-you-have-been-in-all-the-rooms
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance)
---
## Problem
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`:

* Assuming that on a day, you visit room `i`,
* if you have been in room `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`;
* if you have been in room `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.length`
* `2 <= n <= 105`
* `0 <= nextVisit[i] <= i`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. We keep track of the current day, the current room, and the number of times each room has been visited. We follow the rules day by day, advancing one day at a time, until we have visited all `n` rooms. The first day we visit room `n-1` is the first day we have visited all rooms.
**Time:** O(D), where D is the final answer (the number of days). Since D can be very large, this approach is too slow for the given constraints. · **Space:** O(n) to store the `counts` and `visited` arrays.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Requires minimal complex logic.
**Cons:** Extremely inefficient for the given constraints.; The number of days can be very large (up to 10^9), causing the simulation to run for a very long time and result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We can simulate the visiting process step-by-step. We'll need variables to keep track of the `currentDay`, the `currentRoom`, and an array `visitCounts` to store how many times each room has been visited.

The simulation starts on `day = 0` in `room = 0`. In a loop, we determine the next room to visit based on the current room and its visit count. If the number of visits to the current room (including the current one) is odd, we go to `nextVisit[currentRoom]`. If it's even, we go to `(currentRoom + 1) % n`. We increment the day and update the current room. This continues until we land on room `n-1` for the first time. Since we visit rooms `0, 1, ..., i-1` before visiting room `i` for the first time, the first day we reach room `n-1` is our answer.

While straightforward, this approach is too slow because the number of days can be enormous, and simulating each day individually is not feasible within typical time limits.

```java
// This is a conceptual implementation for illustration.
// It will time out for large inputs due to the large number of days.
class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.length;
        long[] counts = new long[n];
        int currentRoom = 0;
        long day = 0;
        boolean[] visited = new boolean[n];
        int visitedCount = 0;

        while (true) {
            if (!visited[currentRoom]) {
                visited[currentRoom] = true;
                visitedCount++;
                if (visitedCount == n) {
                    // We have just arrived at the last unvisited room.
                    return (int) day;
                }
            }

            counts[currentRoom]++;
            int nextRoom;
            if (counts[currentRoom] % 2 == 1) { // Odd visit
                nextRoom = nextVisit[currentRoom];
            } else { // Even visit
                nextRoom = (currentRoom + 1) % n;
            }
            
            currentRoom = nextRoom;
            day++;
        }
    }
}
```
### Algorithm
- Initialize `day = 0`, `currentRoom = 0`.
- Initialize a `counts` array of size `n` to store visit counts for each room.
- Loop until `currentRoom` is `n-1`:
  1. Increment the visit count for the `currentRoom` in the `counts` array.
  2. Determine the `nextRoom` based on the rules:
     - If `counts[currentRoom]` is odd, `nextRoom = nextVisit[currentRoom]`.
     - If `counts[currentRoom]` is even, `nextRoom = (currentRoom + 1) % n`.
  3. Update `currentRoom` to `nextRoom`.
  4. Increment `day`.
- Once the loop terminates, `day` holds the value of the first day we arrive at room `n-1`, which is the answer.

## Dynamic Programming
This approach uses dynamic programming to find the solution efficiently. We define `dp[i]` as the first day we arrive at room `i`. By finding a recurrence relation for `dp[i]`, we can compute the values iteratively in linear time, avoiding the slow day-by-day simulation. The final answer is `dp[n-1]`, calculated modulo `10^9 + 7`.
**Time:** O(n), as we iterate through the rooms from 1 to `n-1` once to fill the `dp` array. · **Space:** O(n) to store the `dp` array.
**Pros:** Highly efficient with linear time complexity.; Guaranteed to solve the problem within the time limits for the given constraints.
**Cons:** The derivation of the recurrence relation is non-trivial and requires careful logical reasoning about the problem's state transitions.
### Explanation
Let `dp[i]` be the first day we visit room `i`. Our goal is to find `dp[n-1]`.

The base case is `dp[0] = 0`, as we start in room 0 on day 0.

To find a recurrence for `dp[i]`, consider how we get to room `i` for the first time. We must have come from room `i-1`. This requires visiting room `i-1` an even number of times.

Let's analyze the sequence of events to get from the first visit of `i-1` to the first visit of `i`:
1.  On day `dp[i-1]`, we arrive at room `i-1` for the 1st time (an odd visit).
2.  On the next day, `dp[i-1] + 1`, we are sent to room `j = nextVisit[i-1]`.
3.  From room `j`, we need to travel back to room `i-1`. The path is `j -> j+1 -> ... -> i-1`. The time it takes to go from a room `k` to `k+1` for the first time is `dp[k+1] - dp[k]`. The total time to travel from `j` back to `i-1` is the sum of these travel times: `sum_{k=j}^{i-2} (dp[k+1] - dp[k])`. This is a telescoping sum which equals `dp[i-1] - dp[j] = dp[i-1] - dp[nextVisit[i-1]]`.
4.  So, we arrive back at room `i-1` after `dp[i-1] - dp[nextVisit[i-1]]` days from the day we were at room `j`. The day of this second arrival at `i-1` is `(dp[i-1] + 1) + (dp[i-1] - dp[nextVisit[i-1]])`.
5.  This is the 2nd visit to `i-1` (an even visit). On the *next* day, we will visit room `(i-1) + 1 = i`.
6.  Therefore, the day we first visit room `i` is `dp[i] = (day of 2nd visit to i-1) + 1`.

This gives the recurrence relation: `dp[i] = ( (dp[i-1] + 1) + (dp[i-1] - dp[nextVisit[i-1]]) ) + 1 = 2 * dp[i-1] - dp[nextVisit[i-1]] + 2`.

We can compute `dp[i]` for `i` from 1 to `n-1` using an array. All calculations must be done modulo `10^9 + 7`.

```java
class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.length;
        long[] dp = new long[n];
        int MOD = 1_000_000_007;
        
        // dp[i] = the first day we visit room i
        // Base case: we are at room 0 on day 0
        dp[0] = 0;
        
        for (int i = 1; i < n; i++) {
            // From room i-1, first visit (odd) is on day dp[i-1].
            // Next day, we go to nextVisit[i-1]. This takes 1 day.
            // To get from nextVisit[i-1] back to i-1, it takes (dp[i-1] - dp[nextVisit[i-1]]) days.
            // So, the day of the second visit to i-1 is:
            // dp[i-1] + 1 + (dp[i-1] - dp[nextVisit[i-1]])
            long secondVisitDay = dp[i-1] + 1 + (dp[i-1] - dp[nextVisit[i-1]]);

            // The day after the second visit, we go to room i.
            // So, dp[i] = secondVisitDay + 1
            long firstVisitDay_i = secondVisitDay + 1;
            
            // Simplified: dp[i] = 2 * dp[i-1] - dp[nextVisit[i-1]] + 2
            
            // Handle modulo for negative results
            dp[i] = (firstVisitDay_i % MOD + MOD) % MOD;
        }
        
        return (int) dp[n - 1];
    }
}
```
### Algorithm
- Define `MOD = 10^9 + 7`.
- Create a `dp` array of size `n`, where `dp[i]` will store the first day we visit room `i`.
- Set the base case: `dp[0] = 0`.
- Iterate `i` from 1 to `n-1`:
  - Calculate `dp[i]` using the recurrence relation: `dp[i] = (2 * dp[i-1] - dp[nextVisit[i-1]] + 2) % MOD`.
  - To handle potential negative results from subtraction, use the formula: `dp[i] = (2 * dp[i-1] - dp[nextVisit[i-1]] + 2 + MOD) % MOD`.
- The final answer is `dp[n-1]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int FirstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.Length;
        long[] f = new long[n];
        int mod = (int) 1 e9 + 7;
        for (int i = 1; i < n; ++i) {
            f[i] = (f[i - 1] + 1 + f[i - 1] - f[nextVisit[i - 1]] + 1 + mod) % mod;
        }
        return (int) f[n - 1];
    }
}
```

### Java

```java
class Solution { public int firstDayBeenInAllRooms ( int [] nextVisit ) { int n = nextVisit . length ; long [] f = new long [ n ]; final int mod = ( int ) 1 e9 + 7 ; for ( int i = 1 ; i < n ; ++ i ) { f [ i ] = ( f [ i - 1 ] + 1 + f [ i - 1 ] - f [ nextVisit [ i - 1 ]] + 1 + mod ) % mod ; } return ( int ) f [ n - 1 ]; } }
```

### CPP

```cpp
class Solution { public: int firstDayBeenInAllRooms ( vector < int >& nextVisit ) { int n = nextVisit . size (); vector < long long > f ( n ); const int mod = 1e9 + 7 ; for ( int i = 1 ; i < n ; ++ i ) { f [ i ] = ( f [ i - 1 ] + 1 + f [ i - 1 ] - f [ nextVisit [ i - 1 ]] + 1 + mod ) % mod ; } return f [ n - 1 ]; } };
```

### Python

```python
class Solution : def firstDayBeenInAllRooms ( self , nextVisit : List [ int ]) -> int : n = len ( nextVisit ) f = [ 0 ] * n mod = 10 ** 9 + 7 for i in range ( 1 , n ): f [ i ] = ( f [ i - 1 ] + 1 + f [ i - 1 ] - f [ nextVisit [ i - 1 ]] + 1 ) % mod return f [ - 1 ]
```