O(n) constance space


  • 0
    D

    Calculate the number of each states base on previous result using a constant space rolling array

        private static final int BASE = 1000000007;
        public int checkRecord(int n) {
            int[][] tab = new int[2][3];
            int[][] sumOfP = new int[2][3];
            tab[0][0] = 1;
            int prev = 0;
            int curr = 1;
            for (int i = 1; i <= n; i++) {
                prev = (i-1) & 1;
                curr = i & 1;
                // curr0: end with P  -> PP + LP + LLP (prev0 + prev1 + prev2)
                // curr1: end with L  -> PL (prev0)
                // curr2: end with LL -> LL (prev1)
                //                    -> LLL (invalid)
                tab[curr][0] = ((tab[prev][0] + tab[prev][1]) % BASE + tab[prev][2]) % BASE;
                tab[curr][1] = tab[prev][0];
                tab[curr][2] = tab[prev][1];
                // calculate how many P's are there, since each P can be exchanged with an A and got a new valid sequence
                sumOfP[curr][0] = ((tab[curr][0] + sumOfP[prev][0]) % BASE + (sumOfP[prev][1] + sumOfP[prev][2]) % BASE) % BASE;
                sumOfP[curr][1] = sumOfP[prev][0];
                sumOfP[curr][2] = sumOfP[prev][1];
            }
            // calcualte the number of sequence with one 'A'
            int sum = ((sumOfP[curr][0] + sumOfP[curr][1]) % BASE + sumOfP[curr][2]) % BASE;
            
            return ((sum + tab[curr][0]) % BASE + (tab[curr][1] + tab[curr][2]) % BASE) % BASE;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.