# C++ solution O(n^2)

• '''

class Solution {
public:
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
if(board.size() < 3 && board[0].size() < 3)
return board;
else {
crush(board);
return board;
}
}

``````void crush(vector<vector<int>>& board) {
vector<vector<int>> vertical(board.size(), vector<int>(board[0].size(), 1));
vector<vector<int>> horizontal(board.size(), vector<int>(board[0].size(), 1));

bool boardDirty = false;
for(int i = 0 ; i < board.size() ; i++) {
for(int j = 0 ; j < board[i].size() ; j++) {
if(board[i][j] == 0) continue;

if(i > 0 && board[i][j] == board[i-1][j]) {
vertical[i][j] = vertical[i-1][j] + 1;
if(vertical[i][j] >= 3) {
boardDirty = true;
}
}
if(j > 0 && board[i][j] == board[i][j-1]) {
horizontal[i][j] = horizontal[i][j-1] + 1;
if(horizontal[i][j] >= 3) {
boardDirty = true;
}
}
}
}

vector<int> zeros(board[0].size(),0);

if(boardDirty) {
// consolidate positions to squash
for(int i = board.size()-1 ; i >= 0 ; i--) {
for(int j = board[i].size()-1 ; j >= 0 ; j--) {
int tempv = vertical[i][j], temph = horizontal[i][j];
if(tempv >= 3) {
zeros[j] += tempv;
for(int k=0 ; k < tempv ; k++) {
board[i-k][j] = 0;
vertical[i-k][j] = 0;
}
}

if(temph >= 3) {
for(int k=0 ; k < temph ; k++){
if(vertical[i][j-k] < 3)
zeros[j-k] += 1;
board[i][j-k] = 0;
horizontal[i][j-k] = 0;
}
}
}
}

// crush candies
int n = board.size();
for(int j=0 ; j < board[0].size(); j++) {
int z = n-1, pos = zeros[j];
for(int i=n-1 ; i >= 0 ; i--) {
if(board[i][j] != 0) {
board[z][j] = board[i][j];
if(z != i) board[i][j] = 0;
z--;
}
}
}
}

if(boardDirty)
crush(board);
}
``````

};

'''

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