Candy Crush Puzzle algorithm in Java

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;
                }
        }
    }
}

1 thought on “Candy Crush Puzzle algorithm in Java”

Leave a Comment

Your email address will not be published. Required fields are marked *