Where Will the Ball Fall solution and explanation
Google
9 more videos on this problem
Where Will the Ball Fall -(Amazon) : Explanation ➕ Live CodingcodestorywithMIK · 20:24 · 7K views
1706. Where Will the Ball Fall | LEETCODE MEDIUM | DFS | DYNAMIC PROGRAMMING | CODE EXPLAINERcode Explainer · 7:54 · 5K views
LeetCode 1706. Where Will the Ball Fall | Visualization | PythonAH Tech · 7:53 · 2K views
Daily Leetcode #945: Nov 01, 2022 - 1706. Where Will the Ball FallProgramming Live with Larry · 16:21 · 789 views
1706. Where Will the Ball Fall (Leetcode Medium)Programming Live with Larry · 19:12 · 771 views
Leetcode 1706. Where Will the Ball FallFraz · 10:20 · 703 views
1706. Where Will the Ball Fall || Leetcode || C++Code with Sky · 14:25 · 530 views
Where Will the Ball Fall | LeetCode 1706 | Java | @LearnOverflowLearn Overflow · 17:22 · 393 views
leetcode 1706. Where Will the Ball Fall - direct simulation, two solution formatsCode-Yao · 13:01 · 224 views
1706. Where Will the Ball Fall | JavaScript | LeetCode Daily Challenge | Matrix | Medium difficultyLeetCodeWithMonu · 11:17 · 203 views
The 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.
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]
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 100grid[i][j]is1or-1.
Approach overview
Problem Overview: You drop one ball from the top of each column in a grid. Every cell contains a diagonal board that redirects the ball either left or right. Some configurations form a V-shape that traps the ball. The task is to simulate the movement and return the column where each ball exits, or -1 if it gets stuck.
Approach 1: Depth-First Search Simulation (O(m * n) time, O(m) space)
Treat each ball drop as a path traversal through the matrix. From column c in row r, read the diagonal direction grid[r][c]. A value of 1 moves the ball to c + 1, while -1 moves it to c - 1. Before moving, check two failure conditions: the next column is outside the grid, or the adjacent cell forms a V-shape (grid[r][c] != grid[r][next]). Either case means the ball gets stuck. If the move is valid, recursively continue to the next row. When the row index reaches m, the ball exits successfully.
This approach models the process directly and is easy to reason about. Each recursive call represents the ball moving one row down. Since a ball can pass through at most m rows and there are n starting columns, the total runtime is O(m * n). Recursion depth gives O(m) auxiliary space.
Approach 2: Iterative Simulation Using Loops (O(m * n) time, O(1) space)
Instead of recursion, simulate the ball movement with loops. For each starting column, track the current column index and iterate row by row. Read the direction from the grid and compute the next column. If the next column is out of bounds or forms a V-shaped block with the adjacent cell, stop and record -1. Otherwise update the column pointer and continue to the next row.
This method uses simple iteration over the array-based grid and avoids recursion overhead. The key observation is that the ball always moves exactly one row per step, making the process deterministic. Each ball requires scanning at most m rows, giving the same O(m * n) runtime but with O(1) extra memory. The logic is a classic simulation pattern where you repeatedly apply movement rules until termination.
Recommended for interviews: The iterative simulation is the expected solution. It keeps the logic explicit, avoids recursion, and runs in optimal O(m * n) time with constant space. Implementing DFS first can help demonstrate understanding of the movement rules, but interviewers typically prefer the loop-based simulation because it is simpler and more memory efficient.
Approach 1: Depth-First Search Simulation
Use depth-first search (DFS) to simulate the movement of each ball from the top to the bottom, keeping track of the ball's column. If a ball encounters a 'V' shape or hits the wall, it gets stuck. This approach simulates the scenario for each ball individually.
class Solution:
def findBall(self, grid):
def dfs(row, col):
if row == len(grid):
return col
next_col = col + grid[row][col]
if next_col < 0 or next_col >= len(grid[0]) or grid[row][next_col] != grid[row][col]:
return -1
return dfs(row + 1, next_col)
return [dfs(0, col) for col in range(len(grid[0]))]class Solution {
public int findExit(int[][] grid, int row, int col) {
if (row == grid.length) return col;
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= grid[0].length || grid[row][nextCol] != grid[row][col]) return -1;
return findExit(grid, row + 1, nextCol);
}
public int[] findBall(int[][] grid) {
int n = grid[0].length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = findExit(grid, 0, i);
}
return result;
}
}#include <vector>
using namespace std;
class Solution {
public:
int findPath(vector<vector<int>>& grid, int row, int col) {
if (row == grid.size()) return col;
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= grid[0].size() || grid[row][nextCol] != grid[row][col]) return -1;
return findPath(grid, row + 1, nextCol);
}
vector<int> findBall(vector<vector<int>>& grid) {
vector<int> result(grid[0].size(), 0);
for (int i = 0; i < grid[0].size(); ++i) {
result[i] = findPath(grid, 0, i);
}
return result;
}
};var findBall = function(grid) {
const dfs = (row, col) => {
if (row === grid.length) return col;
const nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= grid[0].length || grid[row][nextCol] !== grid[row][col]) return -1;
return dfs(row + 1, nextCol);
};
return Array.from({length: grid[0].length}, (_, col) => dfs(0, col));
};#include <stdio.h>
#include <stdlib.h>
int dfs(int **grid, int m, int n, int row, int col) {
if (row == m) return col;
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= n || grid[row][nextCol] != grid[row][col]) return -1;
return dfs(grid, m, n, row + 1, nextCol);
}
int* findBall(int** grid, int gridSize, int* gridColSize, int* returnSize) {
*returnSize = *gridColSize;
int *result = (int *)malloc((*gridColSize) * sizeof(int));
for (int i = 0; i < *gridColSize; ++i) {
result[i] = dfs(grid, gridSize, *gridColSize, 0, i);
}
return result;
}public class Solution {
public int FindExit(int[][] grid, int row, int col) {
if (row == grid.Length) return col;
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol == grid[0].Length || grid[row][nextCol] != grid[row][col]) return -1;
return FindExit(grid, row + 1, nextCol);
}
public int[] FindBall(int[][] grid) {
int n = grid[0].Length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = FindExit(grid, 0, i);
}
return result;
}
}For Python, a nested DFS function is used within the main function to explore the trajectory of each ball. The list comprehension gathers results from exploring each initial column, either obtaining the exit column or a stuck indication.
Time Complexity: O(m * n), with m and n representing the grid dimensions.
Space Complexity: O(n) due to the result list and stack usage in recursive calls.
Approach 2: Iterative Simulation Using Loops
Utilize nested loops to simulate the motion of each ball iteratively instead of using recursion. It tracks each movement step-by-step across the grid, calculates next positions, transitions to subsequent rows, and monitors for blockages or exits.
class Solution:
def findBall(self, grid):
n = len(grid[0])
result = []
for i in range(n):
col = i
for row in grid:
next_col = col + row[col]
if next_col < 0 or next_col == n or row[next_col] != row[col]:
col = -1
break
col = next_col
result.append(col)
return resultclass Solution {
public int[] findBall(int[][] grid) {
int n = grid[0].length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int col = i;
for (int[] row : grid) {
int nextCol = col + row[col];
if (nextCol < 0 || nextCol >= n || row[nextCol] != row[col]) {
col = -1;
break;
}
col = nextCol;
}
result[i] = col;
}
return result;
}
}#include <vector>
using namespace std;
class Solution {
public:
vector<int> findBall(vector<vector<int>>& grid) {
vector<int> result(grid[0].size(), 0);
for (int i = 0; i < grid[0].size(); ++i) {
int col = i;
for (int row = 0; row < grid.size(); ++row) {
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= grid[0].size() || grid[row][nextCol] != grid[row][col]) {
col = -1;
break;
}
col = nextCol;
}
result[i] = col;
}
return result;
}
};var findBall = function(grid) {
const result = [];
for (let i = 0; i < grid[0].length; i++) {
let col = i;
for (let row of grid) {
const nextCol = col + row[col];
if (nextCol < 0 || nextCol >= grid[0].length || row[nextCol] !== row[col]) {
col = -1;
break;
}
col = nextCol;
}
result.push(col);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int* findBall(int** grid, int gridSize, int* gridColSize, int* returnSize) {
*returnSize = *gridColSize;
int *result = (int *)malloc((*gridColSize) * sizeof(int));
for (int i = 0; i < *gridColSize; ++i) {
int col = i;
for (int row = 0; row < gridSize; ++row) {
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= *gridColSize || grid[row][nextCol] != grid[row][col]) {
col = -1;
break;
}
col = nextCol;
}
result[i] = col;
}
return result;
}public class Solution {
public int[] FindBall(int[][] grid) {
int n = grid[0].Length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int col = i;
foreach (var row in grid) {
int nextCol = col + row[col];
if (nextCol < 0 || nextCol >= n || row[nextCol] != row[col]) {
col = -1;
break;
}
col = nextCol;
}
result[i] = col;
}
return result;
}
}The depicted solution navigates through the grid iteratively, using nested loops that calculate each ball's position directly - no recursion. It checks for every cell iteratively to establish if the ball has fallen out or remained trapped in the simulation.
Time Complexity: O(m * n), inherent to all cell checks.
Space Complexity: O(n), representing storage for the output results.
Approach 3: Case Analysis + DFS
We can use DFS to simulate the movement of the ball. Design a function dfs(i, j), which represents the column where the ball will fall when it starts from row i and column j. The ball will get stuck in the following cases:
- The ball is in the leftmost column, and the cell's diagonal directs the ball to the left.
- The ball is in the rightmost column, and the cell's diagonal directs the ball to the right.
- The cell's diagonal directs the ball to the right, and the adjacent cell to the right directs the ball to the left.
- The cell's diagonal directs the ball to the left, and the adjacent cell to the left directs the ball to the right.
If any of the above conditions are met, we can determine that the ball will get stuck and return -1. Otherwise, we can continue to recursively find the next position of the ball. Finally, if the ball reaches the last row, we can return the current column index.
The time complexity is O(m times n), and the space complexity is O(m). Here, m and n are the number of rows and columns of the grid, respectively.
function findBall(grid: number[][]): number[] {
const m = grid.length;
const n = grid[0].length;
const dfs = (i: number, j: number) => {
if (i === m) {
return j;
}
if (grid[i][j] === 1) {
if (j === n - 1 || grid[i][j + 1] === -1) {
return -1;
}
return dfs(i + 1, j + 1);
} else {
if (j === 0 || grid[i][j - 1] === 1) {
return -1;
}
return dfs(i + 1, j - 1);
}
};
return Array.from({ length: n }, (_, j) => dfs(0, j));
}func findBall(grid [][]int) (ans []int) {
m, n := len(grid), len(grid[0])
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i == m {
return j
}
if j == 0 && grid[i][j] == -1 {
return -1
}
if j == n-1 && grid[i][j] == 1 {
return -1
}
if grid[i][j] == 1 && grid[i][j+1] == -1 {
return -1
}
if grid[i][j] == -1 && grid[i][j-1] == 1 {
return -1
}
if grid[i][j] == 1 {
return dfs(i+1, j+1)
}
return dfs(i+1, j-1)
}
for j := 0; j < n; j++ {
ans = append(ans, dfs(0, j))
}
return
}impl Solution {
fn dfs(grid: &Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
if i == grid.len() {
return j as i32;
}
if grid[i][j] == 1 {
if j == grid[0].len() - 1 || grid[i][j + 1] == -1 {
return -1;
}
Self::dfs(grid, i + 1, j + 1)
} else {
if j == 0 || grid[i][j - 1] == 1 {
return -1;
}
Self::dfs(grid, i + 1, j - 1)
}
}
pub fn find_ball(grid: Vec<Vec<i32>>) -> Vec<i32> {
let m = grid.len();
let n = grid[0].len();
let mut ans = vec![0; n];
for i in 0..n {
ans[i] = Self::dfs(&grid, 0, i);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search Simulation | Time Complexity: O(m * n), with m and n representing the grid dimensions. |
| Iterative Simulation Using Loops | Time Complexity: O(m * n), inherent to all cell checks. |
| Case Analysis + DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search Simulation | O(m * n) | O(m) | Useful for modeling the ball path recursively or when demonstrating traversal logic clearly. |
| Iterative Simulation Using Loops | O(m * n) | O(1) | Best general solution. Minimal memory usage and straightforward implementation for interviews. |
Frequently asked questions
Is Where Will the Ball Fall easy or hard?
Where Will the Ball Fall is classified as a Medium problem. The algorithm itself is straightforward simulation, but handling edge cases such as boundaries and V-shaped traps correctly requires careful reasoning.
Where Will the Ball Fall Python or Java solution
Both Python and Java implementations follow the same logic: iterate through each starting column and simulate the ball's path through the rows. Update the column pointer based on the grid value and stop when a boundary or V-shape trap occurs.
How to solve Where Will the Ball Fall in O(m * n)?
Simulate the movement of each ball through the grid. For every row, compute the next column based on the diagonal value (1 for right, -1 for left). If the move goes out of bounds or creates a V-shape with the neighboring cell, the ball gets stuck and returns -1.
What is the best approach for Where Will the Ball Fall?
The iterative simulation approach is the most practical solution. Track the column of each ball and move it row by row according to the board direction. Check for boundary violations or V-shaped blocks at every step. This runs in O(m * n) time with O(1) extra space.
Is Where Will the Ball Fall asked at Google Amazon Meta?
Simulation and grid traversal problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. The problem tests careful boundary checks and the ability to simulate movement through a matrix.
What data structure is used in Where Will the Ball Fall?
The main data structure is a 2D matrix (grid). The algorithm iterates through rows while tracking the current column position for each ball, applying simple simulation rules.
What is the time complexity of Where Will the Ball Fall?
The optimal solution runs in O(m * n) time where m is the number of rows and n is the number of columns. Each ball moves through at most m rows, and there are n balls dropped from the top.