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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int findPath(vector<vector<int>>& grid, int row, int col) {
7 if (row == grid.size()) return col;
8 int nextCol = col + grid[row][col];
9 if (nextCol < 0 || nextCol >= grid[0].size() || grid[row][nextCol] != grid[row][col]) return -1;
10 return findPath(grid, row + 1, nextCol);
11 }
12
13 vector<int> findBall(vector<vector<int>>& grid) {
14 vector<int> result(grid[0].size(), 0);
15 for (int i = 0; i < grid[0].size(); ++i) {
16 result[i] = findPath(grid, 0, i);
17 }
18 return result;
19 }
20};The C++ solution follows the same DFS logic but utilizes C++'s standard library for handling vectors. The recursive function seeks the ball's landing column or indicates if it is stuck. Balls are processed individually across columns and their outcomes are stored in a vector.
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.
1In JavaScript, loops replicate the process of tracking each ball column's fate iteratively. Step-by-step checks thoroughly ascertain each ball's direction outcome, capturing exit points, or stuck places simply and clearly, without recursion.