Candy Crush Grid Matching and Gravity

Problem Overview

You are given an m x n grid of non-negative integers. A positive value represents a candy type, and 0 represents an empty cell. A match is any horizontal or vertical run of at least three consecutive candies of the same type. After identifying all matches, apply gravity to make all candies above a fall into the empty cells below.

Problem Statement

Given a grid of size m x n, where each cell contains a candy type represented by a non-negative integer, and 0 represents an empty cell. Find all matches of at least three consecutive candies in the same row or column, and then apply gravity to make candies above fall into empty cells below.

Constraints

• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 1000

Examples

1. Input: grid = [ [110, 5, 112, 113, 114], [210, 5, 213, 214, 215], [310, 5, 313, 314, 315], [410, 5, 413, 414, 415], [510, 5, 513, 514, 515], [610, 5, 613, 614, 615] ] Output: [ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 1], [0, 0, 2, 2, 2], [0, 0, 3, 3, 3], [0, 0, 4, 4, 4] ]

2. Input: grid = [ [1, 1, 0, 0], [0, 1, 1, 1], [0, 0, 2, 2] ] Output: [ [1, 1, 0, 0], [0, 1, 1, 1], [1, 1, 2, 2] ]

Hints

• Use two nested loops to iterate through each cell in the grid.
• Check for matches in horizontal and vertical directions.
• After identifying matches, apply gravity to shift candies down.
• Consider edge cases where matches span multiple rows or columns.

Solution

`python def candyCrush(grid): rows, cols = len(grid), len(grid[0]) zero_pos = []

# Step 1: Identify matches
for r in range(rows):
    for c in range(cols - 2):
        if grid[r][c] != 0 and grid[r][c] == grid[r][c+1] == grid[r][c+2]:
            zero_pos.extend([(r, c), (r, c+1), (r, c+2)])

for c in range(cols):
    for r in range(rows - 2):
        if grid[r][c] != 0 and grid[r][c] == grid[r+1][c] == grid[r+2][c]:
            zero_pos.extend([(r, c), (r+1, c), (r+2, c)])

# Step 2: Apply gravity
for r in range(rows - 1, -1, -1):
    for c in range(cols - 1, -1, -1):
        if grid[r][c] == 0:
            # Find the first non-zero candy below the current position
            for i in range(r + 1, rows):
                if grid[i][c] != 0:
                    grid[r][c] = grid[i][c]
                    grid[i][c] = 0
                    break

return grid

`

This solution first identifies all matches and stores their positions. Then, it applies gravity by shifting candies down to fill empty cells. The function returns the modified grid after applying the candy crush rules.