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 thefirst 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 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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

1
2
3
4
5

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 <= 10^5
  • 0 <= nextVisit[i] <= i

Solution

Method 1 – Dynamic Programming

Intuition

We use dynamic programming to track the first day we visit all rooms up to i. For each room, the answer depends on the answer for the previous room and the nextVisit rule.

Approach

  1. Let dp[i] be the first day all rooms 0..i have been visited.
  2. Base case: dp[0] = 0 (room 0 is visited on day 0).
  3. For i > 0:
    • To visit room i for the first time, we must have visited all rooms up to i-1.
    • After visiting all up to i-1, we go to room i on day dp[i-1] + 1.
    • But after visiting i, we must return to nextVisit[i] (if odd times), and only after an even number of visits to i do we move to i+1.
    • So, dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2) % MOD.
  4. Return dp[n-1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size(), MOD = 1e9+7;
        vector<long long> dp(n);
        for (int i = 1; i < n; ++i) {
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD;
        }
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8

func firstDayBeenInAllRooms(nextVisit []int) int {
    n, MOD := len(nextVisit), int(1e9+7)
    dp := make([]int, n)
    for i := 1; i < n; i++ {
        dp[i] = (2*dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD
    }
    return dp[n-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.length, MOD = 1_000_000_007;
        long[] dp = new long[n];
        for (int i = 1; i < n; i++) {
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD;
        }
        return (int)dp[n-1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun firstDayBeenInAllRooms(nextVisit: IntArray): Int {
        val n = nextVisit.size
        val MOD = 1_000_000_007
        val dp = LongArray(n)
        for (i in 1 until n) {
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD
        }
        return dp[n-1].toInt()
    }
}
1
2
3
4
5
6
7

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: list[int]) -> int:
        n, MOD = len(nextVisit), 10**9+7
        dp = [0] * n
        for i in range(1, n):
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2) % MOD
        return dp[-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn first_day_been_in_all_rooms(next_visit: Vec<i32>) -> i32 {
        let n = next_visit.len();
        let mut dp = vec![0i64; n];
        let m = 1_000_000_007i64;
        for i in 1..n {
            dp[i] = (2 * dp[i-1] - dp[next_visit[i] as usize] + 2 + m) % m;
        }
        dp[n-1] as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    firstDayBeenInAllRooms(nextVisit: number[]): number {
        const n = nextVisit.length, MOD = 1e9+7;
        const dp = new Array(n).fill(0);
        for (let i = 1; i < n; i++) {
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD;
        }
        return dp[n-1];
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we fill the dp array once.
  • 🧺 Space complexity: O(n), for the dp array.