Where Will the Ball Fall
Simulate each ball top-to-bottom, redirecting via the diagonal sign and detecting wall-stuck cases.
Problem#
An m x n grid of diagonal walls: 1 means top-left to bottom-right, -1 means top-right to bottom-left. Drop a ball from each column at the top; for each ball, return the column index it reaches at the bottom, or -1 if it gets stuck.
Examples#
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]]→[1,-1,-1,-1,-1]grid = [[-1]]→[-1]
Constraints#
m == grid.length,n == grid[i].length,1 <= m, n <= 100.
Approach#
For each starting column, simulate row-by-row: at (r, c), the ball goes right if grid[r][c] == 1 (target c+1) or left if grid[r][c] == -1 (target c-1). Stuck conditions: wall against the grid edge, or the adjacent cell’s diagonal points the opposite way (V-shape).
Solution#
class Solution {public: vector<int> findBall(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<int> ans(n, -1); for (int start = 0; start < n; ++start) { int c = start; for (int r = 0; r < m; ++r) { int nc = c + grid[r][c]; if (nc < 0 || nc >= n || grid[r][nc] != grid[r][c]) { c = -1; break; } c = nc; } ans[start] = c; } return ans; }};func findBall(grid [][]int) []int { m, n := len(grid), len(grid[0]) ans := make([]int, n) for i := range ans { ans[i] = -1 } for start := 0; start < n; start++ { c := start for r := 0; r < m; r++ { nc := c + grid[r][c] if nc < 0 || nc >= n || grid[r][nc] != grid[r][c] { c = -1 break } c = nc } ans[start] = c } return ans}from typing import List
class Solution: def findBall(self, grid: List[List[int]]) -> List[int]: m, n = len(grid), len(grid[0]) ans = [-1] * n for start in range(n): c = start for r in range(m): nc = c + grid[r][c] if nc < 0 or nc >= n or grid[r][nc] != grid[r][c]: c = -1 break c = nc ans[start] = c return ansfunction findBall(grid) { const m = grid.length, n = grid[0].length; const ans = new Array(n).fill(-1); for (let start = 0; start < n; start++) { let c = start; for (let r = 0; r < m; r++) { const nc = c + grid[r][c]; if (nc < 0 || nc >= n || grid[r][nc] !== grid[r][c]) { c = -1; break; } c = nc; } ans[start] = c; } return ans;}class Solution { public int[] findBall(int[][] grid) { int m = grid.length, n = grid[0].length; int[] ans = new int[n]; for (int start = 0; start < n; start++) { int c = start; for (int r = 0; r < m; r++) { int nc = c + grid[r][c]; if (nc < 0 || nc >= n || grid[r][nc] != grid[r][c]) { c = -1; break; } c = nc; } ans[start] = c; } return ans; }}function findBall(grid: number[][]): number[] { const m = grid.length, n = grid[0].length; const ans: number[] = new Array(n).fill(-1); for (let start = 0; start < n; start++) { let c = start; for (let r = 0; r < m; r++) { const nc = c + grid[r][c]; if (nc < 0 || nc >= n || grid[r][nc] !== grid[r][c]) { c = -1; break; } c = nc; } ans[start] = c; } return ans;}Editorial#
Two failure modes: the ball runs into the left or right wall (out-of-range nc), or it hits a V-shape — grid[r][c] != grid[r][nc] means the adjacent diagonal forms a pocket. Otherwise the ball slides through to the next row at column nc.
Complexity#
- Time: O(m*n).
- Space: O(1) extra.
Concept revision#
Related#