Prison Cells After N Days - Video Solutions

Problem Overview: You are given 8 prison cells arranged in a row where each cell is either occupied (1) or vacant (0). Every day the state changes: a cell becomes occupied if its two neighbors were both occupied or both empty the previous day; otherwise it becomes vacant. The first and last cells always become 0 because they have only one neighbor. Given an initial configuration and an integer N, compute the state after N days.

Approach 1: Simulate Each Day (Time: O(N * 8), Space: O(8))

The direct approach is to simulate the transformation day by day. For each day, create a new array and iterate through indices 1..6. A cell becomes 1 when cells[i-1] == cells[i+1], otherwise 0. The edge cells are always set to 0. Since there are only 8 cells, each day's computation takes constant time, so the total complexity is O(N). This approach is simple and useful when N is small, but it becomes impractical when N can reach values like 10^9.

Approach 2: Identify Cycle in States (Time: O(min(N, cycle)) ≈ O(1), Space: O(2^6))

The key observation is that the system eventually repeats. The first and last cells are always 0 after the first day, so only the 6 middle cells change. That means there are at most 2^6 = 64 possible states. If you store each configuration in a hash table, you can detect when a state repeats. Once a cycle is found, reduce N using N % cycle_length and simulate only the remaining days. This turns a potentially huge simulation into a small constant number of steps. Many implementations encode the state as a bitmask using bit manipulation, which makes transitions fast and compact. The grid itself is handled as an array, while the hash table tracks previously seen states.

Recommended for interviews: Start by describing the daily simulation to show you understand the rule transition. Then point out that only 6 cells vary, giving at most 64 possible states. Recognizing this repetition and applying cycle detection with a hash map is the expected optimized solution. Interviewers typically want the cycle insight because it handles extremely large N efficiently.