Java 1ms O(mn) time(m*n is the size of the given array) naive and simple in-place solution


  • 0

    The key point is how to make the updated value does not interfere with the current judgement.
    In this problem, there are only 0 and 1 in each cell. Once certain condition is satisfied, 0 will be 1 or 1 will be 0. Otherwise, they keep their value. My solution uses -1 and -2 to mark the 0 and 1 which will not be changed after update and then rewrite the array. Since -1 is the marked 1, during counting 1s in the neighborhood, both 1 and -1 should be counted.
    For the rewrite, when hitting a -1, it should be recovered to 1 while -2 should be recovered to 0. And when hitting 0 or 1, 0 should be flipped into 1 while 1 should be flipped into 0.

    public class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = 0;
        if(m>0) n = board[0].length;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                int count_1 = 0; //used to count the 1s in the current neighborhood
                if(i>0){
                    if(board[i-1][j]==1||board[i-1][j]==-1) count_1++;
                    if(j>0){
                        if(board[i-1][j-1]==1||board[i-1][j-1]==-1) count_1++;
                    }
                    if(j<n-1){
                        if(board[i-1][j+1]==1||board[i-1][j+1]==-1) count_1++;
                    }
                }
                if(i<m-1){
                    if(board[i+1][j]==1||board[i+1][j]==-1) count_1++;
                    if(j>0){
                        if(board[i+1][j-1]==1||board[i+1][j-1]==-1) count_1++;
                    }
                    if(j<n-1){
                        if(board[i+1][j+1]==1||board[i+1][j+1]==-1) count_1++;
                    }
                }
                if(j>0){
                    if(board[i][j-1]==1||board[i][j-1]==-1) count_1++;
                }
                if(j<n-1){
                    if(board[i][j+1]==1||board[i][j+1]==-1) count_1++;
                }
                //if current entry is 1, mark it as -1
                if(count_1>=2&&count_1<=3&&board[i][j]==1) board[i][j] = -1;
                //if current entry is 0, mark it as -2
                if(count_1!=3&&board[i][j] == 0) board[i][j] = -2;  
            }
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(board[i][j]==-1) board[i][j] = 1; 
                else if(board[i][j]==-2) board[i][j] = 0; 
                else if(board[i][j]==1) board[i][j] = 0; 
                else board[i][j] = 1;
            }
        }
    }
    }

Log in to reply
 

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