First day where you have been in all the rooms

Array Dynamic Programming

40.4% acceptance

Feb 25, 2026

510

104

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn first_day_been_in_all_rooms(next_visit: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = next_visit.len();
    // dp[i] = the day we first visit room i
    // When we first visit room i (odd visit), we go to nextVisit[i]
    // Then we need to revisit from nextVisit[i] to i again (which takes dp[i] - dp[nextVisit[i]] days)
    // Then we arrive at room i for the 2nd time (even), so we move to i+1
    // dp[i+1] = dp[i] + 1 + (dp[i] - dp[nextVisit[i]]) + 1
    //         = 2*dp[i] - dp[nextVisit[i]] + 2
    let mut dp = vec![0i64; n];
    for i in 0..n - 1 {
      let j = next_visit[i] as usize;
      dp[i + 1] = (2 * dp[i] - dp[j] + 2 + MOD) % MOD;
    }
    dp[n - 1] as i32
  }
}