957. Prison Cells After N Days

There are two key observations to make here

1> The transformations form a cycle.

2>The original array that is passed in, is not a part of that cycle.

Here's a generalizable way to approach this problem w/o having to have a ton of insight:

• there are 8 cells so there are 2 ^ 8 = 256 possible cell configurations

• therefore, after 256 transformations you are guaranteed to observe a cycle by the pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

In the future when you see questions where you have to make a large amount of state transitions over a state space that seems small, just compare the size of the state space to the # of transitions to determine if there's a cycle so you can bound complexity to the size of the state space.

[1,0,0,1,0,0,1,0] => original
[0, 0, 0, 1, 0, 0, 1, 0] => next
[0, 1, 0, 1, 0, 0, 1, 0]
[0, 1, 1, 1, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 1, 0, 1, 0]
[0, 0, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 1, 1, 1, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 1, 0]
[0, 1, 0, 0, 1, 1, 1, 0]
[0, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 0]
[0, 1, 1, 1, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 1, 0] => cycle!

cycle = 14

T: O(n)

S: O(n)

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        
        int cycle = 0;
        boolean hasCycle = false;
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            int[] next = helper(cells);
            String cellStr = Arrays.toString(next);
            
            if (!set.contains(cellStr)) {
                set.add(cellStr);
                cycle++;
            } else {
                hasCycle = true;
                break;
            }
            cells = next;
        }
        
        if (hasCycle) {
            n %= cycle;
            for (int i = 0; i < n; i++) {
                cells = helper(cells);
            }
        }
        // every time has a new array
        return cells;
    }
    private int[] helper(int[] cells) {
        int[] newCell = new int[cells.length];
        newCell[0] = 0;
        newCell[cells.length-1] = 0;
        for (int i = 1; i < cells.length - 1; i++) {
            if (cells[i-1] == cells[i+1]) {
                newCell[i] = 1;
            } else {
                newCell[i] = 0;
            }
        }
        return newCell;
    }
}

/*
[0, 1, 0, 1, 1, 0, 0, 1]
[      ]
    [      ]
       [      ]
          [      ]
             [      ]
                [      ]
                
                
[0, 1, 0, 1, 1, 0, 0, 1]
[0, 1, 0, 1, 1, 0, 0, 1]
*/