# Where Will the Ball Fall
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/where-will-the-ball-fall)
Canonical: https://scaleengineer.com/dsa/problems/where-will-the-ball-fall
**Data structures:** Array, Matrix
---
## 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.

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_ `ith` _column at the top, or `-1` if the ball gets stuck in the box._

**Example 1:**

**![](https://assets.glich.co/dsa/where-will-the-ball-fall/image0.jpg)**

**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
## Recursive Simulation (Depth-First Search)
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.
**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.
**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.
### Explanation
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)`.

```java
class Solution {
    public int[] findBall(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = findBallDropColumn(0, i, grid);
        }
        return answer;
    }

    private int findBallDropColumn(int row, int col, int[][] grid) {
        // Base case: Ball has fallen out of the bottom.
        if (row == grid.length) {
            return col;
        }

        int nextCol = col + grid[row][col];

        // Check for stuck conditions
        // 1. Hits a wall
        if (nextCol < 0 || nextCol >= grid[0].length) {
            return -1;
        }
        // 2. Forms a 'V' shape
        if (grid[row][col] != grid[row][nextCol]) {
            return -1;
        }

        // Recursive step: move to the next row
        return findBallDropColumn(row + 1, nextCol, grid);
    }
}
```
### 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.

## Iterative Simulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[] findBall(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int currentCol = i;
            for (int r = 0; r < m; r++) {
                int nextCol = currentCol + grid[r][currentCol];

                // Check for stuck conditions
                if (nextCol < 0 || nextCol >= n || grid[r][currentCol] != grid[r][nextCol]) {
                    currentCol = -1; // Ball is stuck
                    break;
                }
                
                // Move to the next column for the next row
                currentCol = nextCol;
            }
            answer[i] = currentCol;
        }
        return answer;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] grid;
public
  int[] findBall(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int[] ans = new int[n];
    for (int j = 0; j < n; ++j) {
      ans[j] = dfs(0, j);
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    if (i == m) {
      return j;
    }
    if (j == 0 && grid[i][j] == -1) {
      return -1;
    }
    if (j == n - 1 && grid[i][j] == 1) {
      return -1;
    }
    if (grid[i][j] == 1 && grid[i][j + 1] == -1) {
      return -1;
    }
    if (grid[i][j] == -1 && grid[i][j - 1] == 1) {
      return -1;
    }
    return grid[i][j] == 1 ? dfs(i + 1, j + 1) : dfs(i + 1, j - 1);
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number[]} */ var findBall = function (
  grid,
) {
  const m = grid.length;
  const n = grid[0].length;
  const dfs = (i, j) => {
    if (i === m) {
      return j;
    }
    if (grid[i][j] === 1) {
      if (j === n - 1 || grid[i][j + 1] === -1) {
        return -1;
      }
      return dfs(i + 1, j + 1);
    } else {
      if (j === 0 || grid[i][j - 1] === 1) {
        return -1;
      }
      return dfs(i + 1, j - 1);
    }
  };
  return Array.from({ length: n }, (_, j) => dfs(0, j));
};

```

### CPP

```cpp
class Solution {
public:
  vector<int> findBall(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> ans(n);
    function<int(int, int)> dfs = [&](int i, int j) {
      if (i == m) {
        return j;
      }
      if (j == 0 && grid[i][j] == -1) {
        return -1;
      }
      if (j == n - 1 && grid[i][j] == 1) {
        return -1;
      }
      if (grid[i][j] == 1 && grid[i][j + 1] == -1) {
        return -1;
      }
      if (grid[i][j] == -1 && grid[i][j - 1] == 1) {
        return -1;
      }
      return grid[i][j] == 1 ? dfs(i + 1, j + 1) : dfs(i + 1, j - 1);
    };
    for (int j = 0; j < n; ++j) {
      ans[j] = dfs(0, j);
    }
    return ans;
  }
};

```

### Python

```python
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 )]
```