First Day Where You Have Been in All the Rooms: DP with Modular Arithmetic

You are given n rooms numbered 0 to n-1. On day 0 you visit room 0. Each day, you follow a simple rule based on how many times you have visited the current room: if this is an odd-numbered visit (1st, 3rd, ...), you go to nextVisit[i] the next day (where nextVisit[i] is between 0 and i inclusive). If this is an even-numbered visit (2nd, 4th, ...), you go to room (i + 1) % n. Return the first day when you have visited all n rooms, mod 10^9 + 7.

This is LeetCode 1997: First Day Where You Have Been in All the Rooms, and it is a great exercise in deriving a non-obvious DP recurrence from simulation rules. The naive simulation would take far too long, so you need to find a formula that skips ahead.

Why this problem matters

This problem tests your ability to go from a simulation description to a closed-form DP recurrence. You cannot just simulate day by day because the answer can be astronomically large (hence the modular arithmetic). Instead, you need to observe the structure of the visits, figure out that rooms are always first-visited in order, and derive a formula for how many days it takes to advance from one room to the next.

It combines two important skills: recognizing patterns in recursive processes and working with modular arithmetic to handle huge numbers. Both of these show up frequently in contest-style and interview DP problems.

Understanding the movement rules

The movement rules create an interesting pattern. Let's trace through what happens:

1. When you first visit room i, that is visit #1 (odd). So you go to nextVisit[i], which is some room j where 0 <= j <= i. You always go backwards or stay in place.
2. After going back, you eventually revisit room i. That is visit #2 (even). Now you advance to room i + 1.

The key observation: you always first-visit rooms in order 0, 1, 2, ..., n-1. You can never reach room i + 1 for the first time until you have visited room i an even number of times. And since nextVisit[i] only sends you to rooms you have already visited, you are always retracing ground you have covered before.

This means the problem reduces to: how many days does it take to advance from room i-1 to room i? If we can figure that out for each room, we just sum them up.

Deriving the recurrence

Define dp[i] as the day you first visit room i. We know dp[0] = 0 because you start there on day 0.

After visiting room i-1 on day dp[i-1], here is what happens:

1. This is the first visit to room i-1 (odd visit). You go to nextVisit[i-1]. That takes 1 day.
2. You are now at room nextVisit[i-1], and you need to retrace all the way back to room i-1. How long does that take? You have already solved this exact sub-problem before. Getting from room nextVisit[i-1] to room i-1 takes dp[i-1] - dp[nextVisit[i-1]] days. This works because the visit counts for rooms nextVisit[i-1] through i-1 are all even at this point, so the sequence of visits repeats exactly.
3. Now you are back at room i-1 with an even visit count. You advance to room i. That takes 1 more day.

Putting it together:

dp[i] = dp[i-1] + 1 + (dp[i-1] - dp[nextVisit[i-1]]) + 1

Simplifying:

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

All values are computed mod 10^9 + 7 since the numbers grow extremely fast.

Clean Python solution

def firstDayBeenInAllRooms(nextVisit):
    MOD = 10**9 + 7
    n = len(nextVisit)
    dp = [0] * n

    for i in range(1, n):
        dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2) % MOD

    return dp[n - 1]

Step-by-step walkthrough

Let's trace the example nextVisit = [0, 0, 2] (3 rooms) day by day to verify our formula gives the right answer:

• Day 0: Visit room 0 (visit #1, odd). Go to nextVisit[0] = 0.
• Day 1: Visit room 0 (visit #2, even). Go to room 1.
• Day 2: Visit room 1 (visit #1, odd). Go to nextVisit[1] = 0.
• Day 3: Visit room 0 (visit #3, odd). Go to nextVisit[0] = 0.
• Day 4: Visit room 0 (visit #4, even). Go to room 1.
• Day 5: Visit room 1 (visit #2, even). Go to room 2.
• Day 6: Visit room 2. All rooms visited! Answer: 6.

Our formula gives dp[2] = 6, which matches.

Complexity analysis

We fill one DP array of length n with a single pass. Each entry takes O(1) to compute. The modular arithmetic operations (addition, subtraction, mod) are all constant time.

The building blocks

This problem is built on three core concepts:

• Linear DP: each state dp[i] depends on earlier states. The recurrence fills left to right, one entry at a time. Same skeleton as Climbing Stairs and House Robber.
• Modular arithmetic: the answer can be enormous, so all computations use mod 10^9 + 7. Note that in Python, the % operator handles negative numbers correctly (it always returns a non-negative result), but in languages like C++ or Java you need to add MOD before taking mod to avoid negative remainders.
• Simulation-to-formula conversion: rather than simulating each day, you observe the structure and derive a closed-form recurrence. This is a common technique in competitive programming problems where the naive simulation is too slow.

Edge cases

• n = 2 (minimal case): just two rooms. dp[1] = 2 * dp[0] - dp[nextVisit[0]] + 2 = 2. Always takes 2 days regardless of nextVisit[0] (which must be 0).
• nextVisit[i] = i for all i (go back to self): each room takes only 2 extra days to pass through. dp[i] = dp[i-1] + 2, giving dp[n-1] = 2 * (n - 1).
• nextVisit[i] = 0 for all i (always go back to start): the worst case pattern. You retrace from room 0 every time. The values grow exponentially, which is why modular arithmetic is essential.
• Large n requiring modular arithmetic: with n up to 10^5 and exponential growth, the raw day count would be astronomically large. Without the mod operation, you would overflow any integer type.

From understanding to recall

You have just worked through the derivation of a DP recurrence that turns a complex simulation into a simple linear formula. The key insight, that retracing from nextVisit[i-1] to i-1 takes dp[i-1] - dp[nextVisit[i-1]] days, is the kind of observation that feels obvious once you see it but is hard to come up with under pressure.

Spaced repetition helps bridge that gap. By revisiting this recurrence derivation at increasing intervals, the pattern of "simulation rule to DP formula" becomes something you can reach for automatically. You practice not just the final code (which is only 5 lines), but the reasoning process that leads to it.

Related posts

• Climbing Stairs - The foundational linear DP pattern, same structure of building each state from previous states
• Decode Ways - Another linear DP where the recurrence depends on looking back at previous states
• House Robber - Linear DP with a decision at each step, showing the same build-up-from-base pattern