Skip to main content
Talentd

Prison Cells After N Days - Solution & Explanation

MediumArrayHash TableMathBit Manipulation17 min readAsked at: Amazon
Practice this problem

Problem Statement

There are 8 prison cells in a row and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

  • If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
  • Otherwise, it becomes vacant.

Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.

You are given an integer array cells where cells[i] == 1 if the ith cell is occupied and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.

Return the state of the prison after n days (i.e., n such changes described above).

 

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], n = 1000000000
Output: [0,0,1,1,1,1,1,0]

 

Constraints:

  • cells.length == 8
  • cells[i] is either 0 or 1.
  • 1 <= n <= 109

Approach Overview

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.

Approach 1: Simulate Each Day

This approach involves simulating each day's changes directly. Given the constraints of the problem, this can be manageable for relatively small values of 'n'. We iterate over each day, applying the rules to determine the state of each cell. Importantly, the edge cells are always vacant as they lack two neighbors. By updating the state iteratively, we can reach the final configuration after 'n' days.

The C program defines a function nextDay to calculate the state of cells for the next day based on the current state using the rules provided. The prisonAfterNDays function uses this helper function to simulate day-by-day changes. The logic accommodates the cyclic nature of the problem by using n % 14 to optimize large iterations, where 14 is the length of the repeating cycle determined by observation and testing.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(1), as the complexity per cycle of states is fixed. During each cycle, we just iterate over the 8 states.
Space complexity: O(1), only a fixed array is used for state computation.

Try this approach in the editor →

Approach 2: Identify Cycle in States

This alternative approach builds on recognizing patterns within the transformations. Given only 8 cells and binary states, the maximum number of possible unique states is 27 = 128. Through simulation, we can identify that the pattern cycles or repeats after at most 14 days, reducing the need to simulate all given 'n' days. By finding cycles, one can compute the state that would correspond to the final day directly, drastically minimizing operations.

The C code leverages a direct approach to identify patterns using the findCycle method, where state sequences are preserved and revisited to determine recurring configurations. This understanding is then used to restrict operations to only necessary repetitions through precise cycle length determination.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(128), as we explore states to identify cycles, bounded by maximum unique states of 128.
Space complexity: O(128), accommodates tracking up to 128 states.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate Each Day

Time complexity: O(1), as the complexity per cycle of states is fixed. During each cycle, we just iterate over the 8 states.
Space complexity: O(1), only a fixed array is used for state computation.

Identify Cycle in States

Time complexity: O(128), as we explore states to identify cycles, bounded by maximum unique states of 128.
Space complexity: O(128), accommodates tracking up to 128 states.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Each DayO(N)O(1)Small N where direct simulation is sufficient and implementation simplicity matters
Identify Cycle in StatesO(min(N, cycle)) ≈ O(1)O(64)Large N (up to 1e9). Detect repeating states with hashing and skip cycles

Video Solution

Prison Cells After N Days | Leetcode #957 • Techdose • 14,381 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Prison Cells After N Days easy or hard?
The problem is rated Medium because the rules are simple but recognizing the repeating cycle is the main challenge. A brute-force simulation is straightforward, but the optimized cycle detection solution demonstrates stronger algorithmic insight.
Prison Cells After N Days Python/Java solution
Python and Java implementations usually simulate the next state using a loop from index 1 to 6 and check whether neighbors are equal. The optimized version stores each state in a hash map or set to detect cycles and uses modulo arithmetic to skip repeated days.
How to solve Prison Cells After N Days in O(1)?
Store each daily configuration in a hash map or set and stop when a state repeats. Because only 6 cells change, the number of possible states is limited. After detecting the cycle length, reduce N with modulo arithmetic (N % cycle_length) and simulate the remaining days. This keeps the runtime independent of large N values.
What is the best approach for Prison Cells After N Days?
The most efficient approach detects cycles in the cell states using a hash table. Since the first and last cells always become 0, only the 6 middle cells vary, giving at most 64 unique states. Once a repeating configuration appears, compute N % cycle_length and simulate only the remaining steps. This reduces the effective complexity to constant time.
Is Prison Cells After N Days asked at Google/Amazon/Meta?
Cycle detection and state simulation problems similar to this appear in interviews at companies like Amazon and Google. The problem tests array simulation, hashing, and recognizing repeating patterns in constrained state spaces.
What data structure is used in Prison Cells After N Days?
The solution primarily uses an array to represent the 8 prison cells and a hash table or hash set to store previously seen states. Some optimized implementations encode the array as a bitmask integer using bit manipulation for faster comparisons.
What is the time complexity of Prison Cells After N Days?
A naive simulation runs in O(N) time because you compute the next state for each day. The optimized solution uses cycle detection and runs in O(min(N, cycle_length)), where the cycle is at most 64 states. In practice this behaves like O(1) time with O(64) space.

Ready to solve this problem?

Practice Prison Cells After N Days with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays