Prison Cells After N Days - Video Solutions
Prison Cells After N Days | Leetcode #957
Prison Cells After N Days - Video Solution
Watch 10 video solutions for Prison Cells After N Days, a medium level problem involving Array, Hash Table, Math. This walkthrough by Techdose has 14,381 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 == 8cells[i]is either0or1.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.
Complexity Analysis
| 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 |