Simple in-place java solution. O(1) space, O(mn) time.


  • 0
    class Solution {
        public void gameOfLife(int[][] board) {
            for (int i = 0; i < board.length; i++)
            {
                for (int j = 0; j < board[i].length; j++)
                {
                    int cell = board[i][j];
                    if (cell == 1)
                    {
                        board[i][j] = getUpdatedLiveValue(board, i, j);
                    }
                    else if (cell == 0)
                    {
                        board[i][j] = getUpdatedDeadValue(board, i, j);
                    }
                }
            }
            
            for (int i = 0; i < board.length; i++)
            {
                for (int j = 0; j < board[i].length; j++)
                {
                    int cell = board[i][j];
                    // If the cell was set to 3, it means the value used to be alive but is now dead,
                    // so we update the cell to be 0.
                    if (cell == 3)
                    {
                        board[i][j] = 0;
                    }
                    // If the cell was set to 2, it means the value used to be dead but is now alive,
                    // so we update the cell to be 1.
                    else if (cell == 2)
                    {
                        board[i][j] = 1;
                    }
                }
            }
        }
        
        private int getUpdatedLiveValue(int[][] board, int row, int col)
        {
            int liveNeighbors = getLiveNeighbors(board, row, col);
            // The value 3 represents that the live value died. Because the value is still
            // odd, it will get processed as a live value, and at the end we can treat it as dead. 
            if (liveNeighbors < 2 || liveNeighbors > 3) return 3;
            else return 1;
        }
        
        private int getUpdatedDeadValue(int[][] board, int row, int col)
        {
            int liveNeighbors = getLiveNeighbors(board, row, col);
            // The value 2 represents the dead value became alive. Because the value is still
            // even, it will get processed as a dead value, and at the end we can treat it as live. 
            if (liveNeighbors == 3) return 2;
            else return 0;
        }
        
        private int getLiveNeighbors(int[][] board, int row, int col)
        {
            int liveNeighbors = 0;
            liveNeighbors += isAlive(board, row-1, col) ? 1 : 0;
            liveNeighbors += isAlive(board, row, col-1) ? 1 : 0;
            liveNeighbors += isAlive(board, row-1, col-1) ? 1 : 0;
            liveNeighbors += isAlive(board, row-1, col+1) ? 1 : 0;
            liveNeighbors += isAlive(board, row, col+1) ? 1 : 0;
            liveNeighbors += isAlive(board, row+1, col+1) ? 1 : 0;
            liveNeighbors += isAlive(board, row+1, col-1) ? 1 : 0;
            liveNeighbors += isAlive(board, row+1, col) ? 1 : 0;
            return liveNeighbors;
        }
        
        private boolean isAlive(int[][] board, int row, int col)
        {
            if(row < 0 || row >= board.length || col >= board[row].length || col < 0 ) return false;
            return (board[row][col] % 2 != 0);
        }
    }
    

Log in to reply
 

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