Where Will the Ball Fall — Medium Problem & Solution

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.

Difficulty: Medium
Topics: Arrays, Matrix, Simulation, Depth-First Search
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

For each starting column, walk down row by row.
Let d = grid[row][col] and next = col + d.
Stop with -1 if next is out of range, or if grid[row][next] != d (a V).
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue