Where Will the Ball Fall

Medium
903.

Where Will the Ball Fall

Where Will the Ball Fall is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Adobe interviews.

A box has a diagonal board in every cell: 1 redirects a ball to the right (from the cell's top-left to its bottom-right) and -1 redirects it to the left.

One ball is dropped into each column from the top. A ball gets stuck if a board sends it into a wall, or if two boards form a "V" that traps it. Return an array where entry i is the column the ball dropped into column i falls out of, or -1 if it gets stuck.

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
Only the first ball makes it through.

Example 2

Input
grid = [[-1]]
Output
[-1]
Explanation
The board pushes the ball straight into 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]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is 1 or -1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var findBall = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Where Will the Ball Fall — Solution in Python, Java & C++

Where Will the Ball Fall solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Where Will the Ball Fall is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Adobe interviews.

Problem statement

A box has a diagonal board in every cell: 1 redirects a ball to the right (from the cell's top-left to its bottom-right) and -1 redirects it to the left.

One ball is dropped into each column from the top. A ball gets stuck if a board sends it into a wall, or if two boards form a "V" that traps it. Return an array where entry i is the column the ball dropped into column i falls out of, or -1 if it gets stuck.

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: Only the first ball makes it through.

Example 2

Input: grid = [[-1]]
Output: [-1]
Explanation: The board pushes the ball straight into 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]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is 1 or -1

Hints for Where Will the Ball Fall

  1. Hint 1

    Simulate each ball independently, one row at a time.

  2. Hint 2

    A ball in column c of row r moves to column c + grid[r][c].

  3. Hint 3

    It gets stuck if that lands outside the grid, or if the neighbour's board points the other way — the "V".

How to solve Where Will the Ball Fall

Each ball's path is determined and never interacts with the others, so simulate them one at a time. Per row there are only two failure modes: walking off the side, or meeting an opposing board.

Approach

  1. For each starting column, walk down row by row.
  2. Let d = grid[row][col] and next = col + d.
  3. Stop with -1 if next is out of range, or if grid[row][next] != d (a V).
  4. Otherwise continue from next in the following row.

Why it works

A board in cell (r, c) guides the ball diagonally into column c + d of the same row before it drops. If the neighbouring cell's board slopes the other way, the two form a V that pins the ball — which is exactly the grid[row][next] != d test. Nothing else can stop it, so the two checks are complete.

Complexity

  • Time — O(m · n)
  • Space — O(n) for the output

Pitfalls

  • Checking only the wall misses the V case and reports balls that never escape.
  • The V is detected against the cell the ball moves into, in the same row.
  • The balls are independent; there is no need to simulate them together.

Reference solution

Python

from typing import List

def findBall(grid: List[List[int]]) -> List[int]:
    m, n = len(grid), len(grid[0])
    out = []
    for start in range(n):
        col = start
        for row in range(m):
            d = grid[row][col]
            nxt = col + d
            if nxt < 0 or nxt >= n or grid[row][nxt] != d:
                col = -1
                break
            col = nxt
        out.append(col)
    return out

Java

public static int[] findBall(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] out = new int[n];
    for (int start = 0; start < n; start++) {
        int col = start;
        for (int row = 0; row < m; row++) {
            int d = grid[row][col];
            int next = col + d;
            if (next < 0 || next >= n || grid[row][next] != d) {
                col = -1;
                break;
            }
            col = next;
        }
        out[start] = col;
    }
    return out;
}

C++

vector<int> findBall(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<int> out;
    for (int start = 0; start < n; start++) {
        int col = start;
        for (int row = 0; row < m; row++) {
            int d = grid[row][col];
            int next = col + d;
            if (next < 0 || next >= n || grid[row][next] != d) {
                col = -1;
                break;
            }
            col = next;
        }
        out.push_back(col);
    }
    return out;
}

JavaScript

var findBall = function(grid) {
    var m = grid.length, n = grid[0].length;
    var out = [];
    for (var start = 0; start < n; start++) {
        var col = start;
        for (var row = 0; row < m; row++) {
            var d = grid[row][col];
            var next = col + d;
            if (next < 0 || next >= n || grid[row][next] !== d) { col = -1; break; }
            col = next;
        }
        out.push(col);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)