One pass Java solution with explanations


  • 4

    We tried to solve the problem with one pass and O(1) space consumption. The code is so long that it doesn't run though.

    The basic idea is:
    If the original state is 1
    If it will be 1, it is temporarily set to 1 and will forever be 1.
    If it will be 0, it is temporarily set to -5 and will become 0 at some point.
    If the original state is 0
    If it will be 1, it is temporarily set to 5 and will become 1 at some point.
    If it will be 0, it is temporarily set to 0 and will forever be 0.

    So when do we change the 5s and -5s back to 1 and 0? The idea is when we iterate through the array row by row and col by col, a cell will never be used to determine the next state of another cell when we go past the cell to the south east of it. So each time we deal with a cell, we change the cell to its north west back to 0 or 1.

    There is border conditions to be dealt with, so the code is quite long.

    public class Solution {
        public void gameOfLife(int[][] board) {
            int numRows = board.length;
            int numCols = board[0].length;
            
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (i == numRows - 1) {
                        if (i == 0) {
                            if (j == numCols - 1) {
                                if (j == 0) continue;
                                if (board[i][j] == 0) {
                                    switch(board[i][j - 1]) {
                                        case 5:
                                            board[i][j - 1] = 1;
                                            break;
                                        case 0:
                                            break;
                                        case 1:
                                            break;
                                        case -5:
                                            board[i][j - 1] = 0;
                                            break;
                                    }
                                } else {
                                    switch(board[i][j - 1]) {
                                        case 5:
                                            board[i][j] = 0;
                                            board[i][j - 1] = 1;
                                            break;
                                        case 0:
                                            board[i][j] = 0;
                                            break;
                                        case 1:
                                            board[i][j] = 0;
                                            break;
                                        case -5:
                                            board[i][j] = 0;
                                            board[i][j - 1] = 0;
                                            break;
                                        default:
                                            break;
                                    }
                                }
                            } else if (j == 0) {
                                if (board[i][j] == 1) board[i][j] = -5;
                            } else {
                                if (board[i][j] == 1) {
                                    int liveNeighborCount = 0;
                                    if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                                    if (board[i][j + 1] == 1) liveNeighborCount++;
                                    
                                    switch(liveNeighborCount) {
                                        case 2:
                                            board[i][j] = 1;
                                            break;
                                        default:
                                            board[i][j] = -5;
                                            break;
                                    }
                                    
                                    if (board[i][j - 1] == 5) board[i][j - 1] = 1;
                                    if (board[i][j - 1] == -5) board[i][j - 1] = 0;
                                }
                            }
                        } else {
                            if (j == numCols - 1) {
                                if (j == 0) {
                                    board[i][j] = 0;
                                    
                                    if (board[i - 1][j] == 5) board[i - 1][j] = 1;
                                    if (board[i - 1][j] == -5) board[i - 1][j] = 0;
                                } else {
                                    int liveNeighborCount = 0;
                                    
                                    if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                                    if (board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 5) liveNeighborCount++;
                                    if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                                    
                                    switch(liveNeighborCount) {
                                        case 0:
                                            if (board[i][j] == 1) board[i][j] = 0;
                                            break;
                                        case 1:
                                            if (board[i][j] == 1) board[i][j] = 0;
                                            break;
                                        case 3:
                                            if (board[i][j] == 0) board[i][j] = 1;
                                        default:
                                            break;
                                    }
                                    
                                    if (board[i][j - 1] == 5) board[i][j - 1] = 1;
                                    if (board[i][j - 1] == -5) board[i][j - 1] = 0;
                                    if (board[i - 1][j - 1] == 5) board[i - 1][j - 1] = 1;
                                    if (board[i - 1][j - 1] == -5) board[i - 1][j - 1] = 0;
                                    if (board[i - 1][j] == 5) board[i - 1][j] = 1;
                                    if (board[i - 1][j] == -5) board[i - 1][j] = 0;
                                }
                            } else if (j == 0) {
                                int liveNeighborCount = 0;
                                
                                if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                                if (board[i - 1][j + 1] == 1 || board[i - 1][j + 1] == 5) liveNeighborCount++;
                                if (board[i][j + 1] == 1) liveNeighborCount++;
                                
                                switch(liveNeighborCount) {
                                    case 0:
                                        if (board[i][j] == 1) board[i][j] = -5;
                                        break;
                                    case 1:
                                        if (board[i][j] == 1) board[i][j] = -5;
                                        break;
                                    case 3:
                                        if (board[i][j] == 0) board[i][j] = 5;
                                    default:
                                        break;
                                }
                            } else {
                                int liveNeighborCount = 0;
                                
                                if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                                if (board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 5) liveNeighborCount++;
                                if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                                if (board[i - 1][j + 1] == 1 || board[i - 1][j + 1] == 5) liveNeighborCount++;
                                if (board[i][j + 1] == 1) liveNeighborCount++;
                                
                                if (liveNeighborCount < 2 || liveNeighborCount > 3) if (board[i][j] == 1) board[i][j] = -5;
                                if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                                
                                if (board[i][j - 1] == 5) board[i][j - 1] = 1;
                                if (board[i][j - 1] == -5) board[i][j - 1] = 0;
                                if (board[i - 1][j - 1] == 5) board[i - 1][j - 1] = 1;
                                if (board[i - 1][j - 1] == -5) board[i - 1][j - 1] = 0;
                            }
                        }
                    } else if (i == 0) {
                        if (j == numCols - 1) {
                            if (j == 0) {
                                if (board[i][j] == 1) board[i][j] = -5;
                            } else {
                                int liveNeighborCount = 0;
                                
                                if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                                if (board[i + 1][j - 1] == 1) liveNeighborCount++;
                                if (board[i + 1][j] == 1) liveNeighborCount++;
                                
                                if (liveNeighborCount < 2) if (board[i][j] == 1) board[i][j] = -5;
                                if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                            }
                        } else if (j == 0) {
                            int liveNeighborCount = 0;
                            
                            if (board[i][j + 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j + 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j] == 1) liveNeighborCount++;
                            
                            if (liveNeighborCount < 2) if (board[i][j] == 1) board[i][j] = -5;
                            if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                        } else {
                            int liveNeighborCount = 0;
                            
                            if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                            if (board[i + 1][j - 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j] == 1) liveNeighborCount++;
                            if (board[i + 1][j + 1] == 1) liveNeighborCount++;
                            if (board[i][j + 1] == 1) liveNeighborCount++;
                            
                            if (liveNeighborCount < 2 || liveNeighborCount > 3) if (board[i][j] == 1) board[i][j] = -5;
                            if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                        }
                    } else {
                        if (j == numCols - 1) {
                            if (j == 0) {
                                int liveNeighborCount = 0;
                                
                                if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                                if (board[i + 1][j] == 1) liveNeighborCount++;
                                
                                if (liveNeighborCount < 2) if (board[i][j] == 1) board[i][j] = -5;
                                
                                if (board[i - 1][j] == 5) board[i - 1][j - 1] = 1;
                                if (board[i - 1][j] == -5) board[i - 1][j - 1] = 0;
                            } else {
                                int liveNeighborCount = 0;
                                
                                if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                                if (board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 5) liveNeighborCount++;
                                if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                                if (board[i + 1][j - 1] == 1) liveNeighborCount++;
                                if (board[i + 1][j ] == 1) liveNeighborCount++;
                                
                                if (liveNeighborCount < 2 || liveNeighborCount > 3) if (board[i][j] == 1) board[i][j] = -5;
                                if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                                
                                if (board[i - 1][j - 1] == 5) board[i][j - 1] = 1;
                                if (board[i - 1][j - 1] == -5) board[i][j - 1] = 0;
                                if (board[i - 1][j] == 5) board[i - 1][j - 1] = 1;
                                if (board[i - 1][j] == -5) board[i - 1][j - 1] = 0;
                            }
                        } else if (j == 0) {
                            int liveNeighborCount = 0;
                            
                            if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                            if (board[i - 1][j + 1] == 1|| board[i - 1][j + 1] == 5) liveNeighborCount++;
                            if (board[i][j + 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j + 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j] == 1) liveNeighborCount++;
                            
                            if (liveNeighborCount < 2 || liveNeighborCount > 3) if (board[i][j] == 1) board[i][j] = -5;
                            if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                        } else {
                            int liveNeighborCount = 0;
                            
                            if (board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 5) liveNeighborCount++;
                            if (board[i - 1][j] == 1 || board[i - 1][j] == 5) liveNeighborCount++;
                            if (board[i - 1][j + 1] == 1|| board[i - 1][j + 1] == 5) liveNeighborCount++;
                            if (board[i][j + 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j + 1] == 1) liveNeighborCount++;
                            if (board[i + 1][j] == 1) liveNeighborCount++;
                            if (board[i + 1][j - 1] == 1) liveNeighborCount++;
                            if (board[i][j - 1] == 1 || board[i][j - 1] == 5) liveNeighborCount++;
                            
                            if (liveNeighborCount < 2 || liveNeighborCount > 3) if (board[i][j] == 1) board[i][j] = -5;
                            if (liveNeighborCount == 3) if (board[i][j] == 0) board[i][j] = 5;
                            
                            if (board[i - 1][j - 1] == 5) board[i - 1][j - 1] = 1;
                            if (board[i - 1][j - 1] == -5) board[i - 1][j - 1] = 0;
                        }
                    }
                }
            }
        }
    }
    

  • 2

    This is a smart solution! Good job, man.


  • 2

    WOW, genius!


  • 2
    S

    That's the best solution I've ever seen. It is so amazing!!!!!!!!!!


  • 2

    @shashasha Thank you!


  • 1

    I really can't tell whether you guys are serious or making fun of him...


  • 1

    This guy is obviously posting this for fun!!!


  • 0

    @jedihy Hmm, not obvious to me. Maybe I've just seen too many bad solutions posted seriously. Also, looks like a lot of effort for just having a little fun :-)


  • 0
    S

    Why are you so clever, master!


  • 0
    S

    //Here is my solution, FYI
    public class Solution {
    public void gameOfLife(int[][] board) {
    //use -1 : 1 ->1 , -2 : 1 -> 0, 2 : 0 -> 0, 3 : 0 -> 1
    if (board.length == 0 || board[0].length == 0) return;
    int len1 = board.length; int len2 = board[0].length;
    int[][] neighbors = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    for (int i = 0; i < len1; i ++) {
    for (int j = 0; j < len2; j ++) {
    int liveCount = 0;
    for (int[] neighbor : neighbors) {
    int row = i + neighbor[0];
    int col = j + neighbor[1];
    if (row < 0 || row >= len1 || col < 0 || col >= len2) continue;
    if (board[row][col] == 1 || board[row][col] == -1 || board[row][col] == -2) liveCount ++;
    }
    if (board[i][j] == 1) board[i][j] = (liveCount == 2 || liveCount == 3) ? -1 : -2;
    else board[i][j] = liveCount == 3 ? 3 : 2;
    }
    }
    for (int i = 0; i < len1; i ++) {
    for (int j = 0; j < len2; j ++) {
    board[i][j] = (board[i][j] == -1 || board[i][j] == 3) ? 1 : 0;
    }
    }
    }
    }


  • 0
    This post is deleted!

  • 0

    @SenyangZ

    //Here is my solution, FYI
    public class Solution {
    public void gameOfLife(int[][] board) {
    //use -1 : 1 ->1 , -2 : 1 -> 0, 2 : 0 -> 0, 3 : 0 -> 1
    if (board.length == 0 || board[0].length == 0) return;
    int len1 = board.length; int len2 = board[0].length;
    int[][] neighbors = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    for (int i = 0; i < len1; i ++) {
    for (int j = 0; j < len2; j ++) {
    int liveCount = 0;
    for (int[] neighbor : neighbors) {
    int row = i + neighbor[0];
    int col = j + neighbor[1];
    if (row < 0 || row >= len1 || col < 0 || col >= len2) continue;
    if (board[row][col] == 1 || board[row][col] == -1 || board[row][col] == -2) liveCount ++;
    }
    if (board[i][j] == 1) board[i][j] = (liveCount == 2 || liveCount == 3) ? -1 : -2;
    else board[i][j] = liveCount == 3 ? 3 : 2;
    }
    }
    for (int i = 0; i < len1; i ++) {
    for (int j = 0; j < len2; j ++) {
    board[i][j] = (board[i][j] == -1 || board[i][j] == 3) ? 1 : 0;
    }
    }
    }
    }

  • 0
    S

    @adam47 Thanks for the highlight


  • 2

    Posting code like that is polluting this site.

    public class Solution {
        public void gameOfLife(int[][] board) {
            //use -1 : 1 ->1 , -2 : 1 -> 0, 2 : 0 -> 0, 3 : 0 -> 1
            if (board.length == 0 || board[0].length == 0) return;
            int len1 = board.length;
            int len2 = board[0].length;
    		int[][] neighbors = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
            for (int i = 0; i < len1; i++) {
                for (int j = 0; j < len2; j++) {
                    int liveCount = 0;
                    for (int[] neighbor: neighbors) {
                        int row = i + neighbor[0];
                        int col = j + neighbor[1];
                        if (row < 0 || row >= len1 || col < 0 || col >= len2) continue;
                        if (board[row][col] == 1 || board[row][col] == -1 || board[row][col] == -2) liveCount++;
                    }
                    if (board[i][j] == 1) board[i][j] = (liveCount == 2 || liveCount == 3) ? -1 : -2;
                    else board[i][j] = liveCount == 3 ? 3 : 2;
                }
            }
            for (int i = 0; i < len1; i++) {
                for (int j = 0; j < len2; j++) {
                    board[i][j] = (board[i][j] == -1 || board[i][j] == 3) ? 1 : 0;
                }
            }
        }
    }
    

  • 0
    R

    Did you guys seriously read those 1000 lines of code? :)


Log in to reply
 

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