GameOfLife.java

// Source : https://leetcode.com/problems/game-of-life/
// Author : cornprincess
// Date   : 2020-04-02

/***************************************************************************************************** 
 *
 * According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular 
 * automaton devised by the British mathematician John Horton Conway in 1970."
 *
 * Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell 
 * interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules 
 * (taken from the above Wikipedia article):
 *
 * 	Any live cell with fewer than two live neighbors dies, as if caused by under-population.
 * 	Any live cell with two or three live neighbors lives on to the next generation.
 * 	Any live cell with more than three live neighbors dies, as if by over-population..
 * 	Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
 *
 * Write a function to compute the next state (after one update) of the board given its current state. 
 * The next state is created by applying the above rules simultaneously to every cell in the current 
 * state, where births and deaths occur simultaneously.
 *
 * Example:
 *
 * Input: 
 * [
 *   [0,1,0],
 *   [0,0,1],
 *   [1,1,1],
 *   [0,0,0]
 * ]
 * Output: 
 * [
 *   [0,0,0],
 *   [1,0,1],
 *   [0,1,1],
 *   [0,1,0]
 * ]
 *
 * Follow up:
 *
 * 	Could you solve it in-place? Remember that the board needs to be updated at the same time: 
 * You cannot update some cells first and then use their updated values to update other cells.
 * 	In this question, we represent the board using a 2D array. In principle, the board is 
 * infinite, which would cause problems when the active area encroaches the border of the array. How 
 * would you address these problems?
 *
 ******************************************************************************************************/

package GameOfLife;

public class GameOfLife {
    // Time Complexity O(nm)
    // Space Complexity O(mn)
    public void copyBoard(int[][] board) {
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

        int rows = board.length;
        int cols = board[0].length;
        int[][] copyBoard = new int[rows][cols];

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                int liveNeighbour = 0;
                for (int i = 0; i < 8; i++) {
                    int x = row + dx[i];
                    int y = col + dy[i];
                    if (x >= rows || x < 0 || y >= cols || y < 0) {
                        continue;
                    }
                    liveNeighbour += copyBoard[x][y] & 1;
                }

                if (board[row][col] == 1) {
                    if (liveNeighbour < 2 || liveNeighbour > 3) {
                        board[row][col] = 0;
                    }
                } else {
                    if (liveNeighbour == 3) {
                        board[row][col] = 1;
                    }
                }

            }
        }
    }

    // Time Complexity O(nm)
    // Space Complexity O(1)
    public void bitwise(int[][] board) {
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

        int rows = board.length;
        int cols = board[0].length;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                int liveNeighbour = 0;
                for (int i = 0; i < 8; i++) {
                    int x = row + dx[i];
                    int y = col + dy[i];
                    if (x >= rows || x < 0 || y >= cols || y < 0) {
                        continue;
                    }
                    liveNeighbour += board[x][y] & 1;
                }

                if (board[row][col] == 1) {
                    if (liveNeighbour == 2 || liveNeighbour == 3) {
                        board[row][col] |= 2;
                    }
                } else {
                    if (liveNeighbour == 3) {
                        board[row][col] |= 2;
                    }
                }

            }
        }

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                board[row][col] >>= 1;
            }
        }
    }
}