1997. First Day Where You Have Been in All the Rooms LeetCode Solution
In this guide, you will get 1997. First Day Where You Have Been in All the Rooms LeetCode Solution with the best time and space complexity. The solution to First Day Where You Have Been in All the Rooms problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of First Day Where You Have Been in All the Rooms
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1997. First Day Where You Have Been in All the Rooms LeetCode Solution in C++
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();
}
}; /* code provided by PROGIEZ */
1997. First Day Where You Have Been in All the Rooms LeetCode Solution in Java
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];
}
} // code provided by PROGIEZ
1997. First Day Where You Have Been in All the Rooms LeetCode Solution in Python
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] # code by PROGIEZ
