Java readable solution. In-place.


  • 0
    C
    public int[][] candyCrush(int[][] board) {
            int height = board.length;
            int width = board[0].length;
            while(crush(board, height, width)) {
                drop(board, height, width);
            }
            return board;
        }
        
        private boolean crush(int[][] board, int height, int width) {
            boolean canCrush = false;    // if true, then the board need to be updated by drop()
            // vertical
            for(int r = 1; r < height - 1; r++) {
                for(int c = 0; c < width; c++) {
                    int current = Math.abs(board[r][c]);
                    if(current == 0) continue;
                    
                    int top = Math.abs(board[r - 1][c]);
                    int bottom = Math.abs(board[r + 1][c]);
                    if(current == top && current == bottom) {
                        canCrush = true;
                        board[r][c] = -current;
                        board[r - 1][c] = -top;
                        board[r + 1][c] = -bottom;
                    }
                }
            }
            // horizontal
            for(int r = 0; r < height; r++) {
                for(int c = 1; c < width - 1; c++) {
                    int current = Math.abs(board[r][c]);
                    if(current == 0) continue;
                    
                    int left = Math.abs(board[r][c - 1]);
                    int right = Math.abs(board[r][c + 1]);
                    if(current == left && current == right) {
                        canCrush = true;
                        board[r][c] = -current;
                        board[r][c - 1] = -left;
                        board[r][c + 1] = -right;
                    }
                }
            }
            return canCrush;
        }
        
        private void drop(int[][] board, int height, int width) {
            for(int c = 0; c < width; c++) {
                int last = height - 1;       // the position/row where next candy should drop to
                for(int r = height - 1; r >= 0; r--) {
                    if(board[r][c] == 0) {
                        break;
                    } else if(board[r][c] > 0) {
                        int temp = board[r][c];
                        board[r][c] = board[last][c];
                        board[last][c] = temp;
                        last--;
                    } else {
                        board[r][c] = 0;
                    }
                }
            }
        }
    

Log in to reply
 

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