It seems that encoding inside original int[][] just utilized spare spaces from matrix. What if the input matrix is a boolean matrix? Is there still a way to solve it without extra space? Thanks.
What if the input matrix is a boolean[][]?

I took a shot at what dasheng2 said.
I didn't minimize the space as it would be just a copypaste or unnecessary complication for sharing.public void gameOfLife(int[][] board) { if (board.length == 0  board[0].length == 0) return; int rows = board.length, cols = board[0].length; // previous row always exists (it's all 0s above board's first row) int[] prevRow = new int[cols]; for (int r = 0; r < rows; ++r) { int prev = 0; // fakes a dead cell in front of current row for (int c = 0; c < cols; ++c) { int neigh = neigh(board, r, c, prevRow, prev); if (0 <= c1) prevRow[c1] = prev; // only overwrite once not needed prev = board[r][c]; board[r][c] = neigh == 3 /* lives on(3)/reproduction */  board[r][c] + neigh == 3 /* lives on(2) */ ? 1 : 0; } prevRow[cols1] = prev; // fill in the gap for last item's late write } } /** * prevRow[c1]* prevRow[c] prevRow[c+1]* * prev board[r ] [c] board[r ] [c+1]* * board[r+1]*[c1]* board[r+1]*[c]* board[r+1]*[c+1]* * * starred: needs bound check */ int neigh(int[][] board, int r, int c, int[] prevRow, int prev) { int rows = board.length, cols = board[0].length; int neigh = prev; // remember, board[r][c] doesn't count; if (true) neigh += validSum(prevRow, c); // prevRow always exists if (c+1 <= cols1) neigh += board[r][c+1]; // only one needs validation from current row if (r+1 <= rows1) neigh += validSum(board[r+1], c); // only if there's a next row return neigh; } int validSum(int[] row, int c) { int result = 0; if (0 <= c1) result += row[c1]; if (true) result += row[c]; if (c+1 <= row.length1) result += row[c+1]; return result; }

I have coded a solution in Python that works on @dasheng2's idea.
Space complexity is O(min(n,m))class Solution(object): def gameOfLife(self, currStatus): h = len(currStatus) w = len(currStatus[0]) if h >= w: for i in xrange(h): nextStatus = currStatus[i][:] for j in xrange(w): count = 0 if i > 0: count += prevStatus[j] if i > 0 and j > 0: count += prevStatus[j1] if i > 0 and j + 1 < w: count += prevStatus[j+1] if j > 0: count += currStatus[i][j1] if j + 1 < w: count += currStatus[i][j+1] if i + 1 < h and j > 0: count += currStatus[i+1][j1] if i + 1 < h: count += currStatus[i+1][j] if i + 1 < h and j + 1 < w: count += currStatus[i+1][j+1] if (currStatus[i][j] and (count < 2 or count > 3)) or (not currStatus[i][j] and count == 3): nextStatus[j] = not nextStatus[j] prevStatus, currStatus[i] = currStatus[i][:], nextStatus[:] else: for j in xrange(w): nextStatus = [x[j] for x in currStatus] for i in xrange(h): count = 0 if j > 0: count += prevStatus[i] if j > 0 and i > 0: count += prevStatus[i1] if j > 0 and i + 1 < h: count += prevStatus[i+1] if i > 0: count += currStatus[i1][j] if i + 1 < h: count += currStatus[i+1][j] if j + 1 < w: count += currStatus[i][j+1] if j + 1 < w and i > 0: count += currStatus[i1][j+1] if j + 1 < w and i + 1 < h: count += currStatus[i+1][j+1] if (currStatus[i][j] and (count < 2 or count > 3)) or (not currStatus[i][j] and count == 3): nextStatus[i] = not nextStatus[i] prevStatus = [x[j] for x in currStatus] for i in xrange(h): currStatus[i][j] = nextStatus[i]