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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), driven by iterating through all cells.
Space Complexity: O(n), where n stands for the result array requirement.
| 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. |
1706. Where Will the Ball Fall | LEETCODE MEDIUM | DFS | DYNAMIC PROGRAMMING | CODE EXPLAINER • code Explainer • 5,857 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