# 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] == 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.)

**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 ！！**

```java
// 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**

```java
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%

```java
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%

```java
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

```java
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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/array/active-and-inactive-cells-after-k-days.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.