Where Will the Ball Fall

Med

#1564Time: O(m * n). For each of the `n` balls, the simulation involves traversing `m` rows. The recursion depth is `m`, and each recursive call takes constant time.Space: O(m). The recursion can go up to a depth of `m` (the number of rows), so the function call stack will use O(m) space. This is in addition to the O(n) space for the output array.

Data structures

Array Matrix

Prompt

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 i^th 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.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] is 1 or -1.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the path of each ball using a recursive function. For each ball dropped at the top of a column, a recursive function traces its path downwards, row by row. The function checks for conditions that would cause the ball to get stuck at each step. If the ball successfully reaches the bottom, the function returns its final column; otherwise, it returns -1.

Algorithm

Create an integer array answer of size n.
Loop through each column i from 0 to n-1.
For each i, call a recursive helper function findPath(0, i, grid).
Store the result of the helper function in answer[i].
The findPath(row, col, grid) function:
- a. If row equals the number of rows m, it means the ball has passed through. Return col.
- b. Calculate nextCol = col + grid[row][col].
- c. If nextCol is out of bounds (< 0 or >= n) or if grid[row][col] is not equal to grid[row][nextCol] (forming a 'V' shape), the ball is stuck. Return -1.
- d. Otherwise, the ball continues to the next row. Return the result of findPath(row + 1, nextCol, grid).
After the loop, return the answer array.

Walkthrough

We define a helper function, say findBallDropColumn(row, col), which simulates the ball's path starting from (row, col). The main function iterates through each starting column i from 0 to n-1 and calls this helper function with findBallDropColumn(0, i). The results are collected into an answer array.

The findBallDropColumn function works as follows:

Base Case: If the current row is equal to m (the total number of rows), it means the ball has successfully fallen through the bottom of the box. We return the current col.
Stuck Conditions: We determine the direction of deflection direction = grid[row][col] and calculate the next column nextCol = col + direction. We then check for two stuck conditions:
1. Wall Collision: If nextCol is out of bounds (less than 0 or greater than or equal to n), the ball is stuck. Return -1.
2. "V" Shape Trap: If the board in the adjacent cell grid[row][nextCol] has an opposing direction (grid[row][nextCol] != direction), the ball is stuck. Return -1.
Recursive Step: If the ball is not stuck, it moves to the next row at the new column. We make a recursive call: findBallDropColumn(row + 1, nextCol).

1class Solution {2    public int[] findBall(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5        int[] answer = new int[n];6        for (int i = 0; i < n; i++) {7            answer[i] = findBallDropColumn(0, i, grid);8        }9        return answer;10    }11 12    private int findBallDropColumn(int row, int col, int[][] grid) {13        // Base case: Ball has fallen out of the bottom.14        if (row == grid.length) {15            return col;16        }17 18        int nextCol = col + grid[row][col];19 20        // Check for stuck conditions21        // 1. Hits a wall22        if (nextCol < 0 || nextCol >= grid[0].length) {23            return -1;24        }25        // 2. Forms a 'V' shape26        if (grid[row][col] != grid[row][nextCol]) {27            return -1;28        }29 30        // Recursive step: move to the next row31        return findBallDropColumn(row + 1, nextCol, grid);32    }33}

Complexity

Time

O(m * n). For each of the `n` balls, the simulation involves traversing `m` rows. The recursion depth is `m`, and each recursive call takes constant time.

Space

O(m). The recursion can go up to a depth of `m` (the number of rows), so the function call stack will use O(m) space. This is in addition to the O(n) space for the output array.

Trade-offs

Pros

The code can be very clean and closely mirrors the problem's logic of a ball moving from one state (row) to the next.
It's a natural way to think about path-finding problems.

Cons

Can lead to a StackOverflowError for very large m, although the problem constraints (m <= 100) make this unlikely.
Generally less space-efficient than an iterative solution due to the overhead of the function call stack.

This approach simulates the path of each ball using nested loops. The outer loop iterates through each ball, and the inner loop simulates its journey downwards through the rows of the grid. This avoids recursion and its associated overhead, making it more space-efficient.

Algorithm

Create an integer array answer of size n.
Loop through each starting column i from 0 to n-1.
Initialize a variable currentCol = i to track the ball's column.
Loop through each row r from 0 to m-1.
- a. Calculate the next potential column: nextCol = currentCol + grid[r][currentCol].
- b. Check for stuck conditions: if nextCol is out of bounds (< 0 or >= n) or if a 'V' shape is formed (grid[r][currentCol] != grid[r][nextCol]), the ball is stuck. Set currentCol = -1 and break the inner loop over rows.
- c. If the move is valid, update currentCol = nextCol.
After the inner loop finishes, assign the final value of currentCol to answer[i].
After the outer loop completes, return the answer array.

Walkthrough

We initialize an answer array of size n to store the results. We then iterate through each starting column i from 0 to n-1. For each i, we trace the path of one ball.

We use a variable, currentCol, initialized to i, to keep track of the ball's current column position. We then start an inner loop that iterates through each row r from 0 to m-1.

Inside the inner loop, for each cell (r, currentCol), we determine the ball's next move.

Let direction = grid[r][currentCol].
The ball intends to move to nextCol = currentCol + direction.
We check for the two stuck conditions:
1. Wall Collision: nextCol is out of bounds (< 0 or >= n).
2. "V" Shape Trap: The adjacent board grid[r][nextCol] has an opposing direction (grid[r][nextCol] != direction).
If either condition is met, the ball is stuck. We set currentCol to -1 and break out of the inner (row) loop.
If the move is valid, we update currentCol to nextCol and continue to the next row.

After the inner loop finishes (either by completing all rows or breaking early), the final value of currentCol (which is either the exit column or -1) is stored in answer[i]. After the outer loop completes, the answer array is returned.

1class Solution {2    public int[] findBall(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5        int[] answer = new int[n];6 7        for (int i = 0; i < n; i++) {8            int currentCol = i;9            for (int r = 0; r < m; r++) {10                int nextCol = currentCol + grid[r][currentCol];11 12                // Check for stuck conditions13                if (nextCol < 0 || nextCol >= n || grid[r][currentCol] != grid[r][nextCol]) {14                    currentCol = -1; // Ball is stuck15                    break;16                }17                18                // Move to the next column for the next row19                currentCol = nextCol;20            }21            answer[i] = currentCol;22        }23        return answer;24    }25}

Complexity

Time

O(m * n). We have two nested loops. The outer loop runs `n` times (for each ball), and the inner loop runs `m` times (for each row). The operations inside the inner loop are constant time.

Space

O(1) auxiliary space. We only use a few variables to track the state of the current ball. The O(n) space for the output array is typically not counted as extra space.

Trade-offs

Pros

More space-efficient than the recursive approach as it avoids the overhead of the function call stack.
No risk of StackOverflowError, making it more robust for deep grids.
The logic is straightforward and easy to follow for those more comfortable with iterative solutions.

Cons

The code might be slightly more verbose than a compact recursive solution, requiring explicit state management with a loop variable.

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[][] grid;8public9  int[] findBall(int[][] grid) {10    m = grid.length;11    n = grid[0].length;12    this.grid = grid;13    int[] ans = new int[n];14    for (int j = 0; j < n; ++j) {15      ans[j] = dfs(0, j);16    }17    return ans;18  }19private20  int dfs(int i, int j) {21    if (i == m) {22      return j;23    }24    if (j == 0 && grid[i][j] == -1) {25      return -1;26    }27    if (j == n - 1 && grid[i][j] == 1) {28      return -1;29    }30    if (grid[i][j] == 1 && grid[i][j + 1] == -1) {31      return -1;32    }33    if (grid[i][j] == -1 && grid[i][j - 1] == 1) {34      return -1;35    }36    return grid[i][j] == 1 ? dfs(i + 1, j + 1) : dfs(i + 1, j - 1);37  }38}

1/** * @param {number[][]} grid * @return {number[]} */ var findBall = function (2  grid,3) {4  const m = grid.length;5  const n = grid[0].length;6  const dfs = (i, j) => {7    if (i === m) {8      return j;9    }10    if (grid[i][j] === 1) {11      if (j === n - 1 || grid[i][j + 1] === -1) {12        return -1;13      }14      return dfs(i + 1, j + 1);15    } else {16      if (j === 0 || grid[i][j - 1] === 1) {17        return -1;18      }19      return dfs(i + 1, j - 1);20    }21  };22  return Array.from({ length: n }, (_, j) => dfs(0, j));23};

1class Solution {2public:3  vector<int> findBall(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    vector<int> ans(n);6    function<int(int, int)> dfs = [&](int i, int j) {7      if (i == m) {8        return j;9      }10      if (j == 0 && grid[i][j] == -1) {11        return -1;12      }13      if (j == n - 1 && grid[i][j] == 1) {14        return -1;15      }16      if (grid[i][j] == 1 && grid[i][j + 1] == -1) {17        return -1;18      }19      if (grid[i][j] == -1 && grid[i][j - 1] == 1) {20        return -1;21      }22      return grid[i][j] == 1 ? dfs(i + 1, j + 1) : dfs(i + 1, j - 1);23    };24    for (int j = 0; j < n; ++j) {25      ans[j] = dfs(0, j);26    }27    return ans;28  }29};

1class 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 )]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem