Sponsored
Sponsored
Use depth-first search (DFS) to simulate the movement of each ball from the top to the bottom, keeping track of the ball's column. If a ball encounters a 'V' shape or hits the wall, it gets stuck. This approach simulates the scenario for each ball individually.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for the result and recursion stack.
1class Solution {
2 public int findExit(int[][] grid, int row, int col) {
3 if (row == grid.length) return col;
4 int nextCol = col + grid[row][col];
5 if (nextCol < 0 || nextCol >= grid[0].length || grid[row][nextCol] != grid[row][col]) return -1;
6 return findExit(grid, row + 1, nextCol);
7 }
8
9 public int[] findBall(int[][] grid) {
10 int n = grid[0].length;
11 int[] result = new int[n];
12 for (int i = 0; i < n; i++) {
13 result[i] = findExit(grid, 0, i);
14 }
15 return result;
16 }
17}In the Java solution, we define a helper method to recursively trace the ball’s path. The main method iterates over each column to simulate ball drops and accumulates results. Output indicates either a fall-through column or a stuck status for each ball.
Utilize nested loops to simulate the motion of each ball iteratively instead of using recursion. It tracks each movement step-by-step across the grid, calculates next positions, transitions to subsequent rows, and monitors for blockages or exits.
Time Complexity: O(m * n), driven by iterating through all cells.
Space Complexity: O(n), where n stands for the result array requirement.
1 public int[] FindBall(int[][] grid) {
int n = grid[0].Length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int col = i;
foreach (var row in grid) {
int nextCol = col + row[col];
if (nextCol < 0 || nextCol >= n || row[nextCol] != row[col]) {
col = -1;
break;
}
col = nextCol;
}
result[i] = col;
}
return result;
}
}The C# solution executes ball movement in the grid with loop-based simulation rather than recursion. Pairs of condition and movement checks provide responsible progression for the ball's travel path to be either completed (exited) or halted (stuck) conclusively.