We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Prison Cells After N Days

Difficulty: Medium

Problem Description

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.

You are given an integer array cells where cells[i] == 1 if the i-th cell is occupied and cells[i] == 0 if the i-th cell is vacant, and you are given an integer n. Return the state of the prison after n days.

Key Insights

  • The prison cells evolve based on the state of their immediate neighbors.
  • The first and last cells do not have two neighbors, which influences their state changes.
  • The pattern of cell states can repeat after a certain number of days, allowing for optimization when n is very large.

Space and Time Complexity

Time Complexity: O(n) for simulating each day, but can be optimized to O(1) if patterns are recognized. Space Complexity: O(1) since we only need a few variables to keep track of the states.

Solution

The solution involves simulating the changes in the prison cell states according to the provided rules. For each day, we create a new state of cells based on the current state. To optimize for large values of n, we can use a hash map to store previously encountered states, allowing us to detect cycles and reduce the number of iterations needed.

Code Solutions

def prisonAfterNDays(cells, n):
    seen = {}
    while n > 0:
        state = tuple(cells)
        if state in seen:
            n %= seen[state] - n
        seen[state] = n
        if n == 0:
            break
        n -= 1
        new_cells = [0] * 8
        for i in range(1, 7):
            new_cells[i] = 1 if cells[i-1] == cells[i+1] else 0
        cells = new_cells
    return cells
← Back to All Questions