Leetcode 723. Candy Crush
Problem Explanation
The given problem is a game logic for candy crush. We are provided with a 2D board that represents a grid of candy. Different positive integers in the board represent different types of candies, and a value of 0 represents that a particular cell is empty.
Our task is to restore the board to a stable state by crushing candies that have at least 3 of the same type in a row, either vertically or horizontally. Once the candies are crushed, they leave an empty space behind, and other candies may fall down into this space. This process should be repeated until there are no more candies that can be crushed.
For example:
1 2 3Input: 4board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]] 5 6Output: 7[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]
In the given input board, there are candies (5, 1, 2) that are repeated three times continuously in a row either vertically or horizontally. So, we crush these candies. After crushing the candies, the candies on top of these crushed candies will fall down. We keep doing this until there are no more candies to be crushed.
Approach of the solution
The given solution is implemented using a flag controlled loop and matrix traversal.
- The
whileloop runs until there are no more candies to be crushed, detected by thehaveCrushesflag. - For each cell of the grid, we check if there are at least three candies of the same type either vertically or horizontally. If there are, we mark them for crush by assigning them negative values, and set the
haveCrushesflag totrue. - After iterating over all cells, if
haveCrushesistrue, we crush the candies marked for crush and shift the remaining candies downwards. - We repeat the whole process until
haveCrushesisfalse, i.e., there are no more candies to be crushed.
Python Solution
1 2python 3class Solution: 4 def candyCrush(self, board): 5 rows = len(board) 6 cols = len(board[0]) 7 crush = False 8 9 # Check horizontal lines 10 for r in range(rows): 11 for c in range(cols - 2): 12 if abs(board[r][c]) == abs(board[r][c + 1]) == abs(board[r][c + 2]) != 0: 13 board[r][c] = board[r][c + 1] = board[r][c + 2] = -abs(board[r][c]) 14 crush = True 15 16 # Check vertical lines 17 for r in range(rows - 2): 18 for c in range(cols): 19 if abs(board[r][c]) == abs(board[r + 1][c]) == abs(board[r + 2][c]) != 0: 20 board[r][c] = board[r + 1][c] = board[r + 2][c] = -abs(board[r][c]) 21 crush = True 22 23 # Move cells down 24 for c in range(cols): 25 idx = rows - 1 26 for r in reversed(range(rows)): 27 if board[r][c] > 0: 28 board[idx][c] = board[r][c] 29 idx -= 1 30 for r in range(idx + 1): 31 board[r][c] = 0 32 33 return self.candyCrush(board) if crush else board
Java Solution
1 2java 3class Solution { 4 public int[][] candyCrush(int[][] board) { 5 int N = board.length, M = board[0].length; 6 boolean[][] todo = new boolean[N][M]; 7 for (int r = 0; r < N; ++r) 8 for (int c = 0; c + 2 < M; ++c) 9 if (Math.abs(board[r][c]) == Math.abs(board[r][c+1]) && 10 Math.abs(board[r][c]) == Math.abs(board[r][c+2]) && 11 board[r][c] != 0) 12 todo[r][c] = todo[r][c+1] = todo[r][c+2] = true; 13 14 for (int r = 0; r + 2 < N; ++r) 15 for (int c = 0; c < M; ++c) 16 if (Math.abs(board[r][c]) == Math.abs(board[r+1][c]) && 17 Math.abs(board[r][c]) == Math.abs(board[r+2][c]) && 18 board[r][c] != 0) 19 todo[r][c] = todo[r+1][c] = todo[r+2][c] = true; 20 21 for (int r = 0; r < N; ++r) 22 for (int c = 0; c < M; ++c) 23 if (todo[r][c]) board[r][c] = 0; 24 25 for (int c = 0; c < M; ++c) { 26 int wr = N - 1; 27 for (int r = N-1; r >= 0; --r) 28 if (board[r][c] != 0) 29 board[wr--][c] = board[r][c]; 30 while (wr >= 0) 31 board[wr--][c] = 0; 32 } 33 34 if (isStable(board, N, M)) return board; 35 return candyCrush(board); 36 } 37 38 public boolean isStable(int[][] board, int N, int M) { 39 for (int r = 0; r < N; ++r) { 40 for (int c = 0; c + 2 < M; ++c) { 41 if (Math.abs(board[r][c]) == Math.abs(board[r][c+1]) && 42 Math.abs(board[r][c]) == Math.abs(board[r][c+2]) && 43 board[r][c] != 0) 44 return false; 45 } 46 } 47 48 for (int r = 0; r + 2 < N; ++r) { 49 for (int c = 0; c < M; ++c) { 50 if (Math.abs(board[r][c]) == Math.abs(board[r+1][c]) && 51 Math.abs(board[r][c]) == Math.abs(board[r+2][c]) && 52 board[r][c] != 0) 53 return false; 54 } 55 } 56 57 return true; 58 } 59}
Javascript Solution
1 2javascript 3var candyCrush = function(board) { 4 const m = board.length; 5 const n = board[0].length; 6 let todo = false; 7 for (let r = 0; r < m; ++r) 8 for (let c = 0; c + 2 < n; ++c) 9 if (Math.abs(board[r][c]) === Math.abs(board[r][c+1]) && Math.abs(board[r][c]) === Math.abs(board[r][c+2]) && board[r][c] !== 0) { 10 board[r][c] = board[r][c+1] = board[r][c+2] = -Math.abs(board[r][c]); 11 todo = true; 12 } 13 for (let r = 0; r + 2 < m; ++r) 14 for (let c = 0; c < n; ++c) 15 if (Math.abs(board[r][c]) === Math.abs(board[r+1][c]) && Math.abs(board[r][c]) === Math.abs(board[r+2][c]) && board[r][c] !== 0) { 16 board[r][c] = board[r+1][c] = board[r+2][c] = -Math.abs(board[r][c]); 17 todo = true; 18 } 19 for (let c = 0; c < n; ++c) { 20 let wr = m - 1; 21 for (let r = m-1; r >= 0; --r) 22 if (board[r][c] > 0) 23 board[wr--][c] = board[r][c]; 24 for (let r = wr; r >= 0; --r) 25 board[r][c] = 0; 26 } 27 return todo ? candyCrush(board) : board; 28};
C# Solution
1 2csharp 3public int[][] CandyCrush(int[][] board) { 4 bool found = true; 5 while (found) 6 { 7 found = false; 8 for (int i = 0; i < board.Length; i++) 9 for (int j = 0; j < board[0].Length - 2; j++) 10 if (Math.Abs(board[i][j])>0 && Math.Abs(board[i][j])==Math.Abs(board[i][j+1]) && Math.Abs(board[i][j])==Math.Abs(board[i][j+2])) 11 { 12 found = true; 13 int index = j; 14 while (index<board[0].Length && Math.Abs(board[i][j])==Math.Abs(board[i][index])) 15 board[i][index++] = -Math.Abs(board[i][j]); 16 } 17 for (int i = 0; i < board[0].Length; i++) 18 for (int j = 0; j < board.Length - 2; j++) 19 if (Math.Abs(board[j][i])>0 && Math.Abs(board[j][i])==Math.Abs(board[j+1][i]) && Math.Abs(board[j][i])==Math.Abs(board[j+2][i])) 20 { 21 found = true; 22 int index = j; 23 while (index<board.Length && Math.Abs(board[j][i])==Math.Abs(board[index][i])) 24 board[index++][i] = -Math.Abs(board[j][i]); 25 } 26 27 if (found) 28 { 29 for (int i = 0; i < board[0].Length; i++) 30 { 31 int storeIndex = board.Length-1; 32 for (int j = board.Length - 1; j >= 0; j--) 33 if (board[j][i]>=0) 34 board[storeIndex--][i] = board[j][i]; 35 for (int j = storeIndex; j >= 0; j--) 36 board[j][i]=0; 37 } 38 } 39 } 40 return board; 41}
C++ Solution
1 2c++ 3class Solution { 4public: 5 vector<vector<int>> candyCrush(vector<vector<int>>& board) { 6 if(board.empty() || board[0].empty()) return board; 7 int m = board.size(), n = board[0].size(); 8 bool done = false; 9 while(!done) { 10 done = true; 11 for(int i = 0; i < m; i++) { 12 for(int j = 0; j < n; j++) { 13 int val = abs(board[i][j]); 14 if(val==0) continue; 15 if(j < n-2 && abs(board[i][j+1])==val && abs(board[i][j+2])==val) { 16 int ind = j; 17 while(ind<n && abs(board[i][ind])==val) board[i][ind++] = -val; 18 done = false; 19 } 20 if(i < m-2 && abs(board[i+1][j])==val && abs(board[i+2][j])==val) { 21 int ind = i; 22 while(ind<m && abs(board[ind][j])==val) board[ind++][j] = -val; 23 done = false; 24 } 25 } 26 } 27 if(done) break; 28 for(int j = 0; j < n; j++) { 29 int storeInd = m-1; 30 for(int i = m-1; i >= 0; i--) { 31 if(board[i][j] > 0) board[storeInd--][j] = board[i][j]; 32 } 33 for(int k = storeInd; k >= 0; k--) board[k][j]=0; 34 } 35 } 36 return board; 37 } 38};
The solutions in different programming languages follow the same approach. The candies are marked for crush using negative values. Then, they are crushed and the remaining candies are moved down. This is repeated until there are no more candies to be crushed.## Analyzing the Solutions
The Python solution uses a flag-controlled while loop, that continues until there are no longer candies to be crushed. The main part of the solution involves two steps. First, it traverses through the board marking matching candies for crush and setting the crush flag to true. Second, it crushes the candies and moves the remaining candies down. The traversal happens in both horizontal and vertical directions. When there are no more candies to be crushed, the loop terminates and provides the updated board as the final result.
The Java solution follows a similar approach as the Python one. It also uses a flag-controlled while loop, which continues until there are no matching candies left in the board to be crushed. One key difference is that it uses an additional boolean 2D array to track the positions of the candies that have to be crushed. This serves the same purpose as marking candies for crush in the Python solution. Then, using this array, it crushes the candies and moves other candies downwards just like in the Python solution.
The JavaScript solution is also pretty similar to the Python one. The only key difference is that it uses the recursion technique to keep crushing candies until no more matching candies are left on the board. It also uses flags and a while loop to mark candies to be crushed and to move candies downward after crushing.
The C# and C++ solutions use the same algorithm, they use a while loop to keep repeating the process until there are no more candies to be crushed. They also use two for loops to find and mark candies to be crushed in the x and y directions. Moreover, if any candies are found to be crushed, they move the other candies to fill the empty slots.
In conclusion, all solutions use a flag-controlled while loop combined with matrix traversal in both directions to solve the problem. All solutions are efficient and should work well for a reasonable board size. The use of recursion, extra boolean arrays, or negative marking depends upon the programming language and personal preference but does not significantly change the complexity of the solution.
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.