C++ O(1) space, O(mn) time


  • 171

    Since the board has ints but only the 1-bit is used, I use the 2-bit to store the new state. At the end, replace the old state with the new state by shifting all values one bit to the right.

    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                int count = 0;
                for (int I=max(i-1, 0); I<min(i+2, m); ++I)
                    for (int J=max(j-1, 0); J<min(j+2, n); ++J)
                        count += board[I][J] & 1;
                if (count == 3 || count - board[i][j] == 3)
                    board[i][j] |= 2;
            }
        }
        for (int i=0; i<m; ++i)
            for (int j=0; j<n; ++j)
                board[i][j] >>= 1;
    }
    

    Note that the above count counts the live ones among a cell's neighbors and the cell itself. Starting with int count = -board[i][j] counts only the live neighbors and allows the neat

    if ((count | board[i][j]) == 3)
    

    test. Thanks to aileenbai for showing that one in the comments.


  • 2

    Great code! Well, you include the cell itself when counting the 8 neighbors. At first I did not notice it and had been confused for some time :-)


  • 6
    U

    Hi Stefan, your algorithm is perfect as always! It took me a little while to understand the codeif (count == 3 || count - board[i][j] == 3) I thought it should be if (count == 3 || count + board[i][j] == 3). Then I realized that you also checked the cell itself. Good job!!!


  • 0

    Haha, I have also been confused by that part for some time...


  • 1

    Just in case you like confusion, replace

    if (count == 3 || count - board[i][j] == 3)
        board[i][j] |= 2;
    

    with

    board[i][j] |= (2*count - board[i][j]) % 13 % 8 / 5 * 2;
    

    :-)


  • 0

    Maybe I should have initialized count = -board[i][j] to make it work "as expected".
    But it would be a bit duplicated code and I don't like that :-P


  • 0

    Oh, I got totally confused...


  • 0
    J

    great job!
    I had never thought of using extra bits...
    and if (count == 3 || count - board[i][j] == 3) is also very refined,
    although I think it is a bit something as the two conditions contain one same situation...


  • 0
    A

    I got totally confused too...


  • 0
    K

    nice code, the idea was in my mind but hard to come up with an implementation initially.
    it may more clear to write
    if (board[i][j] == 1 && (count == 2 || count ==3) || board[i][j] == 0 && count == 3)
    as following the description. but longer.


  • 0
    A

    I have a shorter one :)

    if ((count | board[i][j]) == 3)
    

    Oh I did not count the cell itself


  • 0

    Wow, how could I miss that?! Thanks, I included it in my question now.


  • 0
    H
    This post is deleted!

  • 0

    Because of the & 1.


  • 0
    Y

    very clever . Thanks for sharing.


  • 0
    This post is deleted!

  • 2

    Maybe small change makes it more easy to understand.

    class Solution {
    public:
        void gameOfLife(vector<vector<int>>& board) {
            int m=board.size(), n=m?board[0].size():0;
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    int count=0;
                    for(int ss=max(i-1, 0); ss<min(i+2, m); ss++){
                        for(int tt=max(j-1, 0); tt<min(j+2, n); tt++){
                            count+=board[ss][tt]&1;
                        }
                    }
                    count-=board[i][j];
                    
                    if(count==3 || (board[i][j]&&count==2))
                        board[i][j]|=2;
                }
            }
            
            for(int i=0; i<m; i++)
                for(int j=0; j<n; j++)
                    board[i][j]>>=1;
        }
    };

  • 0
    Z
    This post is deleted!

  • 0
    F

    use the 2-bit to store the new state. So clever!


  • 0
    H

    Amazing! Just curious time complexity O(m*n) - shall we count the 8 visits caused by 8 neighbor count processes, especially for those cells are not on the edge?


Log in to reply
 

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