957. Prison Cells After N Days

Posted on | Edited on | Views:

LeetCode

link

Using hashset to detect cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int[] prisonAfterNDays(int[] cells, int N) {
        if(cells==null || cells.length==0 || N<=0) return cells;
        boolean hasCycle = false;
        int cycle = 0;
        HashSet<String> set = new HashSet<>(); 
        for(int i=0;i<N;i++){
            int[] next = nextDay(cells);
            String key = Arrays.toString(next);
            if(!set.contains(key)){ //store cell state
                set.add(key);
                cycle++;
            }
            else{ //hit a cycle
                hasCycle = true;
                break;
            }
            cells = next;
        }
        if(hasCycle){
            N%=cycle;
            for(int i=0;i<N;i++){
                cells = nextDay(cells);
            }   
        }
        return cells;
    }
    
    private int[] nextDay(int[] cells){
        int[] tmp = new int[cells.length];
        for(int i=1;i<cells.length-1;i++){
            tmp[i]=cells[i-1]==cells[i+1]?1:0;
        }
        return tmp;
    }
}

Brute Force: Time Complexity: O(KN), Output Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
class Solution {
    public int[] prisonAfterNDays(int[] cells, int N) {
        for(int i=0;i<N;i++){
            int[] preCells=cells.clone();
            for(int j=0;j<cells.length;j++){
                if(j==0) cells[j]=0;
                else if(j==cells.length-1) cells[j]=0;
                else if((preCells[j-1]==1&&preCells[j+1]==1)||(preCells[j-1]==0&&preCells[j+1]==0)) cells[j]=1;
                else cells[j]=0;
            }
        }
        return cells;
    }
}*/

0%