957. Prison Cells After N Days

Problem

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.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

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]

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Discussion

The problems requires us to update a list based on the current values (state) and a given logic rule, and evaluate the result after N iterations.

Let's start with the naive approach. Consider give integer N, we perform the list update logic for N time, we will have the result in O(n) time. Simple.

To escape from the O(n), our only hope is any looping pattern in this problem. Detecting this, we cache the result into a list / map, and check if the latest list exist in cache.

Solution

Our solution iterates towards N, performing update to the list in each iteration. And to search for repeat patterns, we cache the historical records for the rows in Hash Map, and search for the updated rows to see if duplication can be found.

Once we found a looping pattern, we can return the result from cache give days = (N - current day) % period + pattern start day.

Well but if there's no looping pattern, we are doomed with O(n) being the best time complexity.

from typing import List

class Solution:
    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
        i = 0
        cache = {
            ','.join(str(x) for x in cells): i
        }
        pre = cells

        while i < N:
            i += 1
            new = [0,0,0,0,0,0,0,0]

            for j in range(1,7):
                if pre[j - 1] == pre[j + 1]:
                    new[j] = 1

            if ','.join(str(x) for x in new) in cache:
                j = cache.get(','.join(str(x) for x in new))
                period = i - j
                for snap, day in cache.items():
                    if day == j + (N - i) % period:
                        return [int(x) for x in snap.split(',')]

            cache[','.join(str(x) for x in new)] = i
            pre = new

        return new

Complexity Analysis

• Time Complexity: O(k) if pattern with period k exists. Else O(n).
• Space Complexity: O(k) if pattern with period k exists. Else O(n).