Where Will the Ball Fall Problem

Problem

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.

Examples

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]

Solution

Method 1 – Simulation

Intuition

Simulate the path of each ball as it moves through the grid, checking for stuck conditions at each step. If the ball moves out of bounds or encounters a "V" shape, it gets stuck.

Approach

1. For each column, drop a ball and simulate its movement row by row.
2. At each cell, check the direction and whether the ball can move to the next cell.
3. If the ball hits a wall or a "V" shape, mark it as stuck.
4. Otherwise, continue until the ball exits the grid.
5. Collect the results for all columns.

Code

C++

class Solution {
public:
    vector<int> findBall(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> ans(n, -1);
        for (int col = 0; col < n; ++col) {
            int c = col;
            for (int r = 0; r < m; ++r) {
                int d = grid[r][c];
                int nc = c + d;
                if (nc < 0 || nc >= n || grid[r][nc] != d) {
                    c = -1;
                    break;
                }
                c = nc;
            }
            if (c != -1) ans[col] = c;
        }
        return ans;
    }
};

Go

func findBall(grid [][]int) []int {
    m, n := len(grid), len(grid[0])
    ans := make([]int, n)
    for col := 0; col < n; col++ {
        c := col
        for r := 0; r < m; r++ {
            d := grid[r][c]
            nc := c + d
            if nc < 0 || nc >= n || grid[r][nc] != d {
                c = -1
                break
            }
            c = nc
        }
        if c != -1 {
            ans[col] = c
        } else {
            ans[col] = -1
        }
    }
    return ans
}

Java

class Solution {
    public int[] findBall(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] ans = new int[n];
        for (int col = 0; col < n; ++col) {
            int c = col;
            for (int r = 0; r < m; ++r) {
                int d = grid[r][c];
                int nc = c + d;
                if (nc < 0 || nc >= n || grid[r][nc] != d) {
                    c = -1;
                    break;
                }
                c = nc;
            }
            ans[col] = c;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun findBall(grid: Array<IntArray>): IntArray {
        val m = grid.size
        val n = grid[0].size
        val ans = IntArray(n) { -1 }
        for (col in 0 until n) {
            var c = col
            for (r in 0 until m) {
                val d = grid[r][c]
                val nc = c + d
                if (nc !in 0 until n || grid[r][nc] != d) {
                    c = -1
                    break
                }
                c = nc
            }
            if (c != -1) ans[col] = c
        }
        return ans
    }
}

Python

class Solution:
    def findBall(self, grid: list[list[int]]) -> list[int]:
        m, n = len(grid), len(grid[0])
        ans = [-1] * n
        for col in range(n):
            c = col
            for r in range(m):
                d = grid[r][c]
                nc = c + d
                if nc < 0 or nc >= n or grid[r][nc] != d:
                    c = -1
                    break
                c = nc
            if c != -1:
                ans[col] = c
        return ans

Rust

impl Solution {
    pub fn find_ball(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = vec![-1; n];
        for col in 0..n {
            let mut c = col;
            for r in 0..m {
                let d = grid[r][c];
                let nc = (c as i32 + d) as usize;
                if nc >= n || (c as i32 + d) < 0 || grid[r][nc] != d {
                    c = usize::MAX;
                    break;
                }
                c = nc;
            }
            if c != usize::MAX {
                ans[col] = c as i32;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    findBall(grid: number[][]): number[] {
        const m = grid.length, n = grid[0].length;
        const ans = Array(n).fill(-1);
        for (let col = 0; col < n; ++col) {
            let c = col;
            for (let r = 0; r < m; ++r) {
                const d = grid[r][c];
                const nc = c + d;
                if (nc < 0 || nc >= n || grid[r][nc] !== d) {
                    c = -1;
                    break;
                }
                c = nc;
            }
            if (c !== -1) ans[col] = c;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(m * n), since each ball is simulated through all rows.
• 🧺 Space complexity: O(n), for the output array.