#1706
Where Will the Ball Fall
pupil · 530 · lc medium +28 · verified · 72.3% accepted · 3,176 likes · top 82%
Description
You have an m x n grid representing an open-top, open-bottom box with n balls dropped one per column. Each cell contains a diagonal board: 1 deflects balls right (top-left to bottom-right) and -1 deflects them left (top-right to bottom-left). A ball gets stuck if it hits a V-shape or a wall.
Return an array answer of size n where answer[i] is the column where the ball from column i exits, or -1 if it gets stuck.
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]
Code
1
2
3