Solution: Where Will the Ball Fall

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 V-shaped 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$(topleft-bottomright 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 cell grid[1][1].

• If the ball starts from column $2$, row $0$, and the cell grid[0][2] contains $-1$ (topright-bottomleft 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 cell grid[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 topright-bottomleft 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 topleft-bottomright diagonal.

  • The ball is between the left-most and right-most columns, the diagonal in the current cell is topleft-bottomright, and the immediate next column stops the ball from moving to the next row because it has a topright-bottomleft diagonal, forming a $V$ shape.

  • The ball is between the leftmost and rightmost columns, the diagonal in the current cell is topright-bottomleft, and the immediate previous column stops the ball from moving to the next row because it has a topleft-bottomright diagonal, forming a V shape.

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

1. Declare an array, result, of size grid.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.

2. Iterate the grid using nested for loops. For each column, perform the following checks:

   • For each row, row, do the following:

     1. Compute next_column by adding current_column to grid[row][current_column].

     2. Check if grid[row][next_column] has the same value as grid[row][current_column]. If so, the ball can move to the next row.

     3. Check if the ball is not stuck at the boundary of the grid by checking if the next_column is less than zero or greater than the columns of the grid.

     4. Set the current_column as the next_column.

     5. If this is the last row, set result[col] to next_column.

Let’s look at the slide below to see how the algorithm works.