Only one nested loop, in-place, java solution


  • 1
    L

    The idea is simple just like other solutions, and the diffrence is I used only one nested loop instead of two. For each point, there are previous-neighbors:
    [i-1,j-1].....[i-1,j]..... [ i-1, j+1]
    [i, j-1]
    and post-neighbors:
    ................................[i, j+1]
    [i+1, j-1]....[i+1, j].....[i+1,j+1]
    We loop through board, find board[i][j]'s totalNeighbor = previous + post, and if board[i][j] == 1, we update all its post-neighbors: ++ for those >=1, and -- for those <= 0. After this operation, each board[i][j] record its previous neighbors and we only need to find its post neighbors, thus one loop.

    '''
    public class Solution {

    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int row = board.length, col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
    
                // board[i][j] > 0 means there was an '1' initially
                if (board[i][j] > 0) {
                    int totalNeighbors = board[i][j] - 1 + postNeighbors(board, i, j, row, col);
               
                    if (totalNeighbors == 2 || totalNeighbors == 3) {
                        board[i][j] = 1;
                    } else {
                        board[i][j] = 0;
                    }
                    // And we update its post neighbors
                    updatePostNeighbors(board, i, j, row, col);
                    continue;
                }
                
                // board[i][j] <= 0 means there was a '0' initially
                if (board[i][j] <= 0) {
                    int totalNeighbors = -board[i][j] + postNeighbors(board, i, j, row, col);
                    if (totalNeighbors == 3) {
                        board[i][j] = 1;
                    } else {
                        board[i][j] = 0;
                    }
                }
            }
        }
    }
    
    
    private void updatePostNeighbors(int[][] board, int i, int j, int row, int col) {
        if (j+1 < col) {
            if (board[i][j+1] >= 1) {
                board[i][j+1]++;
            } else {
                board[i][j+1]--;
            }
        }
        
        if (i + 1 < row) {
            if (j-1 >= 0) {
                if (board[i+1][j-1] >= 1) {
                    board[i+1][j-1]++;
                } else {
                    board[i+1][j-1]--;
                }
            }
            
            board[i+1][j] = board[i+1][j] >= 1? board[i+1][j] + 1 : board[i+1][j] - 1;
            
            if (j+1 < col) {
                board[i+1][j+1] = board[i+1][j+1] >= 1? board[i+1][j+1] + 1 : board[i+1][j+1] - 1;
            }
        }
    }
    
    private int postNeighbors(int[][] b, int i, int j, int row, int col) {
        int n = 0;
        if (j+1 < col && b[i][j+1] >= 1) n++;
        
        if (i + 1 < row) {
            if (j-1 >= 0 && b[i+1][j-1] >= 1) n++;
            if (b[i+1][j] >= 1) n++;
            if (j+1 < col && b[i+1][j+1] >= 1) n++;
        }
        return n;
    }
    

    }
    '''


  • 0
    C

    wow, brilliant!


Log in to reply
 

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