Java O(1) space O(mn) time, State transition encoder


  • 0
    Z

    The state change of a cell in the matrix can be summarized as:
    0->0 : 2
    0->1 : 3
    1->0 : 4
    1->1 : 5
    So I encode them with simple int value listed above (bold). For each update, we use state transition to replace the value in the original matrix, and convert them back to the 1 0 value after updating all cells in the matrix.

    public class Solution {
            class Tran {
    		int ZERO_ZERO = 2;
    		int ZERO_ONE = 3;
    		int ONE_ZERO = 4;
    		int ONE_ONE = 5;
    	}
    
    	private Tran t = new Tran();
    
    	public void gameOfLife(int[][] board) {
    		int m = board.length;
    		int n = board[0].length;
    		for (int row = 0; row < m; row++) {
    			for (int col = 0; col < n; col++) {
    				checkStats(board, row, col);
    			}
    		}
    		for (int row = 0; row < m; row++) {
    			for (int col = 0; col < n; col++) {
    				board[row][col] = convertStats(board[row][col]);
    			}
    		}
    	}
    
    	private void checkStats(int[][] board, int row, int col) {
    		int live = countlive(board, row, col);
    		if (islive(board[row][col])) {
    			if (live < 2 || live > 3)
    				board[row][col] = t.ONE_ZERO; // die
    			else
    				board[row][col] = t.ONE_ONE; // keep live
    		} else {
    			if (live == 3)
    				board[row][col] = t.ZERO_ONE; // relive
    		}
    	}
    
    	private int countlive(int[][] board, int row, int col) {
    		int live = 0;
    		for (int r = row - 1; r <= row + 1; r++) {
    			for (int c = col - 1; c <= col + 1; c++) {
    				if (r >= 0 && r < board.length && c >= 0 && c < board[0].length) {
    					if (!(r == row && c == col)) {
    						if (islive(board[r][c]))
    							live++;
    					}
    				}
    			}
    		}
    		return live;
    	}
    
    	private int convertStats(int n) {
    		return (n == t.ONE_ONE || n == t.ZERO_ONE) ? 1 : 0;
    	}
    
    	private boolean islive(int n) {
    		return n == 1 || n == t.ONE_ONE || n == t.ONE_ZERO;
    	}
    }
    

Log in to reply
 

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