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 def findBall(self, grid):
3 def dfs(row, col):
4 if row == len(grid):
5 return col
6 next_col = col + grid[row][col]
7 if next_col < 0 or next_col >= len(grid[0]) or grid[row][next_col] != grid[row][col]:
8 return -1
9 return dfs(row + 1, next_col)
10
11 return [dfs(0, col) for col in range(len(grid[0]))]For Python, a nested DFS function is used within the main function to explore the trajectory of each ball. The list comprehension gathers results from exploring each initial column, either obtaining the exit column or a stuck indication.
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.