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.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Simulation
- 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.lengthn == grid[i].length1 <= m, n <= 100grid[i][j] is 1 or -1
Hints for Where Will the Ball Fall
Hint 1
Simulate each ball independently, one row at a time.
Hint 2
A ball in column
cof rowrmoves to columnc + grid[r][c].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
- For each starting column, walk down row by row.
- Let
d = grid[row][col]andnext = col + d. - Stop with
-1ifnextis out of range, or ifgrid[row][next] != d(a V). - Otherwise continue from
nextin 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 outJava
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)