Leetcode 1706. Where Will the Ball Fall

Problem Explanation

You are given a 2D grid of size m x n and n balls. The grid is representing a box that is open on the top and bottom sides. Each cell in the box contains a diagonal board that redirects a ball to the right or the left. The board that redirects the ball to the right is represented by 1, and the board that redirects the ball to the left is represented by -1. The goal is to find an array of size n, where the i-th element is the column that the i-th ball falls out of at the bottom after dropping the ball from the i-th column at the top, or -1 if the ball gets stuck in the box.

Walkthrough of the Solution

The algorithm provided in the solution is quite simple and effective. It is an iterative solution that cycles through each row of the grid from top to bottom. It initializes an array called dp that keeps track of the status of the columns. Then, it initializes an answer array that will keep track of the ball's final positions. As it moves through the rows, each column is checked to see if the i-th ball has reached its final position or if it is stuck or out of bounds.

The approach is mainly using an iterative and dynamic programming approach to solve the problem. It keeps track of the current state while moving one row at a time to calculate the state of the next row. This means that the algorithm only has to go through the grid once and then the final answer can be determined.

For example, let's consider this grid:

1grid = [[1, 1, 1, -1, -1],
2        [1, 1, 1, -1, -1],
3        [-1, -1, -1, 1, 1],
4        [1, 1, 1, 1, -1],
5        [-1, -1, -1, -1, -1]]

The procedure of algorithm works in this way:

1. Initialize dp array as [0, 1, 2, 3, 4] that holds the status of columns.
2. Initialize ans array as [-1, -1, -1, -1, -1] that will hold the final positions of balls.
3. Iterate through rows, and for each row:
   • Check the status of each column in the row:
     • If the ball is stuck or out of bounds, continue.
     • Otherwise, update the new dp array for the corresponding position for next row.
4. Assign the final position of balls according to the dp array.
5. Return ans array.

The answer for this example would be [1, -1, -1, -1, -1].

Solution in C++

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 public:
9  vector<int> findBall(vector<vector<int>> &grid) {
10    int m = grid.size();
11    int n = grid[0].size();
12    vector<int> dp(n);
13    vector<int> ans(n, -1);
14
15    for (int i = 0; i < n; ++i) {
16      dp[i] = i;
17    }
18
19    for (int i = 0; i < m; ++i) {
20      vector<int> newDp(n, -1);
21      for (int j = 0; j < n; ++j) {
22        if (j + grid[i][j] < 0 || j + grid[i][j] == n) {
23          continue;
24        }
25        if (grid[i][j] == 1 && grid[i][j + 1] == -1 ||
26            grid[i][j] == -1 && grid[i][j - 1] == 1) {
27          continue;
28        }
29        newDp[j + grid[i][j]] = dp[j];
30      }
31      dp = move(newDp);
32    }
33
34    for (int i = 0; i < n; ++i) {
35      if (dp[i] != -1) {
36        ans[dp[i]] = i;
37      }
38    }
39
40    return ans;
41  }
42};
43

Solution in Java

1import java.util.*;
2
3class Solution {
4    public int[] findBall(int[][] grid) {
5        int m = grid.length;
6        int n = grid[0].length;
7        int[] dp = new int[n];
8        int[] ans = new int[n];
9
10        for (int i = 0; i < n; i++) {
11            dp[i] = i;
12            ans[i] = -1;
13        }
14
15        for (int i = 0; i < m; i++) {
16            int[] newDp = new int[n];
17            Arrays.fill(newDp, -1);
18            for (int j = 0; j < n; j++) {
19                if (j + grid[i][j] < 0 || j + grid[i][j] == n) {
20                    continue;
21                }
22                if (grid[i][j] == 1 && grid[i][j + 1] == -1 || grid[i][j] == -1 && grid[i][j - 1] == 1) {
23                    continue;
24                }
25                newDp[j + grid[i][j]] = dp[j];
26            }
27            dp = newDp;
28        }
29
30        for (int i = 0; i < n; i++) {
31            if (dp[i] != -1) {
32                ans[dp[i]] = i;
33            }
34        }
35
36        return ans;
37    }
38}

Solution in Python

1from typing import List
2
3class Solution:
4    def findBall(self, grid: List[List[int]]) -> List[int]:
5        m, n = len(grid), len(grid[0])
6        dp = list(range(n))
7        ans = [-1] * n
8
9        for i in range(m):
10            new_dp = [-1] * n
11            for j in range(n):
12                if j + grid[i][j] < 0 or j + grid[i][j] == n:
13                    continue
14                elif grid[i][j] == 1 and grid[i][j + 1] == -1 or grid[i][j] == -1 and grid[i][j - 1] == 1:
15                    continue
16                else:
17                    new_dp[j + grid[i][j]] = dp[j]
18            dp = new_dp
19
20        for i in range(n):
21            if dp[i] != -1:
22                ans[dp[i]] = i
23
24        return ans

Solution in C#

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int[] FindBall(int[][] grid) {
6        int m = grid.Length;
7        int n = grid[0].Length;
8        int[] dp = new int[n];
9        int[] ans = new int[n];
10
11        for (int i = 0; i < n; i++) {
12            dp[i] = i;
13            ans[i] = -1;
14        }
15
16        for (int i = 0; i < m; i++) {
17            int[] newDp = new int[n];
18            Array.Fill(newDp, -1);
19            for (int j = 0; j < n; j++) {
20                if (j + grid[i][j] < 0 || j + grid[i][j] == n) {
21                    continue;
22                }
23                if (grid[i][j] == 1 && grid[i][j + 1] == -1 || grid[i][j] == -1 && grid[i][j - 1] == 1) {
24                    continue;
25                }
26                newDp[j + grid[i][j]] = dp[j];
27            }
28            dp = newDp;
29        }
30
31        for (int i = 0; i < n; i++) {
32            if (dp[i] != -1) {
33                ans[dp[i]] = i;
34            }
35        }
36
37        return ans;
38    }
39}

Solution in JavaScript

1/**
2 * @param {number[][]} grid
3 * @return {number[]}
4 */
5var findBall = function (grid) {
6  const m = grid.length;
7  const n = grid[0].length;
8  const dp = Array.from({ length: n }, (_, i) => i);
9  const ans = Array(n).fill(-1);
10
11  for (let i = 0; i < m; i++) {
12    const newDp = Array(n).fill(-1);
13    for (let j = 0; j < n; j++) {
14      if (j + grid[i][j] < 0 || j + grid[i][j] === n) {
15        continue;
16      }
17      if (
18        (grid[i][j] === 1 && grid[i][j + 1] === -1) ||
19        (grid[i][j] === -1 && grid[i][j - 1] === 1)
20      ) {
21        continue;
22      }
23      newDp[j + grid[i][j]] = dp[j];
24    }
25    dp = newDp;
26  }
27
28  for (let i = 0; i < n; i++) {
29    if (dp[i] !== -1) {
30      ans[dp[i]] = i;
31    }
32  }
33
34  return ans;
35};

In conclusion, the given solutions for this problem use a combination of iterative algorithms and dynamic programming to calculate the final positions of the balls, efficiently going through the grid once and updating the state for the next step. To implement this, you can follow the code examples provided in different programming languages (C++, Java, Python, C#, JavaScript) and understand the implementation of the algorithm in each language.

The key takeaway from this problem is the ability to maintain the state of the system after each row while moving through the grid. By doing this, the problem becomes much easier to solve as you can track the trajectory of the balls and identify when they are stuck.