Leetcode #1706: Where Will the Ball Fall
In this guide, we solve Leetcode #1706 Where Will the Ball Fall in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Array, Matrix, Simulation
Intuition
Grid problems are easiest when you define clear row/column boundaries.
A consistent traversal order prevents off-by-one errors.
Approach
Iterate by rows, columns, or layers depending on the requirement.
Keep bounds updated as the traversal progresses.
Steps:
- Define bounds or directions.
- Visit cells in order.
- Update result and move bounds.
Example
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.
Python Solution
class Solution:
def findBall(self, grid: List[List[int]]) -> List[int]:
def dfs(i: int, j: int) -> int:
if i == m:
return j
if j == 0 and grid[i][j] == -1:
return -1
if j == n - 1 and grid[i][j] == 1:
return -1
if grid[i][j] == 1 and grid[i][j + 1] == -1:
return -1
if grid[i][j] == -1 and grid[i][j - 1] == 1:
return -1
return dfs(i + 1, j + 1) if grid[i][j] == 1 else dfs(i + 1, j - 1)
m, n = len(grid), len(grid[0])
return [dfs(0, j) for j in range(n)]
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.