Faster solution than current highest voted solution.


  • 0
    O

    So far, the best solution is: https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation

    This is a very brilliant solution. However, we can still improve it a little. In the first loop, that method calculated the count for all cells ( m * n times). Instead, we may update the board only when a cell is 1 and do anything when it is 0. That will reduce the operations in the first loop, especially when there are few cells being 1.

    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) { return; }
        int m = board.length, n = board[0].length;
        int[][] dirs = new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((board[i][j] & 1) == 1) {
                    updateBoard(board, i, j, dirs);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int life = (board[i][j] >> 1);
                if ((board[i][j] & 1) == 1) {
                    board[i][j] = (life == 2 || life == 3) ? 1 : 0;
                } else {
                    board[i][j] = life == 3 ? 1 : 0;
                }
            }
        }
    }
    
    private void updateBoard(int[][] board, int i, int j, int[][] dirs) {
        int m = board.length, n = board[0].length;
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x < 0 || y < 0 || x == m || y == n) {
                continue;
            }
            board[x][y] += 2;
        }
    }

Log in to reply
 

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