Where Will the Ball Fall
Medium · Matrix · Array · Matrix · Simulation
Problem
A box is modelled as an m x n grid. Every cell holds a diagonal board: 1 means the board runs from top-left to bottom-right and deflects a ball to the right; -1 runs from top-right to bottom-left and deflects it to the left.
One ball is dropped into the top of each of the n columns. A ball moves one row down per cell, shifting one column in the direction of the board. It gets stuck if it is pushed into a side wall, or if it lands in a "V" formed by two side-by-side cells whose boards point toward each other.
Return an array answer of length n, where answer[i] is the column the ball dropped in column i leaves from at the bottom, or -1 if it gets stuck.
Examples
Input: grid = [[1,1,-1],[-1,-1,-1]] Output: [0,-1,-1]
Ball 0 slides right, then left, and leaves at column 0. Balls 1 and 2 are trapped by the V that columns 1 and 2 form in the top row.
Input: grid = [[1,-1]] Output: [-1,-1]
The two boards form a V, trapping both balls.
Input: grid = [[-1,-1,1,1]] Output: [-1,0,3,-1]
The ball in column 0 hits the left wall, the ball in column 3 hits the right wall, and the middle two slide outward.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 100
- grid[i][j] is 1 or -1
Approaches
- Baseline: every ball moves together, row by row — time O(m · n), space O(n)
Follow-up
Balls never interact, so the answer for column c is a function of the start column alone; a bottom-up table exit[r][c] would answer drops from any cell in O(1) after O(m · n) work. The use cases invert the answer (which ball leaves at each column) and report how far each ball gets.
Related problems
Start free on Cariara · Coding problems · System design studio
