Skip to content

1997. First Day Where You Have Been in All the Rooms 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int firstDayBeenInAllRooms(vector<int>& nextVisit) {
    constexpr int kMod = 1'000'000'007;
    const int n = nextVisit.size();
    // dp[i] := the number of days to visit room i for the first time
    vector<int> dp(n);

    // Whenever we visit i, visit times of room[0..i - 1] are all even.
    // Therefore, the rooms before i can be seen as reset and we can safely
    // reuse dp[0..i - 1] as first-time visit to get second-time visit.
    for (int i = 1; i < n; ++i)
      // The total days to visit room[i] is the sum of
      //   * dp[i - 1]: 1st-time visit room[i - 1]
      //   * 1: visit room[nextVisit[i - 1]]
      //   * dp[i - 1] - dp[nextVisit[i - 1]]: 2-time visit room[i - 1]
      //   * 1: visit room[i]
      dp[i] = (2L * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + kMod) % kMod;

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int firstDayBeenInAllRooms(int[] nextVisit) {
    final int kMod = 1_000_000_007;
    final int n = nextVisit.length;
    // dp[i] := the number of days to visit room i for the first time
    int[] dp = new int[n];

    // Whenever we visit i, visit times of room[0..i - 1] are all even.
    // Therefore, the rooms before i can be seen as reset and we can safely
    // reuse dp[0..i - 1] as first-time visit to get second-time visit.
    for (int i = 1; i < n; ++i)
      // The total days to visit room[i] is the sum of
      //   * dp[i - 1]: 1st-time visit room[i - 1]
      //   * 1: visit room[nextVisit[i - 1]]
      //   * dp[i - 1] - dp[nextVisit[i - 1]]: 2-time visit room[i - 1]
      //   * 1: visit room[i]
      dp[i] = (int) ((2L * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + kMod) % kMod);

    return dp[n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
    kMod = 1_000_000_007
    n = len(nextVisit)
    # dp[i] := the number of days to visit room i for the first time
    dp = [0] * n

    # Whenever we visit i, visit times of room[0..i - 1] are all even.
    # Therefore, the rooms before i can be seen as reset and we can safely
    # reuse dp[0..i - 1] as first-time visit to get second-time visit.
    for i in range(1, n):
      # The total days to visit room[i] is the sum of
      #   * dp[i - 1]: 1st-time visit room[i - 1]
      #   * 1: visit room[nextVisit[i - 1]]
      #   * dp[i - 1] - dp[nextVisit[i - 1]]: 2-time visit room[i - 1]
      #   * 1: visit room[i]
      dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2) % kMod

    return dp[-1]