Prison Cells After N Days

Given the prison rules and the constraints, we can note that the state of the cells will eventually repeat after some number of days, leading to a cycle. We can take advantage of this pattern to avoid simulating all ( n ) days, which could be up to ( 10^9 ). Here’s a step-by-step approach:

  1. Initialize: Create a list seen to store previously seen states of the cells.
  2. Simulate Until Repeat: Simulate the prison’s state for each day until a previously seen state is encountered.
  3. Detect the Cycle: Once a repeated state is found, calculate the cycle length and determine the remaining number of days to simulate by taking ( n \mod \text{{cycle length}} ).
  4. Simulate the Remainder: Simulate the remaining number of days, starting from the initial state.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        def next_day(cells):
            return [int(i > 0 and i < 7 and cells[i - 1] == cells[i + 1]) for i in range(8)]

        seen = {}

        while n > 0:
            state_tuple = tuple(cells)
            if state_tuple in seen:
                # Detected a cycle, calculate the remaining days to simulate
                n %= seen[state_tuple] - n
            seen[state_tuple] = n

            if n > 0:
                cells = next_day(cells)
                n -= 1

        return cells

This code first simulates the prison’s state until a cycle is detected and then simulates the remaining days. The time complexity is ( O(1) ) since there’s a limited number of possible states (up to 256), and the space complexity is also ( O(1) ).