Prison Cells After N Days

(Active and Inactive Cells After k Days)

Array

Medium

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] == 1if thei-th cell is occupied, elsecells[i] == 0.

Given the initial state of the prison, return the state of the prison afterNdays (andNsuch 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]

Note:

1. cells.length == 8

2. cells[i]is in {0, 1}

3. 1 <= N <= 10^9

Analysis & Solution

这个本身逻辑也就是状态转移很直白，但是挑战在于如何处理边界条件以及如何更优化时间（和空间）复杂度。

Brute-force Simulation

用prevVal记录上一个时间的左边cell的状态，nextVal记录上一个时间右边cell的状态，要注意的是nextVal在判断前就可以确定好，而prevVal要在判断完当前cell的更改方案后，再更新。

• Space: Extra Space: O(1) 不算返回答案所需的List

• Time: O(n * m), n - number of cells, m - days

但是，这种方法会TLE。

！！注意：下面的代码在LeetCode会Time Limit Exceeded ！！

// IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;
// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
// DEFINE ANY CLASS AND METHOD NEEDED
// CLASS BEGINS, THIS CLASS IS REQUIRED
public class Solution
{        
  // METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
    public List<Integer> cellCompete(int[] states, int days)
    {
    // WRITE YOUR CODE HERE
        if (states.length != 8 || days < 1) {
            return convertToList(states);
        }
        int n = states.length;

        int prevVal, nextVal;

        while (days-- > 0) {

            prevVal = 0;
            nextVal = 0;

            for (int i = 0; i < n; i++) {
                if (i < n - 1) {
                    nextVal = states[i + 1];
                } else if (i == n - 1) {
                    nextVal = 0;
                }

                if (nextVal == prevVal) {
                    prevVal = states[i];
                    states[i] = 0;
                } else {
                    prevVal = states[i];
                    states[i] = 1;
                }
            }
        }
        return convertToList(states);
    }
    private List<Integer> convertToList(int[] arr) {
        List<Integer> output = new LinkedList<Integer>();
        for (int a: arr) {
            output.add(a);
        }
        return output;
    }
  // METHOD SIGNATURE ENDS
}

这个也会TLE

class Solution {
    public int[] prisonAfterNDays(int[] cells, int days) {
        if (cells.length != 8 || days < 1) {
            return cells;
        }
        int n = cells.length;

        int prevVal, nextVal;

        while (days-- > 0) {

            prevVal = 0;
            nextVal = 0;

            for (int i = 0; i < n; i++) {
                if (i == 0 || i == n - 1) {
                    prevVal = cells[i];
                    cells[i] = 0;
                    continue;
                }
                if (i < n - 1) {
                    nextVal = cells[i + 1];
                } else if (i == n - 1) {
                    nextVal = 0;
                }

                if (nextVal == prevVal) {
                    prevVal = cells[i];
                    cells[i] = 1;
                } else {
                    prevVal = cells[i];
                    cells[i] = 0;
                }
            }
        }
        return cells;
    }
}

时间优化：找pattern

用signature作为hashmap的key记录当前的cells，找到循环之后直接days - period。

Time: O(n * m / k)

Space: O(n * k) - k 是循环周期，n是cells数，m是days

5069 ms, faster than 1.05%

class Solution {
    public int[] prisonAfterNDays(int[] cells, int days) {
        if (cells.length != 8 || days < 1) {
            return cells;
        }
        int n = cells.length;

        int prevVal, nextVal;
        HashMap<String, Integer> map = new HashMap();
        int period = -1;

        while (days > 0) {

            prevVal = 0;
            nextVal = 0;

            for (int i = 0; i < n; i++) {
                if (i == 0 || i == n - 1) {
                    prevVal = cells[i];
                    cells[i] = 0;
                    continue;
                }
                if (i < n - 1) {
                    nextVal = cells[i + 1];
                } else if (i == n - 1) {
                    nextVal = 0;
                }

                if (nextVal == prevVal) {
                    prevVal = cells[i];
                    cells[i] = 1;
                } else {
                    prevVal = cells[i];
                    cells[i] = 0;
                }
            }
            if (period < 0 ) {
                String signature = Arrays.toString(cells);
                if (map.containsKey(signature)) {
                    period = map.get(signature) - days;   
                    while (period > 0 && days - period > 0) {
                        days -= period;
                    }
                } else {
                    map.put(signature, days);
                }
            }
            days--;
        }
        return cells;
    }
}

时间优化才是重点，不做不必要的空间优化可以让代码更简洁：

而且空间本身也只有8个元素的数组，每次也只需要这么多，因此可以接受。

13 ms, faster than 60.41%; 37.6 MB, less than 100.00%

class Solution {
    public int[] prisonAfterNDays(int[] cells, int N) {
        Map<String, Integer> seen = new HashMap<>();
        while (N-- > 0) {
            int[] cells2 = new int[8];
            seen.put(Arrays.toString(cells), N);
            for (int i = 1; i < 7; ++i) {
                cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            }
            cells = cells2;
            if (seen.containsKey(Arrays.toString(cells))) {
                N %= seen.get(Arrays.toString(cells)) - N + 1;
            }
        }
        return cells;
    }
}

假设已经找到循环的Pattern周期为14之后，可以用如下方法：

因为重复从第15天开始，因此 N = (N - 1) % 14 + 1

public int[] prisonAfterNDays(int[] cells, int N) {
    for (N = (N - 1) % 14 + 1; N > 0; --N) {
        int[] cells2 = new int[8];
        for (int i = 1; i < 7; ++i)
            cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
        cells = cells2;
    }
    return cells;
}

Reference

https://www.knowsh.com/Notes/250480/Active-And-Inactive-Cells-After-K-Days

https://www.geeksforgeeks.org/active-inactive-cells-k-days/

https://leetcode.com/problems/prison-cells-after-n-days/discuss/205684/JavaPython-Find-the-Loop-or-Mod-14