First Day Where You Have Been in All the Rooms

Medium
1627.

First Day Where You Have Been in All the Rooms

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.

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 i an odd number of times, tomorrow you visit room nextVisit[i].
  • If you have been in room i an 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.length
  • 2 <= n <= 10^5
  • 0 <= nextVisit[i] <= i
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nextVisit
 * @return {number}
 */
var firstDayBeenInAllRooms = function(nextVisit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 i an odd number of times, tomorrow you visit room nextVisit[i].
  • If you have been in room i an 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.length
  • 2 <= n <= 10^5
  • 0 <= nextVisit[i] <= i

Hints for First Day Where You Have Been in All the Rooms

  1. Hint 1

    You can only move forward from room i to room i + 1 by visiting room i an even number of times. Because nextVisit[i] <= i, you never reach room i + 1 before room i.

  2. 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 to nextVisit[i] — and from there it takes exactly as long to get back to i as it took the first time from nextVisit[i] to i.

  3. Hint 3

    So with dp[i] = first day in room i: dp[i + 1] = dp[i] + 1 + (dp[i] - dp[nextVisit[i]]) + 1. Keep it modulo 10^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

  1. dp[0] = 0.
  2. For i = 0..n-2: dp[i + 1] = 2 * dp[i] - dp[nextVisit[i]] + 2 (modulo 10^9 + 7, adding the modulus before the final reduction so the value stays non-negative).
  3. 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