C++ solution O(n^2)


  • 0
    G

    '''

    class Solution {
    public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
    if(board.size() < 3 && board[0].size() < 3)
    return board;
    else {
    crush(board);
    return board;
    }
    }

    void crush(vector<vector<int>>& board) {
        vector<vector<int>> vertical(board.size(), vector<int>(board[0].size(), 1));
        vector<vector<int>> horizontal(board.size(), vector<int>(board[0].size(), 1));
        
        bool boardDirty = false;
        for(int i = 0 ; i < board.size() ; i++) {
            for(int j = 0 ; j < board[i].size() ; j++) {
                if(board[i][j] == 0) continue;
                
                if(i > 0 && board[i][j] == board[i-1][j]) {
                    vertical[i][j] = vertical[i-1][j] + 1;
                    if(vertical[i][j] >= 3) {
                        boardDirty = true;
                    }
                }
                if(j > 0 && board[i][j] == board[i][j-1]) {
                    horizontal[i][j] = horizontal[i][j-1] + 1;
                    if(horizontal[i][j] >= 3) {
                        boardDirty = true;
                    }
                }
            }
        }
        
        vector<int> zeros(board[0].size(),0);
        
        if(boardDirty) {
            // consolidate positions to squash
            for(int i = board.size()-1 ; i >= 0 ; i--) {
                for(int j = board[i].size()-1 ; j >= 0 ; j--) {
                    int tempv = vertical[i][j], temph = horizontal[i][j];
                    if(tempv >= 3) {
                        zeros[j] += tempv;
                        for(int k=0 ; k < tempv ; k++) {
                          board[i-k][j] = 0; 
                          vertical[i-k][j] = 0;
                        } 
                    }
                    
                    if(temph >= 3) {
                        for(int k=0 ; k < temph ; k++){
                          if(vertical[i][j-k] < 3) 
                              zeros[j-k] += 1;
                          board[i][j-k] = 0; 
                          horizontal[i][j-k] = 0; 
                        } 
                    }                    
                }
            }
            
    
            // crush candies
            int n = board.size();
            for(int j=0 ; j < board[0].size(); j++) {
                int z = n-1, pos = zeros[j];
                for(int i=n-1 ; i >= 0 ; i--) {
                    if(board[i][j] != 0) {
                        board[z][j] = board[i][j];
                        if(z != i) board[i][j] = 0;
                        z--;
                    }
                }
            }            
        }   
        
        if(boardDirty)
            crush(board);
    }
    

    };

    '''


Log in to reply
 

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