My ugly java in place solution with recursion O(1) space and O(9mn) time


  • 0
    I
    public void gameOfLife(int[][] board) {
        if(board.length != 0 & board[0].length != 0)
            gameOfLife(board,0,0);
    }
    
    public void gameOfLife(int [][] board, int x, int y){
        int count_live = 0;
        int left = Math.max(0,y-1);
        int right = Math.min(board[x].length-1,y+1);
        int top = Math.max(0,x-1);
        int bottom = Math.min(board.length-1,x+1);
        for(int i = left; i <= right;i++){
            for(int j=top; j <= bottom;j++){
                count_live += board[j][i];
            }
        }
        count_live -= board[x][y];
        if(y + 1 < board[x].length){
           gameOfLife(board,x,y+1); 
        }else{
            if(x + 1 < board.length)
                gameOfLife(board,x+1,0);
        }
        if(count_live < 2 || count_live > 3){
            board[x][y] = 0;
        }else if(count_live  == 3){
            board[x][y] = 1;
        }
    }

  • 0
    T

    Recursion is never O(1), your recursion goes m+n deep and you have quite a few variables: 7xint and 1xref + method call bookkeeping.


Log in to reply
 

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