Match Three Game

labuladongOriginalAbout 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

// 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;
        }
    }
}