Skip to content

Practice First Day Where You Have Been in All the Rooms

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#1997
LeetCode Problem

First Day Where You Have Been in All the Rooms

Problem Statement

Rooms are numbered 0 through nextVisit.length - 1. Visit room 0 on day 0 and one room each day. After visiting room i, count all visits to i including the current one: if the count is odd, visit nextVisit[i] the next day; if even, visit (i + 1) modulo the room count. Return the first day by which every room has been visited, modulo 10^9 + 7.

Source: First Day Where You Have Been in All the Rooms on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nextVisit = [0,0]
Output
2
Explanation

The sequence of rooms on days 0, 1 and 2 is [0, 0, 1]. The first visit to room 0 has odd count, so the next day returns to nextVisit[0], which is 0. The second visit has even count, allowing the move to room 1 on day 2. Both rooms have now been visited. Days are zero-indexed: three visits here mean the answer is day 2, not 3.

# Example 2

Input
nextVisit = [0,0,2]
Output
6
Explanation

The visits on days 0 through 6 are [0, 0, 1, 0, 0, 1, 2]. On the first visit to room 1, nextVisit[1] sends the route back to room 0. The route must revisit room 0 twice before reaching room 1 for its second visit; only then can it advance to room 2. Counting visits per room, rather than just tracking whether a room was seen, explains why the first complete day is 6.

# Example 3

Input
nextVisit = [0,1,2,0]
Output
6
Explanation

The visits on days 0 through 6 are [0, 0, 1, 1, 2, 2, 3]. Rooms 0, 1 and 2 each point back to themselves on their first, odd-numbered visit. Their second visit advances to the next room, so each new room takes two days to reach. Room 3 is first reached on day 6, completing the set. Its own nextVisit value affects later movement, not this first-completion answer.

Constraints

n == nextVisit.length
2 <= n <= 10^5
0 <= nextVisit[i] <= i

How to solve First Day Where You Have Been in All the Rooms

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Rooms are first reached in increasing order, and when you first reach room i every earlier room has been visited an even number of times, so the detour forced by the odd visit replays exactly the stretch from the first visit of nextVisit[i] back to the first visit of i; that gives a recurrence over first-visit days alone.

Why brute force is not enough

Simulating day by day is correct, but the number of days grows roughly like 2^n in the worst case, which for n up to 10^5 is astronomically large; that is also why the answer is requested modulo 10^9 + 7.

Approach

  1. Let first[i] be the day room i is first visited; first[0] is 0, and the answer is first[n - 1] because rooms are discovered in index order.
  2. On day first[i] you arrive at room i with an odd count, so the next day you move to room j = nextVisit[i], which is at most i.
  3. At that moment the visit parities of rooms j through i - 1 are all even, exactly as they were on day first[j], so returning to room i takes the same first[i] - first[j] days it originally took.
  4. Back at room i the count is even, so one more day reaches room i + 1; hence first[i + 1] = first[i] + 1 + (first[i] - first[j]) + 1 = 2 * first[i] - first[j] + 2.
  5. Compute left to right under the modulus, adding the modulus before reducing so the subtraction never goes negative.

Walkthrough of Example 2

nextVisit = [0,0,2] → 6

  1. first[0] = 0.
  2. Room 0 points to itself: first[1] = 2 * 0 - first[0] + 2 = 2; indeed days 0 and 1 are spent in room 0 and day 2 reaches room 1.
  3. Room 1 points to room 0: first[2] = 2 * 2 - first[0] + 2 = 6; the detour on days 3 and 4 revisits room 0 twice, day 5 returns to room 1 with an even count, and day 6 reaches room 2.
  4. All three rooms have been visited by day 6, so the answer is 6.

Time and space

Time O(n) · Space O(n). n is the number of rooms; each first-visit day is derived in constant time from two earlier entries, and the array of first-visit days must be kept because nextVisit can point arbitrarily far back.

Interview pitfalls

  • Letting 2 * first[i] - first[j] go negative after modular reduction; add the modulus before taking the remainder.
  • Returning the number of days rather than the zero-based day index; the answer for [0,0] is 2, not 3.
  • Attempting to track per-room parity in a simulation instead of trusting the parity invariant.
  • Overflowing 32-bit arithmetic when doubling a value near 10^9.
  • Missing that the constraint nextVisit[i] <= i is what makes the replay argument valid; a forward pointer would break it.

Follow-up questions interviewers ask

  • What if nextVisit[i] could exceed i, and exactly why does the replay argument fail?
  • How would you compute the first day a given room is visited for the second time?
  • Without the modulus, how large does the answer get for a chain where every room points back to room 0?

Further reading on the technique: Dynamic programming

Related LeetCode Problems

Practice more problems similar to First Day Where You Have Been in All the Rooms.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.