First Day Where You Have Been in All the Rooms - Problem

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 10^9 + 7.

Input & Output

Example 1 — Basic Two Rooms

$ Input: nextVisit = [0,0]

› Output: 2

💡 Note: Day 0: visit room 0 (1st time) → next: room 0. Day 1: visit room 0 (2nd time) → next: room 1. Day 2: visit room 1 (1st time) → all rooms visited, return 2

Example 2 — Three Rooms

$ Input: nextVisit = [0,0,2]

› Output: 6

💡 Note: Must visit room 0 and 1 multiple times before reaching room 2 for the first time on day 6

Example 3 — Single Room

$ Input: nextVisit = [0]

› Output: 0

💡 Note: Only one room, visited on day 0, so return 0

Constraints

1 ≤ nextVisit.length ≤ 10⁵
0 ≤ nextVisit[i] ≤ i

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12

The key insight is that each room must be visited exactly twice before progressing to the next room. The optimal dynamic programming approach calculates this mathematically using the recurrence dp[i] = 2*dp[i-1] - dp[nextVisit[i-1]] + 2. Time: O(n), Space: O(n)

Common Approaches

✓ Dynamic Programming

⏱️ Time: O(n) Space: O(n)

Use dynamic programming to calculate the number of days needed to first visit each room. Each room requires visiting the previous room twice before advancing.

Simulation Approach

⏱️ Time: O(2ⁿ) Space: O(n)

Follow the exact rules day by day, keeping track of visit counts for each room and which rooms have been visited. Continue until all rooms are covered.

Dynamic Programming — Algorithm Steps

Define dp[i] = days to first visit room i
Calculate based on pattern: visit room i-1 twice
Sum the transitions efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Case

dp[0] = 0 (start at room 0)

Recurrence

dp[i] = 2*dp[i-1] - dp[nextVisit[i-1]] + 2

Result

dp[n-1] gives first day all rooms visited

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nextVisit, int n) {
    const int MOD = 1000000007;
    
    // dp[i] = number of days to first visit room i
    long long* dp = calloc(n, sizeof(long long));
    
    for (int i = 1; i < n; i++) {
        // To visit room i for the first time:
        // 1. First visit room i-1: dp[i-1] days
        // 2. Go back according to nextVisit[i-1]
        // 3. Visit room i-1 again: (dp[i-1] - dp[nextVisit[i-1]]) days
        // 4. Finally move to room i: 1 more day
        dp[i] = (2 * dp[i-1] - dp[nextVisit[i-1]] + 2 + MOD) % MOD;
    }
    
    int result = dp[n-1];
    free(dp);
    return result;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nextVisit[100];
    int n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nextVisit[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    printf("%d\n", solution(nextVisit, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through rooms calculating DP values

✓ Linear Growth

Space Complexity

O(n)

DP array to store days for each room

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

First Day Where You Have Been in All the Rooms - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler