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:
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 == 8cells[i] is either 0 or 1.1 <= n <= 109Problem 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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| Identify Cycle in States | Time complexity: O(128), as we explore states to identify cycles, bounded by maximum unique states of 128. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Each Day | O(N) | O(1) | Small N where direct simulation is sufficient and implementation simplicity matters |
| Identify Cycle in States | O(min(N, cycle)) ≈ O(1) | O(64) | Large N (up to 1e9). Detect repeating states with hashing and skip cycles |
Prison Cells After N Days | Leetcode #957 • Techdose • 14,238 views views
Watch 9 more video solutions →Practice Prison Cells After N Days with our built-in code editor and test cases.
Practice on FleetCode