First Day Where You Have Been in All the Rooms

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

Understanding the Visualization

Input

Array nextVisit defines where to go after odd visits

Rules

Odd visits → go to nextVisit[i], Even visits → go to next room

Output

First day when all rooms have been visited

Key Takeaway

🎯 Key Insight: Each room requires exactly two visits before advancing to the next room

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

Approach	Time	Space	Notes
✓ Simulation Approach	O(2ⁿ)	O(n)	Simulate day by day until all rooms are visited
Dynamic Programming	O(n)	O(n)	Calculate minimum days using DP to avoid simulation

Simulation Approach — Algorithm Steps

Track visit count for each room
Simulate each day following the rules
Stop when all rooms visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start at room 0 on day 0

Follow Rules

Visit rooms based on odd/even visit counts

Track Progress

Continue until all rooms visited

Code -

solution.c — C

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

int solution(int* nextVisit, int n) {
    const int MOD = 1000000007;
    int* visitCount = calloc(n, sizeof(int));
    bool* visited = calloc(n, sizeof(bool));
    int currentRoom = 0;
    long long day = 0;
    
    while (true) {
        visitCount[currentRoom]++;
        visited[currentRoom] = true;
        
        bool allVisited = true;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                allVisited = false;
                break;
            }
        }
        if (allVisited) {
            free(visitCount);
            free(visited);
            return day % MOD;
        }
        
        if (visitCount[currentRoom] % 2 == 1) {  // odd visits
            currentRoom = nextVisit[currentRoom];
        } else {  // even visits
            currentRoom = (currentRoom + 1) % n;
        }
        
        day++;
        if (day > 1000000) {  // prevent infinite loop
            break;
        }
    }
    
    free(visitCount);
    free(visited);
    return 0;
}

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(2ⁿ)

In worst case, may need exponential days to visit all rooms

✓ Linear Growth

Space Complexity

O(n)

Arrays to track visit counts and visited rooms

⚡ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler