PROBLEM DESCRIPTION
Given an m x n integer array board representing the grid of candy where board[i][j] represents the type of candy. A value of board[i][j] == 0 represents that the cell is empty.
The given board represents the state of the game following the player’s move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:
- If three or more candies of the same type are adjacent vertically or horizontally, crush them all at the same time - these positions become empty.
- After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. No new candies will drop outside the top boundary.
- After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps.
- If there does not exist more candies that can be crushed (i.e., the board is stable), then return the current board.
You need to perform the above rules until the board becomes stable, then return the stable board.
SOLUTION
- First we mark all the positions which should be removed in the current matrix
- We can do this row wise first. Whenever we see at least three elements with same value, mark them. We can change the value to -ve to mark them.
- Do the same thing while traversing column wise
- Once all of them are marked, go to each column and start filling up the position from bottom to top. We can use some pointer pos to start from bottom most position. Use another variable starting from bottom to top to get the next element which is greater than 0 (which means that it is not supposed to be removed). When we get such an element, put it in position pos and move pos one cell above it. Once all possible values are filled, mark rest of the elements from [pos,0] as 0.
- After this, the same steps need to be repeated. If we did not find any triplet which can be removed from the matrix, we have reached a stable state. In that case we can simply return the board. We can use a boolean variable to check if there was at least one triplet which could be removed.
- If the state is not stable, which means that there is at least one triplet which can be removed, then we can recursively call our main method as this will act like a sub-problem.
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class Solution {
public int[][] candyCrush(int[][] board) {
int n = board.length; // Number of rows in the board
int m = board[0].length; // Number of columns in the board
boolean stable = true; // A flag to determine if the board is stable after a pass
// Mark and crush candy in rows
for(int r=0; r<n; r++){
//window for the triplet
int left=0;
int right=2;
//while there are more rows left
while(right<m){
int x = Math.abs(board[r][left]); // Get the absolute value of the candy at the leftmost position in the window
if(x == 0){
left++; right++; continue; // If it's empty, move the window
}
boolean matchFound = true;
// Check if all candies in the window have the same type
for(int c=left+1; c<=right; c++){
if(Math.abs(board[r][c]) != x){
matchFound = false;
}
}
//we found a triplet which should be removed
if(matchFound){
stable = false; // We found a match, so the board is not stable
// Crush the candies in the window by marking them as negative values
for(int c=left; c<=right; c++){
board[r][c] = -x;
}
}
left++; right++;
}
}
// Mark and crush candy in columns
for(int c=0; c<m; c++){
// vertical window for the triplet
int top=0;
int bottom=2;
// while we have more columns
while(bottom<n){
int x = Math.abs(board[top][c]); // Get the absolute value of the candy at the topmost position in the window
if(x == 0){
top++; bottom++; continue; // If it's empty, move the window
}
boolean matchFound = true;
// Check if all candies in the window have the same type
for(int r=top+1; r<=bottom; r++){
if(Math.abs(board[r][c]) != x){
matchFound = false;
}
}
// found a triplet which should be removed
if(matchFound){
stable = false; // We found a match, so the board is not stable
// Crush the candies in the window by marking them as negative values
for(int r=top; r<=bottom; r++){
board[r][c] = -x;
}
}
top++; bottom++;
}
}
if(stable){
return board; // If the board is stable, return the current state
}
rearrange(board); // Otherwise, rearrange the board to drop candies
return candyCrush(board); // Recursively repeat the process until the board becomes stable
}
// Rearrange the board to drop candies
public void rearrange(int[][] board){
int n = board.length;
int m = board[0].length;
for(int c=0; c<m; c++){
int pos = n-1;
for(int r=n-1; r>=0; r--){
if(board[r][c] > 0){
board[pos][c] = board[r][c]; // Move candies down to needed position
pos--; // move to next position where the next valid value can be added
}
}
// Mark the rest of the column as empty (0)
for(int r=pos; r>=0; r--){
board[r][c] = 0;
}
}
}
}