We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

First Day Where You Have Been in All the Rooms

Difficulty: Medium

Problem Description

Given n rooms labeled from 0 to n - 1, you must visit each room according to specific rules defined by an array nextVisit. Starting from day 0 in room 0, return the first day where you have visited all rooms, modulo 10^9 + 7.

Key Insights

  • The visiting pattern alternates based on whether the total visits to a room are odd or even.
  • The problem can be approached with a simulation of room visits while tracking the count of visits to each room.
  • A day is defined as the first instance where all rooms have been visited at least once.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves simulating the room visiting process:

  1. Maintain a counter for how many times each room has been visited.
  2. Use a variable to track the current room index based on the visit rules.
  3. Keep a set or an array to track visited rooms until all rooms have been visited.
  4. Iterate day by day, updating the room visit count and switching rooms based on the visit rules until all rooms have been visited.

Code Solutions

def firstDayWhereAllRoomsVisited(nextVisit):
    n = len(nextVisit)
    visit_count = [0] * n
    visited = [False] * n
    current_room = 0
    day = 0
    total_visited = 0

    while total_visited < n:
        visit_count[current_room] += 1
        if visit_count[current_room] == 1:
            total_visited += 1
            visited[current_room] = True
        
        if visit_count[current_room] % 2 == 1:
            current_room = nextVisit[current_room]
        else:
            current_room = (current_room + 1) % n
        
        day += 1
    
    return day % (10**9 + 7)
← Back to All Questions