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.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
Imagine dropping a ball at the top of a grid. The brute force way is to just follow the ball as it moves, checking each step of the way. If the ball gets stuck or goes off the edge, we just say it got stuck at that starting column.
Here's how the algorithm would work step-by-step:
def where_will_the_ball_fall(grid):
number_of_columns = len(grid[0])
results = []
for starting_column in range(number_of_columns):
current_column = starting_column
current_row = 0
while current_row < len(grid):
direction = grid[current_row][current_column]
# Check for left or right edge collision
if (direction == 1 and current_column == number_of_columns - 1) or \
(direction == -1 and current_column == 0):
current_column = -1
break
next_column = current_column + direction
# Check for V shape collision
if grid[current_row][next_column] != direction:
current_column = -1
break
current_column = next_column
current_row += 1
results.append(current_column)
return resultsThe problem asks us to simulate a ball falling through a grid of angled planks. The key insight is to track the ball's horizontal position as it moves down row by row, determining if it gets deflected or if it continues straight. If the ball gets stuck before reaching the bottom, we report where it got stuck; otherwise, we report its final column.
Here's how the algorithm would work step-by-step:
def where_will_the_ball_fall(grid):
number_of_columns = len(grid[0])
results = []
for starting_column in range(number_of_columns):
current_column = starting_column
for row_index in range(len(grid)):
current_value = grid[row_index][current_column]
# Check for rightward movement
if current_value == 1:
next_column = current_column + 1
if next_column == number_of_columns or grid[row_index][next_column] == -1:
results.append(-1)
current_column = -1
break
else:
current_column = next_column
# Check for leftward movement
elif current_value == -1:
next_column = current_column - 1
if next_column < 0 or grid[row_index][next_column] == 1:
results.append(-1)
current_column = -1
break
else:
current_column = next_column
# Ball made it to the bottom
if current_column != -1:
results.append(current_column)
return results| Case | How to Handle |
|---|---|
| Empty grid | Return an array of -1s with the same length as the number of columns. |
| Grid with zero columns | Return an empty array since there are no columns to process. |
| Ball gets stuck at the top row due to a 'V' shape at the beginning | Handle by immediately returning -1 if the ball gets stuck in the first row. |
| Ball gets stuck in the middle due to a 'V' shape | The algorithm should correctly detect if the ball gets stuck on any row and return -1. |
| Ball reaches the bottom row successfully but falls off to the left | The algorithm must check for boundary conditions after the simulated path to make sure it doesn't fall off the edge, and return -1 if it does. |
| Ball reaches the bottom row successfully but falls off to the right | The algorithm must check for boundary conditions after the simulated path to make sure it doesn't fall off the edge, and return -1 if it does. |
| Grid with very large dimensions that could cause performance issues | The algorithm has a time complexity proportional to the number of cells so it can be optimized using techniques like memoization if needed for extremely large grids. |
| The grid has only one row | Handle the case where a ball immediately falls off after the first move. |