What if the input matrix is a boolean[][]?


  • 21
    E

    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.


  • 4
    D

    It's possible to use O(min(M, N)) extra space since we can do it by row or column, whichever is smaller. Once we finished the current row / column and next row / column, we can update this row / column.
    It seems to me that O(1) extra space is impossible


  • 0
    X

    I think it's impossible. Since the problem uses int, it allows you to use higher bits of each element, which is actually "extra space" as well. Since it only needs one bit to store the live/ die information.


  • 2
    T

    I took a shot at what dasheng2 said.
    I didn't minimize the space as it would be just a copy-paste 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 <= c-1) prevRow[c-1] = 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[cols-1] = prev; // fill in the gap for last item's late write
        }
    }
    /**
     *     prevRow[c-1]*     prevRow[c]      prevRow[c+1]*
     *             prev  board[r  ] [c]  board[r  ] [c+1]*
     * board[r+1]*[c-1]* 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 <= cols-1) neigh += board[r][c+1]; // only one needs validation from current row
        if (r+1 <= rows-1) 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 <= c-1)             result += row[c-1];
        if (true)                 result += row[c];
        if (c+1 <= row.length-1)  result += row[c+1];
        return result;
    }

  • 0
    P

    Good rolling array solution


  • 0
    A

    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[j-1]
                        if i > 0 and j + 1 < w:      count += prevStatus[j+1]
                        if j > 0:                    count += currStatus[i][j-1]
                        if j + 1 < w:                count += currStatus[i][j+1]
                        if i + 1 < h and j > 0:      count += currStatus[i+1][j-1]
                        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[i-1]
                        if j > 0 and i + 1 < h:      count += prevStatus[i+1]
                        if i > 0:                    count += currStatus[i-1][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[i-1][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] 
    

Log in to reply
 

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