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.
1var findBall = function(grid) {
2 const dfs = (row, col) => {
3 if (row === grid.length) return col;
4 const nextCol = col + grid[row][col];
5 if (nextCol < 0 || nextCol >= grid[0].length || grid[row][nextCol] !== grid[row][col]) return -1;
6 return dfs(row + 1, nextCol);
7 };
8 return Array.from({length: grid[0].length}, (_, col) => dfs(0, col));
9};This JavaScript function uses a depth-first recursive lambda to track each ball's navigation. By using Array.from and lambda expressions, results for each column simulate precisely where the ball concludes - with a clear distinction for ball escapes versus entrapment.
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.
1The depicted solution navigates through the grid iteratively, using nested loops that calculate each ball's position directly - no recursion. It checks for every cell iteratively to establish if the ball has fallen out or remained trapped in the simulation.