Java O(1) space single pass


  • -1
    E
    public class Solution {
    public void gameOfLife(int[][] board) {
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[r].length; c++) {
                boolean cellIsAlive = board[r][c] > 0;
                int neighbors = (cellIsAlive) ? board[r][c] - 1 : board[r][c] * -1;
                
                // update immediate next cell
                neighbors += countAndUpdateNeighbor(board, r, c + 1, cellIsAlive);
                
                // update neighbors below
                neighbors += countAndUpdateNeighbor(board, r + 1, c - 1, cellIsAlive);
                neighbors += countAndUpdateNeighbor(board, r + 1, c, cellIsAlive);
                neighbors += countAndUpdateNeighbor(board, r + 1, c + 1, cellIsAlive);
                
                // determine our alive state
                board[r][c] = ((cellIsAlive && neighbors == 2) || neighbors == 3) ? 1 : 0;
            }
        }
    }
    
    // Store predecessor neighbor information by having 1 + neighbors for alive, -1 * neighbors for dead
    private int countAndUpdateNeighbor(int[][] board, int r, int c, boolean updaterAlive) {
        if (r >= 0 && r < board.length && c >= 0 && c < board[r].length) {
            if (updaterAlive) {
                if (board[r][c] > 0) {
                    board[r][c]++;
                } else {
                    board[r][c]--;   
                }
            }
            
            return board[r][c] > 0 ? 1 : 0;
        }
        return 0;
    }
    

    }


  • 0

    Nice one. Longer than the simple two-pass solutions, but it definitely is interesting.


Log in to reply
 

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