Easy and Clear Java Solution


  • 0
    S

    The idea is to first check row by row and mark element that eligible for crushing as negative. So that you can still to check column by column whether it can be involved in some column crushing. for example:

    1 2 2 2
    1 3 4 2
    2 4 1 2

    after row to row marking , you will get :

    1 -2 -2 -2
    1 3 4 2
    2 4 1 2

    Then do a column to column scan (from bottom to up), both for checking crushing for elements in the same column and crush the elements meanwhile by maintain two pointers. the bottom pointer points to where to put next living element and the top pointer point to the next element to scan

    public int[][] candyCrush(int[][] board) {
            /**
            
               row ---  0 ~ rows
               col ---  1 ~ cols   count --> 1
               
                  if (col == col - 1) count++ 
                  else count = 1
                  
                  if (count == 3)  col = col -1 = col - 2 --> negative
                  else if (count > 3) col --> negative
                col --- 0 ~ cols
                row --- rows - 2 ~ 0 count ---> 1 , start --> 0 // indicate the starting copy position
                {
                
                if (row != row + 1 || row == 0){
                   if (count < 3)
                        move previous count of element to start 
                    count = 1;
                } else count ++
                start ---> first negative point
                }
            
            **/
            
            boolean stable = true;
            int rows = board.length;
            int cols = board[0].length;
            do {
                stable = true;
                for (int r = 0; r < rows; r++) {
                    int count = 1;
                    int[] row = board[r];
                    for (int c = 1; c < cols; c++) {
                        if (row[c] == Math.abs(row[c - 1])) count++;
                        else count = 1;
                        if (count >= 3 && row[c] != 0) {
                            stable = false;
                            row[c] = -row[c];
                            if (count == 3) row[c - 1] = row[c - 2] = row[c];
                        }
                    }
                }
                
                for (int c = 0; c < cols; c++) {
                    int start = rows - 1;
                    int count = 1;
                    int r = rows - 2;
                    for (; r >= -1; r--) {
                        
                        if (r == -1 || Math.abs(board[r][c]) != Math.abs(board[r+1][c])) {
                            if (count < 3) {
                                for (int i = r + count; i > r; i--) {
                                    if (board[i][c] > 0) board[start--][c] = board[i][c];
                                }
                            } else stable = false;
                            count = 1;
                        } else count++;
                        if (r >= 0 && board[r][c] == 0) break;
                    }
                    while(start >= Math.max(0, r+1)) board[start--][c] = 0;
                }
                
                
            } while (!stable);
            return board;
        }
    

Log in to reply
 

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