This question is about implementing a basic elimination algorithm for Candy Crush.
Given an m x n
integer array board
representing the grid of candy where board[i][j]
represents the type of candy. A value of board[i][j] == 0
represents that the cell is empty.
class Solution {
public int[][] candyCrush(int[][] board) {
// two main steps to solve this problem are crush and drop
//validate board first
if(board == null || board.length == 0) return board;
int rows = board.length;
int cols = board[0].length;
//mark and crush by setting value to -ve
boolean markedCols = markColsToCrush(board);
boolean markedRows = markRowsToCrush(board) ;
while( markedCols|| markedRows)
{
//drop
drop(board);
markedCols = markColsToCrush(board);
markedRows = markRowsToCrush(board) ;
}
return board;
}
private boolean markColsToCrush(int[][] board)
{
boolean marked = false;
int rows = board.length;
int cols = board[0].length;
for(int r = 0; r < rows ; ++r )
{
//traverse through the cols of board and marked the cell by negate value
//set the flag to true
for(int c = 0 ; c +2 < cols ; ++c )
{
int value = Math.abs(board[r][c] );
int valueAt1 = Math.abs(board[r][c+1] );
int valueAt2 = Math.abs(board[r][c+2] );
if(value != 0 && value == valueAt1 && value == valueAt2)
{
board[r][c] = board[r][c+1] = board[r][c+2] = -value;
marked = true ;
}
}
}
return marked;
}
private boolean markRowsToCrush(int[][] board)
{
boolean marked = false;
int rows = board.length;
int cols = board[0].length;
for(int r = 0; r+2 < rows ; ++r )
{
//traverse through the rows of board and marked the cell by negate value
//set the flag to true
for(int c = 0 ; c < cols ; ++c )
{
int value = Math.abs(board[r][c] );
int valueAt1 = Math.abs(board[r+1][c] );
int valueAt2 = Math.abs(board[r+2][c] );
if(value != 0 && value == valueAt1 && value == valueAt2)
{
board[r][c] = board[r+1][c] = board[r+2][c] = -value;
marked = true ;
}
}
}
return marked;
}
private void drop(int[][] board)
{
int rows = board.length;
int cols = board[0].length;
for(int c = 0; c< cols ; ++c)
{
//two pointer technique to iterate and move values
int row = rows-1;
for(int r = rows-1 ; r >= 0 ; --r )
if(board[r][c] > 0 )
//set the value to row index
board[row--][c] = board[r][c];
while(row >= 0 )
{
//set the cell value to 0 and if it will be avail for drop in next col iteration
board[row--][c] = 0;
}
}
}
}
help full