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.
Use depth-first search (DFS) to simulate the movement of each ball from the top to the bottom, keeping track of the ball's column. If a ball encounters a 'V' shape or hits the wall, it gets stuck. This approach simulates the scenario for each ball individually.
We define a recursive depth-first search function that simulates the ball's journey through the grid. It returns the column at the bottom if the ball falls through, or -1 if it gets stuck. We iterate over each column to drop a ball and compute its result using this DFS function.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for the result and recursion stack.
Utilize nested loops to simulate the motion of each ball iteratively instead of using recursion. It tracks each movement step-by-step across the grid, calculates next positions, transitions to subsequent rows, and monitors for blockages or exits.
The C code iteratively calculates the trajectory for each ball using nested loops without recursion. Starting at each column, the ball’s path is calculated through rows, checking for possible redirections or blockages and finalizing the column or stuck status.
Time Complexity: O(m * n), driven by iterating through all cells.
Space Complexity: O(n), where n stands for the result array requirement.
We can use DFS to simulate the movement of the ball. Design a function dfs(i, j), which represents the column where the ball will fall when it starts from row i and column j. The ball will get stuck in the following cases:
If any of the above conditions are met, we can determine that the ball will get stuck and return -1. Otherwise, we can continue to recursively find the next position of the ball. Finally, if the ball reaches the last row, we can return the current column index.
The time complexity is O(m times n), and the space complexity is O(m). Here, m and n are the number of rows and columns of the grid, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Depth-First Search Simulation | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. |
| Iterative Simulation Using Loops | Time Complexity: O(m * n), driven by iterating through all cells. |
| Case Analysis + DFS | — |
| 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. |
Where Will the Ball Fall -(Amazon) : Explanation ➕ Live Coding • codestorywithMIK • 6,455 views views
Watch 9 more video solutions →Practice Where Will the Ball Fall with our built-in code editor and test cases.
Practice on FleetCode