Candy Crush

medium array matrix simulation

Problem

Given an m x n board of candy values, repeatedly mark any horizontal or vertical run of three or more equal positive cells for crushing, zero them, then let candies fall to fill gaps. Return the board after no more crushes are possible.

Inputboard=[[1,1,1,2],[2,2,2,3]]

Output[[0,0,0,2],[0,0,0,3]]

Both rows are fully crushed; gravity leaves only the trailing column entries.

input

def candyCrush(board):
    m, n = len(board), len(board[0])
    crush = True
    while crush:
        crush = False
        for r in range(m):
            for c in range(n - 2):
                v = abs(board[r][c])
                if v and v == abs(board[r][c+1]) == abs(board[r][c+2]):
                    board[r][c] = board[r][c+1] = board[r][c+2] = -v; crush = True
        for r in range(m - 2):
            for c in range(n):
                v = abs(board[r][c])
                if v and v == abs(board[r+1][c]) == abs(board[r+2][c]):
                    board[r][c] = board[r+1][c] = board[r+2][c] = -v; crush = True
        if crush:
            for c in range(n):
                w = m - 1
                for r in range(m - 1, -1, -1):
                    if board[r][c] > 0: board[w][c] = board[r][c]; w -= 1
                for r in range(w, -1, -1): board[r][c] = 0
    return board

function candyCrush(board) {
  const m = board.length, n = board[0].length;
  let crush = true;
  while (crush) {
    crush = false;
    for (let r = 0; r < m; r++) for (let c = 0; c < n - 2; c++) {
      const v = Math.abs(board[r][c]);
      if (v && v === Math.abs(board[r][c+1]) && v === Math.abs(board[r][c+2])) { board[r][c]=board[r][c+1]=board[r][c+2]=-v; crush = true; }
    }
    for (let r = 0; r < m - 2; r++) for (let c = 0; c < n; c++) {
      const v = Math.abs(board[r][c]);
      if (v && v === Math.abs(board[r+1][c]) && v === Math.abs(board[r+2][c])) { board[r][c]=board[r+1][c]=board[r+2][c]=-v; crush = true; }
    }
    if (crush) for (let c = 0; c < n; c++) {
      let w = m - 1;
      for (let r = m - 1; r >= 0; r--) if (board[r][c] > 0) board[w--][c] = board[r][c];
      for (let r = w; r >= 0; r--) board[r][c] = 0;
    }
  }
  return board;
}

class Solution {
  public int[][] candyCrush(int[][] board) {
    int m = board.length, n = board[0].length; boolean crush = true;
    while (crush) {
      crush = false;
      for (int r = 0; r < m; r++) for (int c = 0; c + 2 < n; c++) {
        int v = Math.abs(board[r][c]);
        if (v != 0 && v == Math.abs(board[r][c+1]) && v == Math.abs(board[r][c+2])) { board[r][c]=board[r][c+1]=board[r][c+2]=-v; crush = true; }
      }
      for (int r = 0; r + 2 < m; r++) for (int c = 0; c < n; c++) {
        int v = Math.abs(board[r][c]);
        if (v != 0 && v == Math.abs(board[r+1][c]) && v == Math.abs(board[r+2][c])) { board[r][c]=board[r+1][c]=board[r+2][c]=-v; crush = true; }
      }
      if (crush) for (int c = 0; c < n; c++) {
        int w = m - 1;
        for (int r = m - 1; r >= 0; r--) if (board[r][c] > 0) board[w--][c] = board[r][c];
        for (int r = w; r >= 0; r--) board[r][c] = 0;
      }
    }
    return board;
  }
}

class Solution {
public:
  vector<vector<int>> candyCrush(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size(); bool crush = true;
    while (crush) {
      crush = false;
      for (int r = 0; r < m; r++) for (int c = 0; c + 2 < n; c++) {
        int v = abs(board[r][c]);
        if (v && v == abs(board[r][c+1]) && v == abs(board[r][c+2])) { board[r][c]=board[r][c+1]=board[r][c+2]=-v; crush = true; }
      }
      for (int r = 0; r + 2 < m; r++) for (int c = 0; c < n; c++) {
        int v = abs(board[r][c]);
        if (v && v == abs(board[r+1][c]) && v == abs(board[r+2][c])) { board[r][c]=board[r+1][c]=board[r+2][c]=-v; crush = true; }
      }
      if (crush) for (int c = 0; c < n; c++) {
        int w = m - 1;
        for (int r = m - 1; r >= 0; r--) if (board[r][c] > 0) board[w--][c] = board[r][c];
        for (int r = w; r >= 0; r--) board[r][c] = 0;
      }
    }
    return board;
  }
};

Explanation

This is a simulation of the game: keep crushing matches and dropping candies until a full round finds nothing to crush. Each round has three phases — mark, then crush, then apply gravity.

To mark runs of three or more, we scan horizontally and vertically and flag matched cells by making them negative (-v). Using the sign as a flag is a neat trick: we compare with abs(...) so an already-marked cell still counts toward another run sharing it, and we never lose the original value yet.

If anything got marked (crush is true), we apply gravity column by column. A write pointer w starts at the bottom; we copy each still-positive cell down into w and move w up, then fill everything above w with zeros. The loop then repeats because new alignments may appear after the fall.

Example: board = [[1,1,1,2],[2,2,2,3]]. Each row is a run of three, so both get crushed to zero, and gravity leaves only the trailing column values: [[0,0,0,2],[0,0,0,3]].

Time: O((mn)^2) Space: O(1)