Watch 10 video solutions for Where Will the Ball Fall, a medium level problem involving Array, Matrix, Simulation. This walkthrough by codestorywithMIK has 6,455 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.
Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.
1.-1.We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.
Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.
Example 1:
Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]] Output: [1,-1,-1,-1,-1] Explanation: This example is shown in the photo. Ball b0 is dropped at column 0 and falls out of the box at column 1. Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1. Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0. Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0. Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.
Example 2:
Input: grid = [[-1]] Output: [-1] Explanation: The ball gets stuck against the left wall.
Example 3:
Input: grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]] Output: [0,1,2,3,4,-1]
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 100grid[i][j] is 1 or -1.Problem Overview: You drop one ball from the top of each column in a grid. Every cell contains a diagonal board that redirects the ball either left or right. Some configurations form a V-shape that traps the ball. The task is to simulate the movement and return the column where each ball exits, or -1 if it gets stuck.
Approach 1: Depth-First Search Simulation (O(m * n) time, O(m) space)
Treat each ball drop as a path traversal through the matrix. From column c in row r, read the diagonal direction grid[r][c]. A value of 1 moves the ball to c + 1, while -1 moves it to c - 1. Before moving, check two failure conditions: the next column is outside the grid, or the adjacent cell forms a V-shape (grid[r][c] != grid[r][next]). Either case means the ball gets stuck. If the move is valid, recursively continue to the next row. When the row index reaches m, the ball exits successfully.
This approach models the process directly and is easy to reason about. Each recursive call represents the ball moving one row down. Since a ball can pass through at most m rows and there are n starting columns, the total runtime is O(m * n). Recursion depth gives O(m) auxiliary space.
Approach 2: Iterative Simulation Using Loops (O(m * n) time, O(1) space)
Instead of recursion, simulate the ball movement with loops. For each starting column, track the current column index and iterate row by row. Read the direction from the grid and compute the next column. If the next column is out of bounds or forms a V-shaped block with the adjacent cell, stop and record -1. Otherwise update the column pointer and continue to the next row.
This method uses simple iteration over the array-based grid and avoids recursion overhead. The key observation is that the ball always moves exactly one row per step, making the process deterministic. Each ball requires scanning at most m rows, giving the same O(m * n) runtime but with O(1) extra memory. The logic is a classic simulation pattern where you repeatedly apply movement rules until termination.
Recommended for interviews: The iterative simulation is the expected solution. It keeps the logic explicit, avoids recursion, and runs in optimal O(m * n) time with constant space. Implementing DFS first can help demonstrate understanding of the movement rules, but interviewers typically prefer the loop-based simulation because it is simpler and more memory efficient.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search Simulation | O(m * n) | O(m) | Useful for modeling the ball path recursively or when demonstrating traversal logic clearly. |
| Iterative Simulation Using Loops | O(m * n) | O(1) | Best general solution. Minimal memory usage and straightforward implementation for interviews. |