Where Will the Ball Fall

medium simulation matrix

Problem

An m×n grid of 1 (↘) and −1 (↙) diagonals diverts balls dropped from each top column. Return for each column the bottom column it exits through, or −1 if wedged.

Inputgrid = [[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]

Only column 0 makes it through.

grid rows ';' separated, 1 or -1 csv

def find_ball(grid):
    m, n = len(grid), len(grid[0])
    out = []
    for start in range(n):
        col = start
        for r in range(m):
            nxt = col + grid[r][col]
            if nxt < 0 or nxt >= n or grid[r][nxt] != grid[r][col]:
                col = -1; break
            col = nxt
        out.append(col)
    return out

function findBall(grid) {
  const m = grid.length, n = grid[0].length, out = [];
  for (let start = 0; start < n; start++) {
    let col = start;
    for (let r = 0; r < m; r++) {
      const nxt = col + grid[r][col];
      if (nxt < 0 || nxt >= n || grid[r][nxt] !== grid[r][col]) { col = -1; break; }
      col = nxt;
    }
    out.push(col);
  }
  return out;
}

class Solution {
    public int[] findBall(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] out = new int[n];
        for (int start = 0; start < n; start++) {
            int col = start;
            for (int r = 0; r < m; r++) {
                int nxt = col + grid[r][col];
                if (nxt < 0 || nxt >= n || grid[r][nxt] != grid[r][col]) { col = -1; break; }
                col = nxt;
            }
            out[start] = col;
        }
        return out;
    }
}

vector<int> findBall(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> out(n);
    for (int start = 0; start < n; start++) {
        int col = start;
        for (int r = 0; r < m; r++) {
            int nxt = col + grid[r][col];
            if (nxt < 0 || nxt >= n || grid[r][nxt] != grid[r][col]) { col = -1; break; }
            col = nxt;
        }
        out[start] = col;
    }
    return out;
}

Explanation

Each cell holds a diagonal board: 1 sends a ball down-right and -1 sends it down-left. The idea is simply to simulate each ball one row at a time and see where it ends up, or whether it gets stuck.

For a ball in col on row r, the board deflects it sideways by grid[r][col], so the next column is nxt = col + grid[r][col]. We move the ball down to that column and continue to the next row.

The ball gets wedged in two cases: it slides off the left or right wall (nxt < 0 or nxt >= n), or the neighbor board points the opposite way (grid[r][nxt] != grid[r][col]), forming a V shape that traps it. Either case sets the answer to -1 and breaks.

If the ball survives all m rows, the final col is the bottom column it exits. We repeat this for every starting column to build the output list.

Example: a ball whose board says go right but whose right neighbor says go left meets a wall of two boards angled toward each other — it can't pass, so that column's result is -1.

Time: O(m·n) Space: O(n)