Candy Crush

Medium Arrays & Hashing Simulation Original on LeetCode

Reported atPinterestRubrik

Candy Crush is a medium arrays & hashing problem solved with the simulation pattern. The best approach, optimal (in-place marking with negative values), runs in O((m · n)²) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (mark grid, rebuild columns) up.

Problem

You are given an m x n grid board for a candy-matching game. A positive value is the type of the candy in that cell, and 0 means the cell is empty. Make the board stable by repeating these rules:

  1. Find every candy that belongs to a horizontal or vertical line of three or more equal candies. Crush all of them at the same time (set those cells to 0).
  2. Candies then fall straight down within their column until they rest on another candy or the bottom. No new candies appear from the top.
  3. Repeat until no line of three or more equal candies is left.

Return the stable board.

Examples

Example 1

Input
board = [[1, 2, 3], [1, 4, 5], [1, 2, 3]]
Output
[[0, 2, 3], [0, 4, 5], [0, 2, 3]]
Why
The three 1s in the first column are crushed. Nothing sits above them, so the column just becomes empty.

Example 2

Input
board = [[5, 1, 6], [2, 2, 2], [5, 3, 6], [5, 1, 6]]
Output
[[0, 0, 0], [0, 1, 0], [0, 3, 0], [0, 1, 0]]
Why
The row of 2s is crushed first. The 5 and the 6 above it fall down and complete vertical runs of three, which are crushed in the next round.

Example 3

Input
board = [[1, 2, 1], [2, 1, 2], [1, 2, 1]]
Output
[[1, 2, 1], [2, 1, 2], [1, 2, 1]]
Why
No three equal candies are in a line, so the board is already stable.

Constraints

  • 3 <= m, n <= 50 where the board is m x n
  • 0 <= board[i][j] <= 2000 (0 means an empty cell)

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (mark grid, rebuild columns)O((m · n)²)O(m · n)
Optimal (in-place marking with negative values)O((m · n)²)O(1)

1Brute force (mark grid, rebuild columns)

TimeO((m · n)²)Each round is O(m · n) and every round except the last removes at least 3 candies, so there are at most m · n / 3 rounds.
SpaceO(m · n)The boolean grid and the per-column lists.

Simulate round by round. In each round use a separate boolean grid to mark every cell that belongs to a horizontal or vertical window of three equal non-zero candies. If nothing is marked, stop. Otherwise clear the marked cells and rebuild each column by collecting its candies from the bottom up.

  1. Create a fresh boolean grid crush of size m x n.
  2. For every horizontal and vertical window of three equal non-zero values, mark the three cells.
  3. If nothing was marked, return the board.
  4. Set marked cells to 0; for every column, gather the non-zero values bottom-up into a list and write them back from the bottom, padding with 0.
class Solution {
    public int[][] candyCrush(int[][] board) {
        int m = board.length, n = board[0].length;
        while (true) {
            boolean[][] crush = new boolean[m][n];
            boolean any = false;
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    int v = board[r][c];
                    if (v == 0) continue;
                    if (c + 2 < n && board[r][c + 1] == v && board[r][c + 2] == v) {
                        crush[r][c] = crush[r][c + 1] = crush[r][c + 2] = true;
                        any = true;
                    }
                    if (r + 2 < m && board[r + 1][c] == v && board[r + 2][c] == v) {
                        crush[r][c] = crush[r + 1][c] = crush[r + 2][c] = true;
                        any = true;
                    }
                }
            }
            if (!any) return board;
            for (int c = 0; c < n; c++) {
                List<Integer> kept = new ArrayList<>();
                for (int r = m - 1; r >= 0; r--) {
                    if (!crush[r][c] && board[r][c] != 0) kept.add(board[r][c]);
                }
                for (int r = m - 1, k = 0; r >= 0; r--, k++) {
                    board[r][c] = k < kept.size() ? kept.get(k) : 0;
                }
            }
        }
    }
}

2Optimal (in-place marking with negative values)

TimeO((m · n)²)Each round is O(m · n) and there are at most m · n / 3 rounds that change the board.
SpaceO(1)The marks live in the board itself; only a few indices are used.

Same rounds, but no extra grid: mark a cell for crushing by making its value negative. Comparisons use absolute values, so a cell that is already marked still counts for the other direction. Gravity is a two-pointer pass per column that copies positive values down and fills the top with 0.

  1. Scan every horizontal and vertical window of three; if the three absolute values are equal and non-zero, set all three to -value.
  2. If nothing was marked, stop.
  3. For each column, let write = m - 1; for r from m - 1 up to 0, if board[r][c] > 0 copy it to board[write--][c].
  4. Set the remaining cells above write to 0 and start the next round.
class Solution {
    public int[][] candyCrush(int[][] board) {
        int m = board.length, n = board[0].length;
        boolean changed = true;
        while (changed) {
            changed = 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;
                        changed = 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;
                        changed = true;
                    }
                }
            }
            if (!changed) break;
            for (int c = 0; c < n; c++) {
                int write = m - 1;
                for (int r = m - 1; r >= 0; r--) {
                    if (board[r][c] > 0) board[write--][c] = board[r][c];
                }
                while (write >= 0) board[write--][c] = 0;
            }
        }
        return board;
    }
}

Edge cases to test

  • A board that is already stable
  • A candy that is part of a horizontal and a vertical run at once (an L or T shape)
  • Runs longer than three
  • Chain reactions that need several rounds
  • Empty cells (0) in a line must never be crushed

Hints

Hint 1

Crushing must be simultaneous: first find every cell to crush, only then remove them.

Hint 2

Checking each window of three cells horizontally and vertically finds every run of length three or more.

Hint 3

Gravity per column is a two-pointer pass from the bottom: copy surviving candies down, then fill the rest with 0.

FAQ

What is the best time complexity for Candy Crush?

Optimal (in-place marking with negative values) runs in O((m · n)²) time and O(1) extra space. Each round is O(m · n) and there are at most m · n / 3 rounds that change the board.

Which pattern does Candy Crush use?

It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).

Is there a brute force solution for Candy Crush?

Yes. Brute force (mark grid, rebuild columns) takes O((m · n)²) time and O(m · n) space. Simulate round by round.

Which edge cases should I test for Candy Crush?

A board that is already stable; A candy that is part of a horizontal and a vertical run at once (an L or T shape); Runs longer than three; Chain reactions that need several rounds; Empty cells (0) in a line must never be crushed.