Candy Crush
What is this problem about?
The Candy Crush interview question asks you to implement the core logic of the popular mobile game. You are given a 2D grid of integers representing different types of candies. You need to:
- Identify and "crush" all horizontal or vertical sequences of 3 or more identical candies.
- After crushing (setting values to 0), let candies "drop" down to fill the empty spaces.
- Repeat the process until no more candies can be crushed.
This Candy Crush coding problem is a comprehensive simulation task involving matrix traversal and gravity logic.
Why is this asked in interviews?
Companies like Uber and Bloomberg use this to test a candidate's ability to manage complex state transitions in a 2D environment. It evaluates your skills in matrix manipulation, coordinate system management, and your ability to write modular code. It’s also a test of patience and attention to detail regarding boundary conditions.
Algorithmic pattern used
This follows the Array, Matrix, Two Pointers, Simulation interview pattern.
- Crushing Phase: Iterate through the grid. Use sets or marking to flag every candy that is part of a 3+ sequence horizontally or vertically.
- Gravity Phase: For each column, use a two-pointer approach to move all non-zero candies to the bottom and fill the top with zeros.
- Loop: Wrap these phases in a while loop that continues as long as at least one candy was crushed in the previous turn.
Example explanation
Grid:
1 1 1
2 3 4
5 6 7
- Row 0 has three '1's. Mark them for crushing.
- Set them to 0.
- Gravity: Column 0, 1, and 2 all have a 0 at the top. The '2', '3', '4' stay where they are (since 0 is above them).
If it were:
2 3 4
1 1 1
5 6 7
The '2', '3', '4' would "drop" into Row 1 after the '1's are crushed.
Common mistakes candidates make
- Crushing mid-turn: Changing candies to 0 while still checking for other sequences. This can break sequences that should have been crushed (e.g., a T-shape). You must find all crushable candies first, then set them all to 0.
- Inefficient dropping: Using a nested loop to "bubble" every candy down, which is O(R^2 * C). The two-pointer approach is O(R * C).
- Diagonal checks: Adding diagonal crushing logic when the problem usually only specifies horizontal and vertical.
Interview preparation tip
Break simulation problems into distinct functions (e.g., findCrushable, applyGravity). This makes the code easier to debug and demonstrates good software engineering practices to the interviewer.
