Match Three Game
OriginalAbout 619 words
In the Match-Three game, players can swap blocks. When three or more of the same blocks are connected in a row or column, they will be eliminated. Then, blocks above will fall down to fill the empty spaces.
In the Match-Three game on this site, please implement the applyGravity
function to complete the logic of blocks falling down. You should update the board
array in place and avoid inserting or deleting elements in the middle of the array.
Explanation
This problem mainly tests the Two Pointer Array Techniques, similar to the moveZeroes
solution. You can use the fast and slow pointer method to move all the zeros in each column to the top.
Here is a reference solution:
java
// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding
class Solution {
public void applyGravity(int[][] board) {
if (board == null || board.length == 0) {
return;
}
int rows = board.length;
int cols = board[0].length;
// Traverse each column
for (int col = 0; col < cols; col++) {
// Initialize fast and slow pointers
int slow = rows - 1;
int fast = rows - 1;
while (fast >= 0) {
if (board[fast][col] != 0) {
// Move non-zero element to slow pointer position
board[slow][col] = board[fast][col];
slow--;
}
fast--;
}
// Fill remaining top positions with zeros
for (int i = 0; i <= slow; i++) {
board[i][col] = 0;
}
}
}
}
cpp
// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding
class Solution {
public:
void applyGravity(vector<vector<int>>& board) {
int rows = board.size();
int cols = board[0].size();
// Traverse each column
for (int col = 0; col < cols; col++) {
// Initialize fast and slow pointers
int slow = rows - 1;
int fast = rows - 1;
while (fast >= 0) {
if (board[fast][col] != 0) {
// Move non-zero element to slow pointer position
board[slow][col] = board[fast][col];
slow--;
}
fast--;
}
// Fill remaining top positions with zeros
for (int i = 0; i <= slow; i++) {
board[i][col] = 0;
}
}
}
};
python
# The game panel only supports submitting JavaScript code
# The code in other languages is only for understanding
class Solution:
def applyGravity(self, board: List[List[int]]) -> None:
if not board or not board[0]:
return
rows = len(board)
cols = len(board[0])
# Traverse each column
for col in range(cols):
# Initialize fast and slow pointers
slow = rows - 1
fast = rows - 1
while fast >= 0:
if board[fast][col] != 0:
# Move non-zero element to slow pointer position
board[slow][col] = board[fast][col]
slow -= 1
fast -= 1
# Fill remaining top positions with zeros
for i in range(slow + 1):
board[i][col] = 0
go
// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding
func applyGravity(board [][]int) {
rows := len(board)
cols := len(board[0])
// Traverse each column
for col := 0; col < cols; col++ {
// Initialize fast and slow pointers
slow := rows - 1
fast := rows - 1
for fast >= 0 {
if board[fast][col] != 0 {
// Move non-zero element to slow pointer position
board[slow][col] = board[fast][col]
slow--
}
fast--
}
// Fill remaining top positions with zeros
for i := 0; i <= slow; i++ {
board[i][col] = 0
}
}
}
javascript
function applyGravity(board) {
const rows = board.length;
const cols = board[0].length;
// Traverse each column
for (let col = 0; col < cols; col++) {
// Initialize fast and slow pointers
let slow = rows - 1;
let fast = rows - 1;
while (fast >= 0) {
if (board[fast][col] !== 0) {
// Move non-zero element to slow pointer position
board[slow][col] = board[fast][col];
slow--;
}
fast--;
}
// Fill remaining top positions with zeros
for (let i = 0; i <= slow; i++) {
board[i][col] = 0;
}
}
}