Prison Cells After N Days

Prison Cells After N Days

What is this problem about?

The Prison Cells After N Days problem gives you 8 prison cells (occupied or not) that evolve each day: a cell becomes occupied if both neighbors match, otherwise vacant. Find the cell state after N days. This coding problem detects cycles in state evolution to avoid iterating N times (N can be up to 10^9). The array, math, hash table, and bit manipulation interview pattern is the core.

Why is this asked in interviews?

Amazon asks this because the naive simulation is O(N) which TLEs for large N. The key insight: with 8 cells (256 possible states), the sequence must cycle within 256 steps. Detecting the cycle and jumping to N mod cycle_length is the critical optimization.

Algorithmic pattern used

Cycle detection + modular simulation. Simulate one day at a time: new[i] = 1 if cells[i-1] == cells[i+1] else 0 (cells[0] and cells[7] always become 0). After first step (since endpoints always become 0), store states in a hash map. When a repeated state is seen, compute remaining = (N - cycle_start) % cycle_length. Continue simulating remaining more steps.

Example explanation

cells=[0,1,0,1,1,0,0,1], N=7. Step 1: [0,1,1,0,0,0,0,0]. Continue simulating. States cycle after at most 14 steps for 6-active-cell states. After 7 steps: [0,0,1,1,0,0,0,0].

For N=10^9: detect cycle at step k, N mod cycle_length remaining steps.

Common mistakes candidates make

• Not detecting the cycle (O(N) simulation TLEs).
• Off-by-one: the first transformation step uses the initial state.
• Forgetting that cells[0] and cells[7] (endpoints) always become 0.
• Not handling N=0 (return original cells).

Interview preparation tip

Prison Cells After N Days is a cycle detection problem disguised as a simulation. Any finite-state system must eventually cycle — the cycle length is at most 2^6 = 64 for 6 active interior cells (since endpoints are always 0 after day 1). Always simulate the first step separately, then apply cycle detection. Practice similar "find state after N transformations" problems — they all use cycle detection with hash maps.