Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Where Will the Ball Fall

Understand how to simulate ball movement in a 2D grid where cells redirect balls left or right. Explore conditions causing balls to get stuck or fall out and implement a solution that returns the exit column or -1 if stuck. Practice traversing matrices and handling edge cases.

We'll cover the following...

Statement

You have nn balls and a 2D grid of size m×nm \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 nn 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 11 or −1-1.

  • 11 represents that the grid will redirect the ball to the right.
  • −1-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 nn, with the ithith element indicating the column that the ball falls out of, or it becomes −1-1 if it’s stuck. If the ball drops from column xx and falls out from column yy, then in the result array, index xx contains value yy.

Constraints:

  • m==m == grid.length
  • n==n == grid[i].length
  • 1≤m,n≤1001 \leq m, n \leq 100
  • grid[i][j] is 11 or −1-1.

Example

canvasAnimation-image
1 / 4

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Where Will the Ball Fall

1.

What will be the output of the grid given below?

grid = [[1, 1], [-1, -1]]
A.

[−1,−1][-1, -1]

B.

[0,−1][0, -1]

C.

[0,0][0, 0]

D.

[1,1][1, 1]

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > FindExitColumn.java
import java.util.*;
class FindExitColumn{
    public static int[] findExitColumn(int[][] grid) {
        // Replace this placeholder return statement with your code
        return new int[]{};
    }
}
Where Will the Ball Fall