1706. Where Will the Ball Fall
Problem Description
In the given problem, we have a box represented by a 2-D grid of size m x n, where m is the number of rows and n is the number of columns. There are n balls that we will be dropping from each column's top. Each cell in the grid has a diagonal board that can either redirect the ball to the right or to the left. The boards are represented by either a 1 (redirects to the right) or a -1 (redirects to the left). Our objective is to determine the final column where each ball lands at the bottom, or decide that the ball is stuck in the box. A ball is considered stuck if it encounters a 'V' shaped pattern formed by two adjacent cells with diagonal boards pointing towards each other or if it is redirected into a wall.
To summarize, we need to simulate the path of each ball dropped from the top and see where, if at all, it comes out at the bottom. We must return an array where each index contains the column number where the corresponding ball exits, or -1 if the ball gets stuck.
Intuition
When thinking about the solution, it seems evident that we need to track the journey of each ball from the moment it is dropped until it reaches the bottom or gets stuck. We can do this using Depth-First Search (DFS). The DFS will begin at the top of each column and move step by step, analyzing the board's direction in the current cell.
The intuition behind the solution is as follows:
- Start from the
0throw of every column and attempt to trace the path of the ball to the bottom. - If the ball is directed right (
1), we need to ensure that the next column is also directing the ball right, otherwise, it will get stuck. - If the ball is directed left (
-1), we must check that the previous column also keeps directing the ball left, for the same reason as above. - If the ball is on the leftmost or rightmost side, check if the direction of the board does not push it into the wall; if it does, the ball gets stuck.
- If none of these conditions are met, the ball proceeds to the next row in whichever direction the board is pointing.
- If the ball reaches the bottom (
mthrow), we have found the column where the ball exits.
The dfs function takes care of these considerations for each ball, and it's called for each column at the top of the grid. The result of these dfs calls is stored in an array, which is then returned as the solution.
The code uses recursion in the dfs function to trace the path of the ball until it either reaches the bottom (and the column is returned) or gets stuck (and -1 is returned).
Learn more about Depth-First Search and Dynamic Programming patterns.
Which two pointer techniques do you use to check if a string is a palindrome?
Solution Approach
The solution implements a recursive Depth-First Search (DFS) function dfs which takes two parameters, i and j, corresponding to the current cell's row and column indexes. It attempts to follow the ball's path from the top of the column where it is dropped, until it either falls out of the grid or gets stuck according to the rules described in the problem.
Here is a step-by-step walkthrough of the recursive dfs function implemented in the solution:
-
Base Case: If
iequals the number of rowsm, it means the ball has reached the bottom of the grid. The function then returns the column indexj, indicating the exit column. -
Boundary Check: If the ball is at the first column and the current board directs to the left (
grid[i][j] == -1), or it's at the last column and the board directs to the right (grid[i][j] == 1), the ball is stuck because it will collide with the wall. In these cases, the function returns-1. -
V-shaped Pattern Check: If the current board directs the ball to the right (
grid[i][j] == 1) but the next column's board directs to the left (grid[i][j + 1] == -1), the ball is stuck in a 'V' shaped pattern. The same check applies if the current board directs left (grid[i][j] == -1) and the previous column's board directs to the right (grid[i][j - 1] == 1). Again, the function returns-1if any of these scenarios occur. -
Recursive Case: If none of these conditions apply, the ball can continue to the next row. The direction is determined by the current board: if
grid[i][j] == 1, the ball will go to the cell on the right (j+1), while ifgrid[i][j] == -1, it will go to the cell on the left (j-1). It then calls itself with the new cell's coordinates and continues the path tracing. -
Loop Through Columns: The function
findBallsets up a loop that goes through all columns (for each ball). "dfs(0, j)" calls the recursivedfsfunction from the top row(0)of each column(j). The results are added to the return list, which eventually contains the outcome for each ball's path.
Itâs important to note that the recursion in this solution serves as backtracking through the grid. At any point, if a ball cannot move downwards, it returns -1, effectively "backtracking" and ending that path. The use of the list comprehension [dfs(0, j) for j in range(n)] succinctly executes this process for each ball and compiles the results into the final list.
In summary, the algorithm employs DFS and checks for boundary conditions as well as path continuity (no 'V' pattern obstruction) to determine the ball's final position. It leverages recursion to elegantly handle the traversal of each possible pathway.
Which technique can we use to find the middle of a linked list?
Example Walkthrough
Let's take a small grid example to illustrate the solution approach to see how the Depth-First Search (DFS) would work.
Consider a 2x3 grid (2 rows and 3 columns):
1[ 2 [ 1, -1, 1], 3 [-1, 1, -1] 4]
There will be 3 balls dropped, each aligning with the columns from left to right (column indexes 0, 1, and 2).
Ball 1 (Column 0):
- Start at
grid[0][0], the board is1, so move right togrid[0][1]. - At
grid[0][1], the board is-1, so move left togrid[1][0]. - At
grid[1][0], the board is-1, and we are at the leftmost column so the ball can't move and gets stuck. The result is-1.
Ball 2 (Column 1):
- Start at
grid[0][1], the board is-1, so move left togrid[0][0]. - At
grid[0][0], the board is1, so move right togrid[1][1]. - At
grid[1][1], the board is1, so move right togrid[1][2]. - At
grid[1][2], the board is-1, and it's a bottom row so the ball exits from column 2. The result is2.
Ball 3 (Column 2):
- Start at
grid[0][2], the board is1, so the ball tries to move right but hits the wall. It gets stuck. The result is-1.
The DFS function traces these paths:
- For Ball 1, it gets stuck as it cannot move left from
grid[1][0]. - For Ball 2, it successfully exits the grid at column 2.
- For Ball 3, it hits the wall at
grid[0][2]and gets stuck.
The return array for this example should be [-1, 2, -1], indicating the outcomes for the balls corresponding to each column.
To recap, the function findBall applies DFS starting from the first row of each column, determining where the ball will end. It repeatedly calls dfs(0, j) for each starting position j. The conditions in the DFS function account for situations where the ball may get stuck against a wall, in a 'V' pattern, or exit successfully. The return array is built by compiling the results of the DFS for each ball, which in this scenario is [-1, 2, -1].
Solution Implementation
1from typing import List
2
3class Solution:
4 def findBall(self, grid: List[List[int]]) -> List[int]:
5 # Dimensions of the grid
6 rows, cols = len(grid), len(grid[0])
7
8 # Helper function to simulate the ball drop
9 def drop_ball(row: int, col: int) -> int:
10 # Base case: ball has reached the bottom row
11 if row == rows:
12 return col
13 # Edge case: ball is at the leftmost position and is directed left
14 if col == 0 and grid[row][col] == -1:
15 return -1
16 # Edge case: ball is at the rightmost position and is directed right
17 if col == cols - 1 and grid[row][col] == 1:
18 return -1
19 # V-shape case: ball is directed into a wall
20 if grid[row][col] == 1 and grid[row][col + 1] == -1:
21 return -1
22 # Inverted V-shape case: ball is directed into a wall
23 if grid[row][col] == -1 and grid[row][col - 1] == 1:
24 return -1
25 # Recursive case: keep the ball moving according to the direction
26 # If the direction is right (1), move the ball to the next row and next column
27 # If the direction is left (-1), move the ball to the next row and previous column
28 return drop_ball(row + 1, col + grid[row][col])
29
30 # Simulate the drop for each ball positionally indexed from 0 to cols-1
31 # and store their outcomes in a list
32 return [drop_ball(0, col) for col in range(cols)]
331class Solution {
2 // Dimensions of the grid
3 private int rowCount;
4 private int columnCount;
5 // The grid to operate on
6 private int[][] grid;
7
8 // Finds the eventual positions of the balls
9 public int[] findBall(int[][] grid) {
10 // Initialize the dimensions based on the input grid
11 rowCount = grid.length;
12 columnCount = grid[0].length;
13 // Store the grid in the field for easy access
14 this.grid = grid;
15
16 // Result array to store the final position of each ball
17 int[] result = new int[columnCount];
18 // Simulate the path for each ball starting from the top row
19 for (int col = 0; col < columnCount; ++col) {
20 result[col] = dropBall(0, col);
21 }
22 return result;
23 }
24
25 // Runs the simulation for a single ball drop, returning its final position
26 private int dropBall(int row, int col) {
27 // If the ball has reached the bottom row, return the column index
28 if (row == rowCount) {
29 return col;
30 }
31 // Check for out-of-bound scenarios or cases where the ball gets stuck
32 if (col == 0 && grid[row][col] == -1 || col == columnCount - 1 && grid[row][col] == 1 ||
33 grid[row][col] == 1 && grid[row][col + 1] == -1 ||
34 grid[row][col] == -1 && grid[row][col - 1] == 1) {
35 return -1; // Ball is stuck or fell out of the grid
36 }
37 // Recursively drop the ball into the next slot based on the current direction
38 return grid[row][col] == 1 ? dropBall(row + 1, col + 1) : dropBall(row + 1, col - 1);
39 }
40}
411#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Declaring class member variables for the grid dimensions.
7 int rows, cols;
8 vector<vector<int>> board;
9
10 vector<int> findBall(vector<vector<int>>& grid) {
11 // Initialize the member variables with the input grid.
12 this->board = grid;
13 rows = grid.size();
14 cols = grid[0].size();
15
16 // Prepare the answer vector which will hold the final positions of the balls.
17 vector<int> finalPositions(cols);
18
19 // Process each ball starting from the top of each column.
20 for (int col = 0; col < cols; ++col) {
21 finalPositions[col] = dropBall(0, col);
22 }
23
24 // Return the computed final positions of the balls.
25 return finalPositions;
26 }
27
28 int dropBall(int row, int col) {
29 // If we reach the bottom row, return the current column as the ball's final position.
30 if (row == rows) return col;
31
32 // Handle the cases where the ball is stuck:
33 // - at the left edge with a left-tilted cell
34 // - at the right edge with a right-tilted cell
35 // - in a 'V' shaped position
36 // - in an inverted 'V' shaped position
37 if ((col == 0 && board[row][col] == -1) ||
38 (col == cols - 1 && board[row][col] == 1) ||
39 (board[row][col] == 1 && board[row][col + 1] == -1) ||
40 (board[row][col] == -1 && board[row][col - 1] == 1)) {
41 return -1; // Ball is stuck and does not have a final position.
42 }
43
44 // If none of the above cases apply,
45 // continue the recursion in the direction that the cell tilts.
46 return board[row][col] == 1 ? dropBall(row + 1, col + 1) : dropBall(row + 1, col - 1);
47 }
48};
491function findBall(grid: number[][]): number[] {
2 // Get the number of rows (m) and columns (n) from the grid dimensions.
3 const rows = grid.length;
4 const columns = grid[0].length;
5
6 // Initialize the result array with column positions where the ball will exit.
7 const result = new Array(columns).fill(-1); // Preset with -1 to indicate that the ball is stuck.
8
9 // Helper function to perform deep-first search to find the ball's path.
10 const findBallPathDFS = (rowIndex: number, colIndex: number): number => {
11 // If the ball reached the bottom row, return the current column index.
12 if (rowIndex === rows) {
13 return colIndex;
14 }
15 // If the ball is in a V-shaped path (pointing to the right)...
16 if (grid[rowIndex][colIndex] === 1) {
17 // If the ball is at the rightmost column or has a wall to the right, it's stuck.
18 if (colIndex === columns - 1 || grid[rowIndex][colIndex + 1] === -1) {
19 return -1;
20 }
21 // Otherwise, move the ball down and right.
22 return findBallPathDFS(rowIndex + 1, colIndex + 1);
23 } else {
24 // If the ball is in a V-shaped path (pointing to the left)...
25 // If the ball is at the leftmost column or has a wall to the left, it's stuck.
26 if (colIndex === 0 || grid[rowIndex][colIndex - 1] === 1) {
27 return -1;
28 }
29 // Otherwise, move the ball down and left.
30 return findBallPathDFS(rowIndex + 1, colIndex - 1);
31 }
32 };
33
34 // Iterate over each column index to simulate the falling of the ball from that column.
35 for (let columnIndex = 0; columnIndex < columns; columnIndex++) {
36 // Store the result of each ball's path in the result array.
37 result[columnIndex] = findBallPathDFS(0, columnIndex);
38 }
39
40 // Return the updated result array with each ball's exit column (or -1 if stuck).
41 return result;
42}
43Which data structure is used to implement recursion?
Time and Space Complexity
Time Complexity
The function findBall entails a depth-first search (DFS) algorithm that recursively computes the path of each ball within the grid until it reaches the bottom or encounters a blockage.
Since each ball is independent of the others, the complexity for a single ball is dependent on the depth of the recursion, which in this case is the number of rows m. The DFS does not necessarily traverse every row for every ball, as it can be terminated early in case the ball gets stuck. However, in the worst-case scenario where no early termination happens, the recursion depth would be equivalent to m.
Given that we are performing this operation independently for each of the n columns, the overall worst-case time complexity scales linearly with the number of balls, leading to a final time complexity of O(m * n).
Space Complexity
The space complexity primarily stems from the depth of the recursive calls which can go as deep as the number of rows m. In the worst case where the recursion is not terminated early by a blockage, the recursion stack may grow to a depth of m. Therefore, the worst-case space complexity is O(m) due to the recursion stack.
The non-recursion related space consumption is constant as there is a fixed number of variables being used, and no additional data structures that scale with the input size are being maintained. Thus, aside from the space taken up by the input grid itself which we do not usually count in space complexity analysis, the extra space used by the algorithm is proportional to the recursive depth.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.