Simple AC Java Solution With Explanation -- Easy to Understand


  • 0
    S

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

Log in to reply
 

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