Scale Engineer

Prison Cells After N Days

Med
#0911Time: 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.
Patterns
MathBit Manipulation
Data structures
ArrayHash Table

Prompt

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

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 n times, representing n days.
  • Inside the loop, create a temporary array nextCells of size 8 to hold the state of the cells for the next day.
  • The first and last cells, nextCells[0] and nextCells[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 the currentCells array: nextCells[j] = (currentCells[j-1] == currentCells[j+1]) ? 1 : 0;.
  • After computing all the states for the next day, update currentCells to be nextCells.
  • After the main loop of n iterations completes, currentCells will 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.

Solutions

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);  }}

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.

← Previous

Previous problem

Next →

Next problem