Prison Cells After N Days: Cycle Detection in State Space

LeetCode 957. Prison Cells After N Days gives you a row of 8 prison cells, each either occupied (1) or vacant (0). Every day, each cell updates according to a simple rule: if a cell's two neighbors are both occupied or both vacant, the cell becomes occupied. Otherwise, it becomes vacant. The first and last cells have only one neighbor, so they always become 0 after the first day.

Given the initial state and a number N (which can be up to one billion), return the state of the cells after N days.

Why brute force fails

The naive approach is to simulate one day at a time, applying the update rule N times. Each step takes O(8) = O(1) work, so you might think the total cost is O(N). But N can be 10^9. Simulating a billion steps is far too slow, even at constant work per step.

You need a way to skip ahead.

The key insight: bounded state space

Here is the observation that unlocks this problem. The first and last cells are always 0 after day 1 (they lack two neighbors). That means only the 6 interior cells matter. Each interior cell is either 0 or 1, giving at most 2^6 = 64 possible states.

With 64 possible states and potentially billions of days, the pigeonhole principle guarantees a repeat. Once a state repeats, the sequence cycles. And once you know the cycle length, you can use modular arithmetic to jump directly to the answer.

This is the same core idea behind Happy Number: a bounded state space means cycle detection will always work.

The solution

def prisonAfterNDays(cells, n):
    seen = {}
    while n > 0:
        state = tuple(cells)
        if state in seen:
            n %= seen[state] - n
        seen[state] = n
        if n >= 1:
            cells = [0] + [1 if cells[i-1] == cells[i+1] else 0 for i in range(1, 7)] + [0]
            n -= 1
    return cells

The logic is compact, but there is a lot happening. Let's walk through it.

Step-by-step walkthrough

The algorithm has two phases. First, it simulates day by day while recording each state in a hash map. The map stores state -> remaining_days so we can compute the cycle length when a repeat is found. Second, when a repeated state appears, it computes n % cycle_length to reduce the remaining days. Then it continues simulating for just those few remaining steps.

How the cycle detection works

Each iteration of the while loop does the following:

1. Convert the current cells to a tuple (hashable form) and check if we have seen it before.
2. If yes, we found a cycle. The cycle length is seen[state] - n (the difference in remaining days between the first and second occurrence). We set n = n % cycle_length to skip full cycles.
3. Store state -> n in the seen dictionary.
4. If n is still at least 1, apply the update rule and decrement n.

The update rule itself is a one-liner: for each interior cell (indices 1 through 6), set it to 1 if both neighbors match and 0 otherwise. The first and last cells are always 0.

Complexity analysis

Both time and space are constant because the state space is bounded. No matter how large N is, the algorithm never simulates more than about 64 + 64 = 128 steps.

Building blocks

This problem combines two reusable patterns that appear throughout LeetCode.

1. Cycle detection with a hash map

Store each state you visit. When you see a repeat, you have found the cycle. This is the exact pattern from Happy Number and Linked List Cycle, applied to an array state instead of a single number or a linked list node.

seen = {}
while state not in seen:
    seen[state] = step
    state = next_state(state)
cycle_length = step - seen[state]

2. Modular arithmetic to skip repetition

Once you know a process repeats every k steps, the state after n steps is the same as the state after n % k steps. This is the same idea behind Rotate Array, where rotating by k positions in an array of length n is equivalent to rotating by k % n.

remaining = n % cycle_length

On CodeBricks, you drill each of these building blocks separately. When they show up combined in a problem like Prison Cells, you recognize both pieces immediately and wire them together without hesitation.

Edge cases

• N = 0: Return the original cells unchanged. No simulation needed.
• All cells the same: If all cells start as 0 or all as 1, the state still evolves (the first and last cells become 0 on day 1). The cycle detection handles this correctly.
• N = 1: Just apply one step of the update rule. The cycle detection logic still works, but the loop exits after a single iteration before any repeat is found.
• Very large N: N can be up to 10^9. The modular arithmetic reduction handles this in constant time after detecting the cycle.

From understanding to recall

Reading through this solution, the logic makes sense. Bounded state space forces a cycle. Modular arithmetic lets you skip the cycle. But reproducing this under interview pressure is a different challenge entirely.

The tricky part is not the idea. It is the bookkeeping: when to store the state, how to compute the cycle length from the stored values, and how to handle the off-by-one details around n >= 1 vs n > 0.

That is where spaced repetition helps. CodeBricks breaks this problem into its two building blocks (cycle detection with a hash map, modular arithmetic skip) and drills them at increasing intervals. After a few review cycles, the bookkeeping becomes automatic. You stop thinking about whether to check n >= 1 or n > 0 because your fingers already know.

Related posts

• Happy Number - Cycle detection in a bounded numeric sequence, the same pattern applied to digit-square chains
• Linked List Cycle - Floyd's tortoise and hare for cycle detection in linked lists, another face of the same underlying idea
• Rotate Array - Modular arithmetic to reduce a large step count, the same trick that makes Prison Cells efficient