# Simple AC Java Solution With Explanation -- Easy to Understand

• This is a brute force 2 pass approach. The idea is very simple and can be broken up into 3 basic parts. Since I was writing it during contest, code is a little verbose, but very straight forward. Feel free to suggest edits if you see any :)

Idea:

1. Traverse Matrix for each index if it isn't empty (Ie: 0), we need to search in 4 directions (up, down, left, right) for as many contiguous identical cells and keep a count in each direction. If the count is >= 3, we need to mark those cells as needed for deletion (with -1 in our deletion_board).

2. Traverse Matrix from bottom row up (left to right) and for each cell that was marked for deletion (with -1 in our deletion board) , we search upwards for the nearest neighbor in it's column that is available (not -1). We swap the value with our current cell.

3. Maintain a deletion flag to track if anything was deleted in the previous iteration (any direction has 3 or more identical cells). If so, we clear our deletion flag and our deletion_board and repeat.

Runtime:
First Pass: O(n * m * (m + n))
Second Pass: O(n * m * n);
Overall: O(n * m * (m + n))

``````class Solution {
public int[][] candyCrush(int[][] board) {
int rows = board.length;
int cols = board[0].length;
boolean deletion = true;

while(deletion) {
deletion = false;
int[][] deletion_board = new int[rows][cols];
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 0){
continue;
}
deletion |= markDeletion(board, i, j, rows, cols, deletion_board);
}
}

// if something has been deleted, we need to drop cells down
if(deletion) {
for(int i = rows - 1; i >= 0; i--){
for(int j = 0; j < cols; j++){
if(deletion_board[i][j] == -1){
board[i][j] = search(board, i, j, deletion_board);
}
}
}
}
}

return board;
}

// for a deleted cell, looks up for closest non deleted neighbor
// moves that non deleted cell to current position and marks it as deleted
public int search(int[][] board, int i, int j, int[][] deletion_board){
int index = i-1;
while(index >= 0 && deletion_board[index][j] == -1){
index--;
}

if(index < 0){
return 0;
} else {
int res = board[index][j];
deletion_board[index][j] = -1;
return res;
}
}

// 1. Counts # of cells that share same value as (i, j) in 4 directions: Up, Down, Left, Right
// 2. If Count is >= 3, we go back and mark those cells as ready for deletion. Since a group of 3 vertically and horizontally may intersect, we use a separate matrix called deletion_board to track which cells we need to remove with -1. Note: We cannot mark -1 on the original board because this will cause some cells not to be marked correctly. See Example below!

/*   Ex:
*   1 0 0     -1 0 0
*   1 0 0 =>  -1 0 0
*   1 1 1     -1 1 1
*/
// In the example above, the bottom row also needs to be deleted, but because we changed cell (2, 0) from 1 to -1, it affects the count when you reach the bottom. With the new count = 2, it won't mark the cells correctly as needed for deletion.

public boolean markDeletion(int[][] board, int i, int j, int rows, int cols, int[][] deletion_board){

boolean flag = false;
// search up
int up_count = 1;
for(int k = i-1; k >= 0; k--){
if(board[k][j] != board[i][j]){
break;
} else {
up_count++;
}
}

if(up_count >= 3){
flag = true;
for(int k = 0; k < up_count; k++){
deletion_board[i - k][j] = -1;
}
}

// search down
int down_count = 1;
for(int k = i+1; k < rows; k++){
if(board[k][j] != board[i][j]){
break;
} else {
down_count++;
}
}

if(down_count >= 3){
flag = true;
for(int k = 0; k < down_count; k++){
deletion_board[i + k][j] = -1;
}
}

// search left
int left_count = 1;
for(int k = j-1; k >= 0; k--){
if(board[i][k] != board[i][j]){
break;
} else {
left_count++;
}
}

if(left_count >= 3){
flag = true;
for(int k = 0; k < left_count; k++){
deletion_board[i][j - k] = -1;
}
}

// search right
int right_count = 1;
for(int k = j+1; k < cols; k++){
if(board[i][k] != board[i][j]){
break;
} else {
right_count++;
}
}

if(right_count >= 3){
flag = true;
for(int k = 0; k < right_count; k++){
deletion_board[i][j + k] = -1;
}
}
return flag;
}
}
``````

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