Solution: Where Will the Ball Fall
Let's solve the Where Will the Ball Fall problem using the Matrices pattern.
We'll cover the following
Statement
You have $n$ balls and a 2D grid of size $m \times n$ representing a box. The box is open on the top and bottom sides. Each cell in the box has a diagonal that can redirect a ball to the right or the left. You must drop $n$ balls at each columnâ€™s top. The goal is to determine whether each ball will fall out of the bottom or become stuck in the box. Each cell in the grid has a value of $1$ or $1$.
 $1$ represents that the grid will redirect the ball to the right.
 $1$ represents that the grid will redirect the ball to the left.
A ball gets stuck if it hits a Vshaped pattern between two grids or if a grid redirects the ball into either wall of the box.
The solution should return an array of size $n$, with the $ith$ element indicating the column that the ball falls out of, or it becomes $1$ if itâ€™s stuck. If the ball drops from column $x$ and falls out from column $y$, then in the result array, index $x$ contains value $y$.
Constraints:
 $m ==$
grid.length
 $n ==$
grid[i].length
 $1 \leq m, n \leq 100$
grid[i][j]
is $1$ or $1$.
Solution
The following steps utilize the intuitive version of the algorithm, where we drop each ball from the top of the grid one by one and follow the path it can take. The ball starts moving from a certain column and jumps from one row to the next based on the value of the current cell. Letâ€™s consider the following two examples to better understand the ball movement within the grid:

If the ball starts from column $0$, row $0$, and the value in the cell
grid[0][0]
is $1$(topleftbottomright diagonal), the ball will move to the next row, which is 1, and to the next column, which is also $1$. So, the next position of the ball will be the cellgrid[1][1]
. 
If the ball starts from column $2$, row $0$, and the cell
grid[0][2]
contains $1$ (toprightbottomleft diagonal), the ball will go to the next row, which is $1$, and to the previous column, which is $1$. So, the next position of the ball will be the cellgrid[1][1]
.
We repeat the process above as the ball moves to the next rows. The termination conditions for the algorithm are as follows:

The ball keeps moving to the next rows until it hits the last row in the grid. This is a success case, and the column where the ball meets the final row is recorded in the output array.

The ball gets stuck in a row because one of the following conditions is met:

The ball falls to the leftmost column, and the value in the cell is $1$. This will stop the ball from moving to the next row because the ball will hit the wall because of the toprightbottomleft diagonal.

The ball falls to the rightmost column, and the value in the cell is $1$. This will stop the ball from moving to the next row because the ball will hit the wall because of the topleftbottomright diagonal.

The ball is between the leftmost and rightmost columns, the diagonal in the current cell is topleftbottomright, and the immediate next column stops the ball from moving to the next row because it has a toprightbottomleft diagonal, forming a $V$ shape.

The ball is between the leftmost and rightmost columns, the diagonal in the current cell is toprightbottomleft, and the immediate previous column stops the ball from moving to the next row because it has a topleftbottomright diagonal, forming a V shape.

We can solve the problem using the iterative approach by following the steps below:

Declare an array,
result
, of sizegrid.length
, and initialize its elements with $1$, assuming that each ball will be stuck in the grid. We will change the values for the columns where the balls will succeed in reaching the last row. 
Iterate the grid using nested for loops. For each column, perform the following checks:

For each row,
row
, do the following:
Compute
nextColumn
by addingcurrentColumn
togrid[row][currentColumn]
. 
Check if
grid[row][nextColumn]
has the same value asgrid[row][currentColumn]
. If so, the ball can move to the next row. 
Check if the ball is not stuck at the boundary of the grid by checking if the
nextColumn
is less than zero or greater than the columns of the grid. 
Set the
currentColumn
as thenextColumn
. 
If this is the last row, set
result[col]
tonextColumn
.


Letâ€™s look at the slide below to see how the algorithm works.
Level up your interview prep. Join Educative to access 80+ handson prep courses.