Accepted Java O(n^2) O(1) space solution


  • 0
    A
    public class Solution {
        
        private int[] iLoc = {-1,0,1};
        private int[] jLoc = {-1,0,1};
        
        public void gameOfLife(int[][] board) {
            if ( (board == null) || (board.length==0) || (board[0].length==0) ) {
                return;
            }
            
            for (int i=0;i<board.length;i++) {
                for (int j=0;j<board[i].length;j++) {
                    
                    int livingNb = getCount(board, i, j, 1);
    
                    int currVal = board[i][j];
                    
                    if (currVal == 1) {
                        if (livingNb < 2) {
                            board[i][j] = getNewVal(1, 0); // dies
                        }
                        else if ( (livingNb >=2) && (livingNb<=3) ) {
                            board[i][j] = getNewVal(1, 1); // continues
                        }
                        else if (livingNb>3) {
                            board[i][j] = getNewVal(1, 0); // dies
                        }
                    }
                    else if (currVal == 0) {
                        if (livingNb == 3) {
                            board[i][j] = getNewVal(0, 1); // lives
                        }
                    }
                }
            }
            
            // persist the future val.
            for (int i=0;i<board.length;i++) {
                for (int j=0;j<board[i].length;j++) {
                    board[i][j] = getFutureVal(board[i][j]);
                }
            }
        }
        
        private Integer getFutureVal(int val) {
            switch(val) {
                case 2: return 1;
                case 3: return 0;
                default: return val;
            }
        } 
        
        private Integer getNewVal(int val, int futureVal) {
            if ( (val == 0) && (futureVal == 1) ) {
                return 2;
            }
            else if ( (val == 1) && (futureVal == 0) ) {
                return 3;
            }
    
            return val;
        } 
        
        private Integer getCount(int[][] board, int i, int j, int value) {
            int c = 0;
            
            for (int a=0;a<iLoc.length;a++) {
                for (int b=0;b<jLoc.length;b++) {
                    int cI = i + iLoc[a];
                    int cJ = j + jLoc[b];
                    
                    if ( (cI == i) && (cJ == j) ) {
                        continue;
                    }
                    
                    if (isValid(cI, cJ, board)) {
                        int orgVal = getOrgVal(board[cI][cJ]);
                        if (orgVal == value) {
                            c++;
                        }
                    }
                }
            }
            
            return c;
        }
        
        private boolean isValid(int i, int j, int[][] board) {
            if ( (i<0) || (j<0) || (i>=board.length) || (j>=board[0].length) ) {
                return false;
            }
            
            return true;
        }
        
        private int getOrgVal(int value) {
            switch(value) {
                case 2: return 0;
                case 3: return 1;
                default: return value;
            }
        }
    }
    

Log in to reply
 

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