# Using bit manipulation should not count as O(1)

• 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);
}
}
};``````

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