MediumNo. 1706
Where Will the Ball Fall — LeetCode 1706 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Array, Matrix, Simulation
- Reading time
- 3 min
- Source
- leetcode.com
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.
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.
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
- Time
- O(m × n)
- Space · auxiliary
- O(m)
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1706. Where Will the Ball Fall is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0054 | Spiral Matrix | Medium |
| 0059 | Spiral Matrix II | Medium |
| 0289 | Game of Life | Medium |
| 0498 | Diagonal Traverse | Medium |
| 0566 | Reshape the Matrix | Easy |
| 0867 | Transpose Matrix | Easy |
Frequently asked questions
- How hard is LeetCode 1706. Where Will the Ball Fall?
LeetCode 1706. Where Will the Ball Fall is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1706. Where Will the Ball Fall?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 1706. Where Will the Ball Fall?
The Python solution on this page uses O(m) auxiliary space.
- What topics does LeetCode 1706. Where Will the Ball Fall cover?
LeetCode 1706. Where Will the Ball Fall is tagged Array, Matrix and Simulation on LeetCode.