Skip to main content

Matrix

Where Will the Ball Fall Solution In C++/Python/java/JS

Problem Description

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.

A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.

A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -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

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]]

Where Will the Ball Fall-Problem-Description

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.

Input: grid = [[-1]]
Output: [-1]
Explanation: The ball gets stuck against the left wall.

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]
Explanation: Ball b0 is dropped at column 0. It zig-zags right and left, staying between columns 0 and 1, and exits at column 0.
Ball b1 is dropped at column 1. It follows a similar zig-zag path and exits cleanly at column 1.
Ball b2 is dropped at column 2. It keeps moving right, then left, row by row, and exits at column 2.
Ball b3 is dropped at column 3. Each row guides it smoothly between columns, and it falls out at column 3.
Ball b4 is dropped at column 4. It continues diagonally as expected and exits at column 4.
Ball b5 is dropped at column 5. It tries to move right at the top but hits the wall and gets stuck.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is 1 or -1.
💡
Try Solving "Where Will the Ball Fall" Yourself First !!
Figuring out "Where Will the Ball Fall" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!

Optimal Approach

Intuition

We've got this problem where we have a grid. Each cell contains either a 1 or a -1, representing the direction a ball will move if it passes through that cell — 1 means it moves diagonally right, -1 means diagonally left. We're dropping a ball from the top of each column, and we need to figure out where it will come out at the bottom, or if it gets stuck along the way.

So, the first thing that comes to mind is, how do we even begin to track one single ball? Let's say we drop a ball from the top of the first column. What happens?

It hits the first board in that column. And that board will tell it whether to go diagonally down to the right or diagonally down to the left in the next row. So, it seems like we need to follow the ball step by step, row by row, and also keep track of the column it moves to.

Let's take a super simple example. Imagine a 2x1 grid:
[[1],
[-1]]

If we drop a ball in the first (and only) column, what happens?

It first hits the 1 in the first row, so it moves diagonally down to the right... but there's no column to the right. So, it gets stuck.

What if the grid was:
[[-1],
 [1]]

Then it hits -1 in the first row, goes diagonally down to the left, hits the left wall, and gets stuck again.

So it looks like if a board tries to push the ball outside the grid's columns in the next row, it's stuck. That's one condition for getting stuck.

Now let’s try a new example to understand successful exits:
[[1, 1, 1],
 [-1, 1, -1]]

Let’s trace each ball from each column:

  • Ball 0 starts at column 0:
    • Row 0, column 0: it's 1, so it moves to row 1, column 1.
    • Row 1, column 1: it's 1 again, so it moves to row 2, column 2.
    • Ball exits at column 2.
  • Ball 1 starts at column 1:
    • Row 0, column 1: it's 1, moves to row 1, column 2.
    • Row 1, column 2: it's -1, moves to row 2, column 1.
    • Ball exits at column 1.
  • Ball 2 starts at column 2:
    • Row 0, column 2: it's 1, wants to go to row 1, column 3 — but column 3 doesn’t exist.
    • Hits the right wall.

So the output is: [2, 1, -1]

Now let’s look at a classic V-shape trap example:
[[1, -1, -1, -1],
[1,  1, -1,  1]]

This one is interesting. Let’s drop balls one by one.

  • Ball 0 at column 0:
    • Row 0, column 0: it's 1, wants to move to column 1.
    • But grid[0][1] is -1, which wants to go back to column 0. Both boards are fighting each other.
    • V-shape! Ball is stuck.
  • Ball 1 at column 1:
    • Row 0, column 1: it's -1, wants to move to column 0.
    • But grid[0][0] is 1, wants to go to column 1. Again — V-shape!
  • Ball 2 at column 2:
    • Row 0, column 2: it's -1, moves to row 1, column 1.
    • Row 1, column 1: it's 1, wants to go to column 2.
    • But grid[1][2] is -1, which wants to go back to column 1 — another V-shape on exit!
  • Ball 3 at column 3:
    • Row 0, column 3: it's -1, moves to row 1, column 2.
    • Row 1, column 2: it's -1, tries to move to column 1.
    • But grid[1][1] is 1, which wants to go to column 2 — again V-shape. Ball is stuck on the way out.

So the output is: [-1, -1, -1, -1]

So, the conditions for getting stuck are:

  1. Wall hit:
    • If at grid[row][col], the direction is -1 and col is 0.
    • If at grid[row][col], the direction is 1 and col is cols - 1.
  2. "V" shape:
    • If at grid[row][col], grid[row][col] == 1 and grid[row][col + 1] == -1.
    • If at grid[row][col], grid[row][col] == -1 and grid[row][col - 1] == 1.

Now, for each ball starting at the top of each column, we simulate its path downwards, checking these conditions at each step (at the current row before deciding the next move). If the ball reaches the last row, we record the column. If it gets stuck, we record -1.

Well spotted! Now, if you think about it, what kind of approach are we using here?
We’re following one path deeply for each ball, going step by step down the grid, checking conditions, and deciding the next move.

This is exactly what a Depth-First Search (DFS) looks like!

We're not branching into multiple paths or keeping track of multiple states simultaneously — we're simply exploring a single path for each ball until it either gets stuck or exits.
That’s classic DFS behavior: go deep until you hit a base case.

Let's now see how our algorithm looks!

Where Will the Ball Fall Algorithm

  1. Wall Check
    First, we check if the move based on grid[row][col] would lead the ball outside the grid.
    • If grid[row][col] == 1 and col == cols - 1, it's trying to go right but there’s no column → ball is stuck.
    • If grid[row][col] == -1 and col == 0, it's trying to go left but there’s no column → ball is stuck.
  2. "V" Shape Check
    Next, we check whether the current cell and its adjacent cell in the same row form a "V" shape:
    • If grid[row][col] == 1 and grid[row][col + 1] == -1, there's a right board followed by a left board → ball is stuck.
    • If grid[row][col] == -1 and grid[row][col - 1] == 1, there's a left board followed by a right board → ball is stuck.
  3. Valid Move → Go Down Diagonally
    If no stuck conditions are met, the ball moves diagonally down:
    • New row: row + 1
    • New column: col + grid[row][col]
      Repeat the process from the new position.
  4. Exit Condition
    If row == total number of rows, the ball has reached the bottom and exits successfully.
    Return the current column index as the final position.
  5. Repeat for All Columns
    Simulate this process for each column from 0 to cols - 1 independently, and collect the results in an array.

Approach

  1. Define Recursive Function (DFS): drop_ball(row, col) → Simulates the movement of a single ball starting at (row, col).
  2. Handle Base Case: If row == total number of rows, the ball has exited the grid. Return the current col.
  3. Determine Next Move
    • Get the direction = grid[row][col].
    • Calculate next_col = col + direction.
  4. Wall Hit Conditions: If next_col < 0 or next_col >= number of columns, return -1 (ball hits the left/right wall).
  5. Clash / 'V' Shape Conditions
    • If direction == 1 and grid[row][col + 1] == -1 → stuck in a V-shape clash. Return -1.
    • If direction == -1 and grid[row][col - 1] == 1 → stuck in a V-shape clash. Return -1.
  6. Move to the Next Row and Continue:  If none of the stuck conditions are met, recursively call drop_ball(row + 1, next_col).
  7. Simulate for All Columns: For each starting column from 0 to cols - 1, call drop_ball(0, col) and store the result and return it.

Let us understand this with a video,

0:00
/1:25

Where Will the Ball Fall - Optimal-Approach-Animation

Dry-Run

Input: grid = [[ 1, 1, 1, -1, 1],
[ 1, -1, -1, 1, -1],
[ 1, 1, 1, -1, -1]]

Output: [-1, 2, -1, -1, -1]

Explanation:

Let’s simulate dropping a ball from each column (0 to 4) and trace its full journey. Watch out for V-shapes and wall hits!

Ball 0 (starts at column 0):

  • grid[0][0] = 1 → move diagonally right → row 1, column 1
  • grid[1][1] = -1 → wants to go left → back to column 0
  • grid[1][0] = 1 → wants to go right
    V-shape trap formed between (1,0) and (1,1) — both cells push into each other.

Ball 0 is stuck.
Ball 0 output: -1

Ball 1 (starts at column 1):

  • grid[0][1] = 1 → move diagonally right → row 1, column 2
  • grid[1][2] = -1 → move diagonally left → row 2, column 1
  • grid[2][1] = 1 → move diagonally right → row 3, column 2 (out of grid)
    Successfully exits at column 2.

Ball 1 reaches the bottom.
Ball 1 output: 2

Ball 2 (starts at column 2):

  • grid[0][2] = 1 → wants to go diagonally right → to column 3
  • grid[0][3] = -1 → wants to go left → to column 2
    V-shape trap immediately at (0,2) and (0,3) — they push into each other.

Ball 2 gets stuck right at the top.
Ball 2 output: -1

Ball 3 (starts at column 3):

  • grid[0][3] = -1 → wants to go left → to column 2
  • grid[0][2] = 1 → wants to go right
    Again, V-shape at (0,2) and (0,3)

Ball 3 is stuck immediately.
Ball 3 output: -1

Ball 4 (starts at column 4):

  • grid[0][4] = 1 → wants to go right → to column 5
    But column 5 is outside the grid → Right wall hit

Ball 4 is stuck due to boundary
Ball 4 output: -1

Final Output: [-1, 2, -1, -1, -1]

Where Will the Ball Fall Solution

Now let's checkout the "Where Will the Ball Fall code" in C++, Java, Python and JavaScript.

"Where Will the Ball Fall" Code in all Languages.
1. Where Will the Ball Fall solution in C++ Try on Compiler 
class Solution {
public:

    // Simulates the movement of a single ball from a specific column
    int dropBall(vector<vector<int>>& grid, int rowCount, int colCount, int row, int col) {

        // Base case: if the ball has reached the last row
        if (row == rowCount) return col;

        // Ball hits left wall or right wall
        if ((col == 0 && grid[row][col] == -1) ||
            (col == colCount - 1 && grid[row][col] == 1)) return -1;

        // Ball gets stuck in a "V" shape
        if ((grid[row][col] == 1 && grid[row][col + 1] == -1) ||
            (grid[row][col] == -1 && grid[row][col - 1] == 1)) return -1;

        // Move diagonally based on the direction of the board
        return grid[row][col] == 1 
            ? dropBall(grid, rowCount, colCount, row + 1, col + 1)
            : dropBall(grid, rowCount, colCount, row + 1, col - 1);
    }

    vector<int> findBall(vector<vector<int>>& grid) {

        // Get dimensions of the grid
        int rowCount = grid.size();
        int colCount = grid[0].size();

        // Initialize result array to store final column for each ball
        vector<int> result(colCount);

        // Drop each ball from the top of each column
        for (int col = 0; col < colCount; ++col) {
            result[col] = dropBall(grid, rowCount, colCount, 0, col);
        }

        return result;
    }
};

2. Where Will the Ball Fall Solution in Java Try on Compiler 
class Solution {

    // Simulates the movement of a single ball from a specific column
    private int dropBall(int[][] grid, int rowCount, int colCount, int row, int col) {

        // Base case: ball has reached the bottom
        if (row == rowCount) return col;

        // Ball hits wall on either side
        if ((col == 0 && grid[row][col] == -1) ||
            (col == colCount - 1 && grid[row][col] == 1)) return -1;

        // Ball gets stuck in a V-shape
        if ((grid[row][col] == 1 && grid[row][col + 1] == -1) ||
            (grid[row][col] == -1 && grid[row][col - 1] == 1)) return -1;

        // Continue the path based on the slope direction
        return grid[row][col] == 1 
            ? dropBall(grid, rowCount, colCount, row + 1, col + 1)
            : dropBall(grid, rowCount, colCount, row + 1, col - 1);
    }

    public int[] findBall(int[][] grid) {

        // Get dimensions of the grid
        int rowCount = grid.length;
        int colCount = grid[0].length;

        // Result array to store the final column for each ball
        int[] result = new int[colCount];

        // Simulate for each column
        for (int col = 0; col < colCount; ++col) {
            result[col] = dropBall(grid, rowCount, colCount, 0, col);
        }

        return result;
    }
}

3. Where Will the Ball Fall Solution in Python Try on Compiler 
class Solution:

    # Simulates the path of a single ball using recursion
    def drop_ball(self, grid: List[List[int]], rowCount: int, colCount: int, row: int, col: int) -> int:

        # Base case: reached the bottom
        if row == rowCount:
            return col

        # Ball hits the left or right wall
        if (col == 0 and grid[row][col] == -1) or (col == colCount - 1 and grid[row][col] == 1):
            return -1

        # Ball gets stuck in a V-shape
        if (grid[row][col] == 1 and grid[row][col + 1] == -1) or \
           (grid[row][col] == -1 and grid[row][col - 1] == 1):
            return -1

        # Move diagonally based on board direction
        return self.drop_ball(grid, rowCount, colCount, row + 1, col + grid[row][col])

    def findBall(self, grid: List[List[int]]) -> List[int]:

        # Grid dimensions
        rowCount = len(grid)
        colCount = len(grid[0])

        # Simulate each ball and store result
        return [self.drop_ball(grid, rowCount, colCount, 0, col) for col in range(colCount)]

4. Where Will the Ball Fall solution in JavaScript Try on Compiler 
/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var findBall = function(grid) {

    // Simulate a single ball's path
    function dropBall(row, col) {

        // Base case: reached the bottom
        if (row === grid.length) return col;

        // Wall collision
        if ((col === 0 && grid[row][col] === -1) ||
            (col === grid[0].length - 1 && grid[row][col] === 1)) return -1;

        // V-shape trap
        if ((grid[row][col] === 1 && grid[row][col + 1] === -1) ||
            (grid[row][col] === -1 && grid[row][col - 1] === 1)) return -1;

        // Continue based on slope
        return dropBall(row + 1, col + grid[row][col]);
    }

    // Simulate each column and return result
    const result = [];
    for (let col = 0; col < grid[0].length; col++) {
        result.push(dropBall(0, col));
    }

    return result;
};

Where Will the Ball Fall Complexity Analysis

Time Complexity: O(m x n)

The Where Will the Ball Fall algorithm involves two main operations:

Simulating the ball’s path using depth-first search (DFS): For each ball dropped from the top of the grid, the algorithm recursively checks its path row by row until it either exits or gets stuck.
This step takes O(m) time per ball in the worst case, where m is the number of rows.

Repeating the simulation for all columns: Each column (ball) is processed independently. If there are n columns, this results in n DFS calls.

Thus, the total time complexity is:
O(m) per ball × n balls = O(m × n)
where m is the number of rows and n is the number of columns.

Space Complexity: O(m + n)

Auxiliary Space Complexity: Auxiliary space refers to the extra space required by the algorithm other than extra space.

  • Recursion stack: Up to O(m) in the worst case
  • Result array: O(n)
  • Other variables: Constant → O(1)
    So, auxiliary space complexity: O(m + n)

Total Space Complexity

  • Input grid: O(m × n).
  • Extra space (recursion + result array): O(m + n)

Total space complexity: O(m x n).

Similar Problems

Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Game of Life

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.

Given the current state of the board, update the board to reflect its next state.

Note that you do not need to return anything.