Prison Cells After N Days
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the day-by-day changes of the prison cells for n days. It follows the rules given in the problem description in a straightforward manner without any optimizations.
Algorithm
- Create a loop that iterates
ntimes, representingndays. - Inside the loop, create a temporary array
nextCellsof size 8 to hold the state of the cells for the next day. - The first and last cells,
nextCells[0]andnextCells[7], are always set to 0 because they cannot have two adjacent neighbors. - Iterate through the inner cells from index 1 to 6.
- For each cell
j, calculate its next state based on its neighbors in thecurrentCellsarray:nextCells[j] = (currentCells[j-1] == currentCells[j+1]) ? 1 : 0;. - After computing all the states for the next day, update
currentCellsto benextCells. - After the main loop of
niterations completes,currentCellswill hold the final state of the prison.
Walkthrough
We iterate from day 1 to day n. In each iteration, we compute the state of the cells for the next day based on the current day's state. A temporary array, say nextCells, is used to store the new state to avoid modifying the current state while it's still being used for calculation. The rules are applied for each cell from index 1 to 6: nextCells[i] becomes 1 if cells[i-1] and cells[i+1] are the same, and 0 otherwise. The first and last cells (cells[0] and cells[7]) always become 0 as they don't have two neighbors. After calculating all the cells for the next day, the cells array is updated with the nextCells array. This process is repeated n times.
class Solution { public int[] prisonAfterNDays(int[] cells, int n) { if (n == 0) { return cells; } int[] currentCells = cells; for (int i = 0; i < n; i++) { int[] nextCells = new int[8]; // First and last cells become 0 for (int j = 1; j < 7; j++) { if (currentCells[j - 1] == currentCells[j + 1]) { nextCells[j] = 1; } else { nextCells[j] = 0; } } currentCells = nextCells; } return currentCells; }}Complexity
Time
O(N * L), where N is the number of days and L is the number of cells. Since L is a constant (8), the time complexity is effectively O(N). Given that N can be as large as 10^9, this approach is too slow.
Space
O(L), where L is the number of cells. Since L is fixed at 8, the space complexity is O(1). This space is used for the temporary array to store the next state.
Trade-offs
Pros
Simple to understand and implement.
Works correctly for small values of
n.
Cons
Highly inefficient for large values of
n.Will result in a 'Time Limit Exceeded' (TLE) error on most platforms given the constraint
n <= 10^9.
The number of possible states for the prison cells is finite. Since the length of the array is fixed at 8, there are at most 2^8 = 256 possible states. This means the sequence of states must eventually repeat, forming a cycle. By detecting this cycle, we can mathematically determine the final state without simulating all n days, making the solution efficient for a large n.
Algorithm
- Initialize a
HashMap<String, Integer>to store a mapping from a cell state (as a String) to the day number it was first seen. - Start a loop to simulate day by day, from day
i = 0up ton-1. - In each iteration,
cellsrepresents the state at dayi. Convert thecellsarray to a stringkey. - Check if
keyalready exists in the map.- If it does, a cycle is detected. Let the first time this state appeared be
firstOccurrenceDay. The length of the cycle iscycleLength = i - firstOccurrenceDay. - The number of remaining days to simulate is
remainingDays = n - i. - We only need to perform
remainingDays % cycleLengthmore state transitions. - Perform these remaining transitions and return the final state.
- If it does, a cycle is detected. Let the first time this state appeared be
- If
keyis not in the map, store the current state and day:map.put(key, i). - Calculate the next state of
cellsfor dayi+1. - If the loop finishes without finding a cycle (because
nwas small), the finalcellsarray is the answer.
Walkthrough
The core idea is to simulate day by day while keeping track of the states we have already seen. A HashMap is perfect for this, mapping a state (represented as a string) to the day number on which it occurred.
We start the simulation. On each day i, we have the state S_i. We check if we have seen this state before. If we encounter a state S_i that's already in our map, say it first appeared on day k (i.e., S_i == S_k), we have found a cycle. The length of this cycle is L = i - k. We need to find the state after n days, S_n. We have already simulated i days. The number of remaining days is n - i. The final state will be the one that occurs after (n - i) % L steps into the cycle. We can then simulate these few remaining steps and return the result.
This approach avoids the TLE error because the number of unique states is small (at most 256), so a cycle is guaranteed to be found very quickly. The total number of simulations will be a small constant value, regardless of how large n is.
import java.util.Arrays;import java.util.HashMap;import java.util.Map; class Solution { public int[] prisonAfterNDays(int[] cells, int n) { Map<String, Integer> seen = new HashMap<>(); for (int i = 0; i < n; i++) { String key = Arrays.toString(cells); if (seen.containsKey(key)) { int firstOccurrenceDay = seen.get(key); int cycleLength = i - firstOccurrenceDay; int remainingDays = n - i; int stepsToSimulate = remainingDays % cycleLength; for (int j = 0; j < stepsToSimulate; j++) { cells = getNextState(cells); } return cells; } seen.put(key, i); cells = getNextState(cells); } return cells; } private int[] getNextState(int[] cells) { int[] nextCells = new int[8]; for (int i = 1; i < 7; i++) { if (cells[i - 1] == cells[i + 1]) { nextCells[i] = 1; } } return nextCells; }}Complexity
Time
O(K * L), where K is the number of unique states and L is the number of cells. A cycle must be detected within K steps. Since K and L are constants, the time complexity is O(1).
Space
O(K * L), where K is the number of unique states and L is the number of cells. Since K is at most 2^8=256 and L=8, both are constants. Therefore, the space complexity is O(1).
Trade-offs
Pros
Extremely efficient and handles very large
n.Correctly models the problem as a finite state machine with cycles.
Guaranteed to be fast because the number of states is constant and small.
Cons
Slightly more complex to implement due to the cycle detection logic and state management with a map.
Solutions
Solution
class Solution {public int[] prisonAfterNDays(int[] cells, int N) { Map<String, Integer> stateDayMap = new HashMap<String, Integer>(); Map<Integer, int[]> dayStateMap = new HashMap<Integer, int[]>(); int[] prevCells = new int[8]; System.arraycopy(cells, 0, prevCells, 0, 8); int days = 0; int cycle = 0; while (days < N) { days++; int[] change = new int[8]; change[0] = 0; change[7] = 0; for (int i = 1; i < 7; i++) { if (prevCells[i - 1] == prevCells[i + 1]) change[i] = 1; } for (int i = 0; i < 8; i++) prevCells[i] = change[i]; String arrayStr = Arrays.toString(change); if (stateDayMap.containsKey(arrayStr)) { int prevDay = stateDayMap.get(arrayStr); cycle = days - prevDay; break; } else { stateDayMap.put(arrayStr, days); dayStateMap.put(days, change); } } if (days == N) return prevCells; int remainder = N % cycle; if (remainder == 0) remainder = cycle; return dayStateMap.get(remainder); }}class Solution (object): def prisonAfterNDays(self, oldcells, N): """ :type cells: List[int] :type N: int :rtype: List[int] """ cells = copy . deepcopy(oldcells) count = 0 N %= 14 if N == 0: N = 14 while count < N: newCell = [0] * 8 for i in range(1, 7): if cells[i - 1] == cells[i + 1]: newCell[i] = 1 else: newCell[i] = 0 cells = newCell count += 1 return cells// OJ: https://leetcode.com/problems/prison-cells-after-n-days/ // Time: O(1) // Space: O(1) class Solution { char next ( char c ) { char ans = 0 ; for ( int i = 1 ; i < 7 ; ++ i ) ans |= (( c >> ( i - 1 ) & 1 ) == ( c >> ( i + 1 ) & 1 )) << i ; return ans ; } public: vector < int > prisonAfterNDays ( vector < int >& A , int N ) { char c = 0 ; for ( int i = 0 ; i < 8 ; ++ i ) c |= A [ i ] << i ; vector < char > v { c }; unordered_map < char , int > m { { c , 0 } }; for ( int i = 1 ; i <= N ; ++ i ) { c = next ( c ); if ( m . count ( c )) { int d = i - m [ c ]; c = v [( N - i ) % d + m [ c ]]; break ; } v . push_back ( c ); m [ c ] = i ; } vector < int > ans ( 8 ); for ( int i = 0 ; i < 8 ; ++ i ) ans [ i ] = ( c >> i ) & 1 ; return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.