LeetCode 1706 - Where Will the Ball Fall

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

This problem asks us to simulate the movement of balls dropped into a 2-D box represented by a grid. Each cell in the grid has a diagonal board that directs a ball either to the right (1) or to the left (-1). We drop one ball into each column at the top of the box and need to determine where each ball will exit at the bottom, or if it gets stuck inside the box.

The input grid is a 2-D array of integers with m rows and n columns, where grid[i][j] indicates the direction of the board in row i and column j. The output should be an array of size n, where the ith element tells the column from which the ball dropped at the ith column exits the bottom of the box, or -1 if the ball gets stuck.

Important observations include that a ball gets stuck if it moves into a wall (j < 0 or j >= n) or if it encounters a "V" shape between two adjacent boards pointing towards each other (i.e., 1 followed by -1 or -1 followed by 1). The constraints 1 <= m, n <= 100 indicate that a direct simulation is feasible because the total number of operations will be at most 10,000, which is acceptable for modern systems.

Key edge cases include a single column grid, balls that immediately hit walls, and patterns that trap balls between two adjacent cells.

Approaches

The brute-force approach is to simulate each ball’s path row by row. For each row, check the current direction and determine if the ball moves left or right. If the ball tries to move outside the grid or encounters a "V" shape, mark it as stuck. This approach is correct but involves iterating over every row for every ball.

The optimal solution is essentially the same as the brute-force approach because we need to simulate the path to know whether a ball gets stuck. The key is recognizing that each ball’s path is independent, so we can iterate over each column independently. There is no need for additional data structures or memoization beyond storing the results.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(n)	Simulate each ball row by row; check boundaries and "V" shapes.
Optimal	O(m * n)	O(n)	Same as brute-force; independent simulation for each ball, storing results in an array.

Algorithm Walkthrough

Initialize an array result of size n with all values set to -1 as a default for balls that get stuck.
Iterate over each column c from 0 to n-1. This represents dropping a ball from column c.
For each ball, start at the top row (row = 0) and the current column col = c.
For each row:
Compute the next column as col + grid[row][col].
Check if the next column is out of bounds (next_col < 0 or next_col >= n). If it is, the ball is stuck; break the simulation for this ball.
Check if the next cell has a board that opposes the current direction (grid[row][col] != grid[row][next_col]). If true, the ball is stuck; break the simulation.
Move the ball to next_col for the next row.
If the ball reaches the last row without getting stuck, record its final column in result[c].
Return the result array.

Why it works: Each ball moves independently and the only factors that stop it are well-defined: walls and "V" shapes. Simulating the path preserves these conditions exactly, ensuring correctness.

Python Solution

from typing import List

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        result = [-1] * n
        
        for c in range(n):
            col = c
            for row in range(m):
                next_col = col + grid[row][col]
                if next_col < 0 or next_col >= n or grid[row][col] != grid[row][next_col]:
                    col = -1
                    break
                col = next_col
            result[c] = col
            
        return result

This implementation initializes the results to -1 for each column. For each ball, it simulates movement row by row, updating the column according to the board's direction and checking for boundaries or "V" shapes. If the ball successfully reaches the last row, its final column is recorded; otherwise, -1 remains.

Go Solution

func findBall(grid [][]int) []int {
    m, n := len(grid), len(grid[0])
    result := make([]int, n)
    
    for c := 0; c < n; c++ {
        col := c
        for row := 0; row < m; row++ {
            nextCol := col + grid[row][col]
            if nextCol < 0 || nextCol >= n || grid[row][col] != grid[row][nextCol] {
                col = -1
                break
            }
            col = nextCol
        }
        result[c] = col
    }
    
    return result
}

The Go version mirrors the Python logic. The main differences are slice initialization and using := for variable declarations. Go does not need type hints due to static typing.

Worked Examples

Example 1: 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]]

Ball	Path Simulation	Result
0	col=0 → 1 → 2 → 2 → 3 → 1	1
1	col=1 → 2 → 2 → stuck ("V" shape)	-1
2	col=2 → 3 → stuck	-1
3	col=3 → 2 → stuck	-1
4	col=4 → 3 → stuck	-1

Output: [1,-1,-1,-1,-1]

Example 2: grid = [[-1]]

Ball 0 immediately hits the left wall, so result is [-1].

Example 3: 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]]

Balls 0-4 move freely to the next column, while ball 5 hits the wall. Output: [0,1,2,3,4,-1].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each of the n balls is simulated over m rows.
Space	O(n)	Store the result for each ball; no additional data structures are needed.

The simulation is efficient because the maximum total operations are 10,000, which is acceptable under the problem constraints.

Test Cases

# Provided examples
assert Solution().findBall([[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]]) == [1,-1,-1,-1,-1]
assert Solution().findBall([[-1]]) == [-1]
assert Solution().findBall([[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]) == [0,1,2,3,4,-1]

# Edge cases
assert Solution().findBall([[1]]) == [0]  # Single cell, ball exits
assert Solution().findBall([[-1,1]]) == [-1,1]  # Ball stuck on left, free on right
assert Solution().findBall([[1,-1],[1,-1]]) == [-1,-1]  # "V" traps for both balls

Test	Why
[[1,1,1,-1,-1],...]]	Typical mixed grid, tests multiple stuck and free balls
[[-1]]	Single cell, ball stuck against wall
[[1,1,1,1,1,1],...]	Alternating row patterns, tests ball movement across multiple rows
[[1]]	Single cell, ball exits directly
[[-1,1]]	Small 1x2 grid, tests boundary movement
[[1,-1],[1,-1]]	2x2 "V" shape, tests balls getting stuck in adjacent cells

Edge Cases

One important edge case is a grid with a single column. Here, any -1 immediately causes the ball to get stuck, while a 1 allows the ball to pass through. The