# 723. Candy Crush

• Time: $O(m^2n^2)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public: vector> candyCrush(vector>& board) { const int m = board.size(); const int n = board[0].size(); bool haveCrushes = true; while (haveCrushes) { haveCrushes = false; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { const int val = abs(board[i][j]); if (val == 0) continue; // crush vertical candies if (j + 2 < n && abs(board[i][j + 1]) == val && abs(board[i][j + 2]) == val) { haveCrushes = true; for (int k = j; k < j + 3; ++k) board[i][k] = -val; } // crush horizontal candies if (i + 2 < m && abs(board[i + 1][j]) == val && abs(board[i + 2][j]) == val) { haveCrushes = true; for (int k = i; k < i + 3; ++k) board[k][j] = -val; } } if (haveCrushes) { // for each column, drop candies for (int j = 0; j < n; ++j) { int nextIndex = m - 1; for (int i = m - 1; i >= 0; --i) if (board[i][j] > 0) board[nextIndex--][j] = board[i][j]; // set board[0..nextIndex][j] to 0s for (int i = nextIndex; i >= 0; --i) board[i][j] = 0; } } } return board; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public int[][] candyCrush(int[][] board) { final int m = board.length; final int n = board[0].length; boolean haveCrushes = true; while (haveCrushes) { haveCrushes = false; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { final int val = Math.abs(board[i][j]); if (val == 0) continue; // crush vertical candies if (j + 2 < n && Math.abs(board[i][j + 1]) == val && Math.abs(board[i][j + 2]) == val) { haveCrushes = true; for (int k = j; k < j + 3; ++k) board[i][k] = -val; } // crush horizontal candies if (i + 2 < m && Math.abs(board[i + 1][j]) == val && Math.abs(board[i + 2][j]) == val) { haveCrushes = true; for (int k = i; k < i + 3; ++k) board[k][j] = -val; } } if (haveCrushes) { // for each column, drop candies for (int j = 0; j < n; ++j) { int nextIndex = m - 1; for (int i = m - 1; i >= 0; --i) if (board[i][j] > 0) board[nextIndex--][j] = board[i][j]; // set board[0..nextIndex][j] to 0s for (int i = nextIndex; i >= 0; --i) board[i][j] = 0; } } } return board; } }