First Day Where You Have Been in All the Rooms — Solution
First Day Where You Have Been in All the Rooms solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
First Day Where You Have Been in All the Rooms is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n rooms numbered 0 to n - 1, and you visit exactly one room per day, starting with room 0 on day 0. Which room you visit the next day follows a fixed rule, using the array nextVisit (with 0 <= nextVisit[i] <= i):
- If, counting today's visit, you have been in room
ian odd number of times, tomorrow you visit roomnextVisit[i]. - If you have been in room
ian even number of times, tomorrow you visit room(i + 1) mod n.
Return the label of the first day on which you have visited every room at least once. The answer can be huge, so return it modulo 10^9 + 7.
Example 1
Input: nextVisit = [0,0]
Output: 2
Explanation: Day 0: room 0 (1st visit, odd → room 0). Day 1: room 0 (2nd visit, even → room 1). Day 2: room 1 — every room seen.
Example 2
Input: nextVisit = [0,0,2]
Output: 6
Explanation: Rooms visited on days 0..6 are 0, 0, 1, 0, 0, 1, 2.
Example 3
Input: nextVisit = [0,1,2,0]
Output: 6
Explanation: Rooms visited on days 0..6 are 0, 0, 1, 1, 2, 2, 3.
Constraints
n == nextVisit.length2 <= n <= 10^50 <= nextVisit[i] <= i
Hints for First Day Where You Have Been in All the Rooms
Hint 1
You can only move forward from room
ito roomi + 1by visiting roomian even number of times. BecausenextVisit[i] <= i, you never reach roomi + 1before roomi.Hint 2
When you first enter room
i, every room before it has been visited an even number of times. After the odd visit, you jump back tonextVisit[i]— and from there it takes exactly as long to get back toias it took the first time fromnextVisit[i]toi.Hint 3
So with
dp[i]= first day in roomi:dp[i + 1] = dp[i] + 1 + (dp[i] - dp[nextVisit[i]]) + 1. Keep it modulo10^9 + 7(and keep it non-negative).
How to solve First Day Where You Have Been in All the Rooms
Let dp[i] be the first day you stand in room i. Reaching room i + 1 requires a second visit to room i, and the detour in between replays exactly the stretch from nextVisit[i] to i, which took dp[i] - dp[nextVisit[i]] days the first time.
Approach
dp[0] = 0.- For
i = 0..n-2:dp[i + 1] = 2 * dp[i] - dp[nextVisit[i]] + 2(modulo10^9 + 7, adding the modulus before the final reduction so the value stays non-negative). - Return
dp[n - 1].
Why it works
When you first arrive at room i, every room j < i has an even visit count — you left each of them forward, which only happens on even visits. Going back to nextVisit[i] = k puts you in the same position as your first arrival at k (all rooms from k on even), so the walk from k back to i repeats the original walk and takes dp[i] - dp[k] days. Counting the day spent jumping to k and the day stepping from i to i + 1 gives the recurrence.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Subtracting
dp[nextVisit[i]]under a modulus can go negative — add the modulus back. 2 * dp[i]reaches about 2·10^9 before the reduction, which overflows a 32-bit int; use 64-bit arithmetic.- The answer is the first day the last room is entered, which is
dp[n - 1]because rooms are always reached in order.
Reference solution
Python
from typing import List
def firstDayBeenInAllRooms(nextVisit: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(nextVisit)
dp = [0] * n
for i in range(n - 1):
dp[i + 1] = (2 * dp[i] - dp[nextVisit[i]] + 2) % MOD
return dp[n - 1]Java
public static int firstDayBeenInAllRooms(int[] nextVisit) {
final long MOD = 1000000007L;
int n = nextVisit.length;
long[] dp = new long[n];
for (int i = 0; i + 1 < n; i++) {
dp[i + 1] = ((2 * dp[i] - dp[nextVisit[i]] + 2) % MOD + MOD) % MOD;
}
return (int) dp[n - 1];
}C++
int firstDayBeenInAllRooms(vector<int>& nextVisit) {
const long long MOD = 1000000007LL;
int n = nextVisit.size();
vector<long long> dp(n, 0);
for (int i = 0; i + 1 < n; i++) {
dp[i + 1] = ((2 * dp[i] - dp[nextVisit[i]] + 2) % MOD + MOD) % MOD;
}
return (int)dp[n - 1];
}JavaScript
var firstDayBeenInAllRooms = function(nextVisit) {
var MOD = 1000000007, n = nextVisit.length, dp = new Array(n).fill(0);
for (var i = 0; i + 1 < n; i++) {
dp[i + 1] = ((2 * dp[i] - dp[nextVisit[i]] + 2) % MOD + MOD) % MOD;
}
return dp[n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming