Where Will the Ball Fall: Grid Simulation

You have a box made of an m x n grid. Each cell contains a diagonal board that either slants to the right (1, like \) or to the left (-1, like /). You drop a ball from the top of each column and need to find where it exits at the bottom, or determine that it gets stuck. This is LeetCode 1706: Where Will the Ball Fall, and it is a clean exercise in grid simulation with neighbor checking.

Column-by-column simulation

The idea is to simulate each ball independently. For each ball, you start at row 0 in its starting column and walk down row by row. At each cell, the diagonal board tells you which direction the ball is redirected:

• If grid[r][c] == 1 (board slants right \), the ball wants to move to column c + 1.
• If grid[r][c] == -1 (board slants left /), the ball wants to move to column c - 1.

Before moving, you check two things. First, is the target column within bounds? If the board pushes the ball into a wall (column c - 1 when c == 0, or column c + 1 when c == n - 1), the ball is stuck. Second, does the neighboring cell's board slant the same way? If grid[r][c] and grid[r][c + dir] have opposite directions, the two boards form a V-shape that traps the ball.

If neither condition triggers, the ball moves to the next column and drops to the next row. After processing all rows, the ball's final column is the answer for that starting position.

def find_ball(grid: list[list[int]]) -> list[int]:
    m, n = len(grid), len(grid[0])
    result = []

    for col in range(n):
        c = col
        for r in range(m):
            d = grid[r][c]
            nc = c + d
            if nc < 0 or nc >= n or grid[r][nc] != d:
                c = -1
                break
            c = nc
        result.append(c)

    return result

The outer loop iterates over each starting column. The inner loop walks the ball down row by row. At each row, d is the board direction and nc is the candidate next column. If nc is out of bounds or the neighbor board has a different direction, we mark this ball as stuck (-1) and break. Otherwise, the ball moves to column nc and we continue to the next row.

Visual walkthrough

Let's trace ball 0 through the grid step by step. Watch how the ball bounces between right-slanting and left-slanting boards, checking the neighbor at each row before proceeding.

The ball successfully navigated all five rows because at every step, the current cell and its neighbor slanted in the same direction. Whenever two adjacent boards disagree, they form a V-shape or the ball hits a wall, and that ball gets stuck.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. For each of the n balls, you walk through at most m rows. Each row takes O(1) work (one comparison, one bounds check).

Space is O(n) for the result array. The simulation uses only a single variable c to track the current column, so it needs no extra grid or matrix.

Building blocks

1. Grid traversal with simulation

The core pattern here is simulating movement through a grid one step at a time. Instead of searching for a path or exploring all directions, you follow a deterministic rule at each cell. This same "follow the rule, check if you can proceed" pattern appears in problems like robot movement simulation, falling dominos, and spiral traversal. The key is having a clear transition function: given the current position, what is the next position?

2. Boundary and neighbor checking

Before making any move, you verify two conditions: the target cell is within the grid, and the target cell cooperates with the current cell. This "check before you step" pattern prevents index-out-of-bounds errors and handles edge cases naturally. You will see it in any grid problem where movement depends on adjacent cells, such as flood fill, path finding, and matrix rotation.

Edge cases

• Single row: the ball either exits or gets stuck in one step, depending on whether its neighbor agrees
• All same direction: every board slants the same way, so balls flow smoothly (except the one at the boundary wall)
• V-shaped traps: two adjacent cells with opposite diagonals (1 next to -1) form a valley that traps any ball entering from either side
• Wall traps: a board at column 0 slanting left, or a board at column n - 1 slanting right, pushes the ball into the wall

From understanding to recall

You now understand the simulation: walk each ball down row by row, check the neighbor, and either advance or mark it stuck. The logic fits in a short nested loop. But when you sit down in an interview, the details matter. Do you add d or subtract it? Do you check grid[r][nc] or grid[r][c + 1]? Is the stuck condition != or ==?

These are not conceptual gaps. They are recall gaps, and spaced repetition is how you close them. CodeBricks breaks this problem into its simulation loop and neighbor-checking building blocks, then drills them at increasing intervals until the pattern is automatic. You see "simulate movement through a grid" in a problem statement, and the code flows out without hesitation.

Related posts

• Spiral Matrix - another grid traversal problem with boundary tracking
• Rotting Oranges - grid simulation with BFS spreading from multiple sources
• Set Matrix Zeroes - grid manipulation pattern with in-place marking