Clean O(MN) solution each iteration


  • 0
    K
    class Solution(object):
        def candyCrush(self, board):
            def scanHorizontally(to_crush):
                starts = [0] * M # Scan horizontally from each row starting from index 0
                for i in range(M):
                    while starts[i] < N:
                        cnt = 0
                        start = starts[i]
                        while starts[i] < N:
                            if board[i][start] == 0 or board[i][start] != board[i][starts[i]]:
                                break
                            cnt += 1
                            starts[i] += 1
                        if cnt == 0: # Skip 0
                            starts[i] += 1
                        elif cnt >= 3:
                            for k in range(start, starts[i]):
                                to_crush.add((i, k))
            def scanVertically(to_crush):
                starts = [0] * N # Scan horizontally from each column starting from index 0
                for j in range(N):
                    while starts[j] < M:
                        cnt = 0
                        start = starts[j]
                        while starts[j] < M:
                            if board[start][j] == 0 or board[start][j] != board[starts[j]][j]:
                                break
                            cnt += 1
                            starts[j] += 1
                        if cnt == 0: # Skip 0
                            starts[j] += 1
                        elif cnt >= 3:
                            for k in range(start, starts[j]):
                                to_crush.add((k, j))
            def crush(to_crush):
                for i, j in to_crush:
                    board[i][j] = 0
            def drop(): # Similar to move zeros
                for j in range(N):
                    idx = M - 1
                    for i in range(M - 1, -1, -1):
                        if board[i][j] != 0:
                            board[idx][j] = board[i][j]
                            idx -= 1
                    for i in range(idx, -1, -1):
                        board[i][j] = 0
    
            M = len(board)
            N = len(board[0])
            while True:
                to_crush = set()
                scanHorizontally(to_crush)
                scanVertically(to_crush)
                if not to_crush:
                    break
                crush(to_crush)
                drop()
            return board
    

Log in to reply
 

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