Using bit manipulation should not count as O(1)


  • 5
    K

    Really, I think using extra storage in high bits of ints isn't really O(1). The authors should really have changed the input to vector<vector<bool>> to make this impossible.
    And while I'm not aware of a real O(1) solution, O(n) for n*m sized board is relatively easy: just store the original state of 'previous row':

    class Solution {
    public:
        struct Fb {
            vector<vector<int>>& board;
            vector<int> frontier;
            int fpos;
            Fb(vector<vector<int>>& b) : board(b), frontier(board[0]), fpos(-1) {}
            int at(int i, int j) {
                if (j < 0 || j >= frontier.size())
                    return 0;
                if (i < 0 || i >= board.size())
                    return 0;
                if (i == fpos) {
                    return frontier[j];
                }
                return board[i][j];
            }
            void push(vector<int>& nf) {
                fpos++;
                if (fpos < board.size())
                    frontier = board[fpos];
                if (fpos >= 0)
                    swap(board[fpos], nf);
            }
        };
        void gameOfLife(vector<vector<int>>& board) {
            Fb fb(board);
            vector<int> newline(board[0].size(), 0);
            for (int i = 0; i < board.size(); ++i) {
                for (int j = 0; j < board[i].size(); ++j) {
                    int count = fb.at(i-1, j-1) + fb.at(i-1, j) + fb.at(i-1, j+1) 
                            + fb.at(i, j-1) + fb.at(i, j+1) 
                            + fb.at(i+1, j-1) + fb.at(i+1, j) + fb.at(i+1, j+1);
                    int me = fb.at(i, j);
                    if (me) {
                        newline[j] = (count == 2 || count == 3) ? 1 : 0;
                    }
                    else {
                        newline[j] = count == 3 ? 1 : 0;
                    }
                }
                fb.push(newline);
            }
        }
    };

Log in to reply
 

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