Where Will the Ball Fall

Where Will the Ball Fall

What is this problem about?

In this problem, you have a 2D grid representing a box filled with diagonal boards. Each cell either has a board tilting right (value 1) or tilting left (value -1). You drop several balls from the top of the box and need to determine where each ball ends up at the bottom. A ball can get stuck if it hits a "V" shape (two boards pointing at each other) or if it hits a wall.

Why is this asked in interviews?

Google frequently asks this to test Matrix Simulation skills. It requires careful navigation of 2D indices and the ability to model a physical process. The key is to track the ball's position (row, col) and determine the next col based on the current board's direction and the adjacent board's direction.

Algorithmic pattern used

The pattern is Simulation or DFS. For each ball, you start at row 0 and iterate down to the last row. In each step, you check if the ball can move to the next row by comparing the current cell grid[r][c] with the neighbor it's being pushed toward. If they don't match (one is 1, the other is -1), the ball is stuck.

Example explanation

Grid: [[1, 1, -1]]. Ball dropped at column 0.

1. grid[0][0] is 1 (tilts right).
2. Check the neighbor to the right: grid[0][1] is also 1.
3. The ball moves to row 1, col 1. Ball dropped at column 2.
4. grid[0][2] is -1 (tilts left).
5. Check neighbor to the left: grid[0][1] is 1.
6. Stuck! The boards form a "V" shape (1 and -1 meet). Ball returns -1.

Common mistakes candidates make

• Boundary Checks: Forgetting to check if the ball hits the left wall (col < 0) or right wall (col >= N) after being tilted.
• Stuck Condition: Only checking the current cell and not the one it's moving into.
• Logic for -1: Mixing up the directions. A 1 moves you to col + 1, a -1 moves you to col - 1.

Interview preparation tip

For matrix simulation problems, always use a single loop to track the ball's progress through the rows. If at any point the "stuck" condition is met, break early and return -1. This keeps the code clean and avoids nested complexity.