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 <stdio.h>
2#include <stdlib.h>
3
4int dfs(int **grid, int m, int n, int row, int col) {
5 if (row == m) return col;
6 int nextCol = col + grid[row][col];
7 if (nextCol < 0 || nextCol >= n || grid[row][nextCol] != grid[row][col]) return -1;
8 return dfs(grid, m, n, row + 1, nextCol);
9}
10
11int* findBall(int** grid, int gridSize, int* gridColSize, int* returnSize) {
12 *returnSize = *gridColSize;
13 int *result = (int *)malloc((*gridColSize) * sizeof(int));
14 for (int i = 0; i < *gridColSize; ++i) {
15 result[i] = dfs(grid, gridSize, *gridColSize, 0, i);
16 }
17 return result;
18}We define a recursive depth-first search function that simulates the ball's journey through the grid. It returns the column at the bottom if the ball falls through, or -1 if it gets stuck. We iterate over each column to drop a ball and compute its result using this DFS function.
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.
1using namespace std;
class Solution {
public:
vector<int> findBall(vector<vector<int>>& grid) {
vector<int> result(grid[0].size(), 0);
for (int i = 0; i < grid[0].size(); ++i) {
int col = i;
for (int row = 0; row < grid.size(); ++row) {
int nextCol = col + grid[row][col];
if (nextCol < 0 || nextCol >= grid[0].size() || grid[row][nextCol] != grid[row][col]) {
col = -1;
break;
}
col = nextCol;
}
result[i] = col;
}
return result;
}
};A straightforward transition allows the C++ version to iteratively simulate the function. A nested loop sequence helps identify whether each ball successfully traverses the grid or ends with it stuck condition - calculating step-by-step to retain accuracy.