Taro Logo

Where Will the Ball Fall

#1893 Most AskedMedium
19 views
Topics:
Arrays

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

  • A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
  • A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

Example 1:

Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]
Explanation: This example is shown in the photo.
Ball b0 is dropped at column 0 and falls out of the box at column 1.
Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1.
Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.
Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.
Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.

Example 2:

Input: grid = [[-1]]
Output: [-1]
Explanation: The ball gets stuck against the left wall.

Example 3:

Input: grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
Output: [0,1,2,3,4,-1]

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] is 1 or -1.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the dimensions of the grid? What are the maximum possible values for rows and columns?
  2. Can the grid contain values other than 1 and -1? What should I do if I encounter an invalid value?
  3. If the ball gets stuck (e.g., hits a 'V' shape), what value should I return for that column?
  4. Is the grid guaranteed to be rectangular (i.e., all rows have the same number of columns)?
  5. Are edge cases such as an empty grid or a grid with zero rows/columns possible?

Brute Force Solution

Approach

Imagine dropping a ball at the top of a grid. The brute force way is to just follow the ball as it moves, checking each step of the way. If the ball gets stuck or goes off the edge, we just say it got stuck at that starting column.

Here's how the algorithm would work step-by-step:

  1. Start with the ball at the top of the grid, in the first column.
  2. Look at the current place the ball is and see which way the grid directs it (left or right).
  3. Move the ball in that direction to the next spot in the grid.
  4. Keep moving the ball until it either reaches the bottom of the grid, or gets stuck because the grid pushes it off an edge.
  5. If the ball reaches the bottom, the column it lands in is where it ends up.
  6. If the ball gets stuck before the bottom, then that means the ball is stuck at the starting column.
  7. Repeat this process, starting the ball at the top of the grid for every other column on the top row.
  8. Write down where the ball ends up (or that it got stuck) for each of those starting columns.

Code Implementation

def where_will_the_ball_fall(grid):
    number_of_columns = len(grid[0])
    results = []

    for starting_column in range(number_of_columns):
        current_column = starting_column
        current_row = 0

        while current_row < len(grid):
            direction = grid[current_row][current_column]

            # Check for left or right edge collision
            if (direction == 1 and current_column == number_of_columns - 1) or \
               (direction == -1 and current_column == 0):
                current_column = -1
                break

            next_column = current_column + direction

            # Check for V shape collision
            if grid[current_row][next_column] != direction:
                current_column = -1
                break

            current_column = next_column
            current_row += 1

        results.append(current_column)

    return results

Big(O) Analysis

Time Complexity
O(m*n) – The algorithm simulates dropping a ball from each of the n columns at the top of the grid. For each starting column, the ball traverses at most m rows of the grid before reaching the bottom or getting stuck. Therefore, in the worst case, we perform m operations for each of the n starting columns. This leads to a total of m*n operations, resulting in a time complexity of O(m*n), where m is the number of rows and n is the number of columns.
Space Complexity
O(1) – The algorithm's space complexity is O(1) because it primarily uses a constant number of variables to track the ball's position (row and column indices) during its traversal of the grid. No auxiliary data structures that scale with the input grid's dimensions (rows x columns) are created. The amount of extra memory required remains constant regardless of the grid's size; therefore, the space complexity is constant.

Optimal Solution

Approach

The problem asks us to simulate a ball falling through a grid of angled planks. The key insight is to track the ball's horizontal position as it moves down row by row, determining if it gets deflected or if it continues straight. If the ball gets stuck before reaching the bottom, we report where it got stuck; otherwise, we report its final column.

Here's how the algorithm would work step-by-step:

  1. Imagine each ball starts above the first row at its specified column.
  2. For each row, look at the current cell the ball is in.
  3. If the plank in that cell points to the right, check the cell to the right of it. If that cell also points right, the ball can move diagonally down and to the right. If not (either it points left, or is the end of the grid), the ball gets stuck.
  4. If the plank points to the left, check the cell to the left. If that cell also points left, the ball can move diagonally down and to the left. If not, the ball gets stuck.
  5. If the ball makes it to the next row, update its horizontal position based on whether it moved left or right.
  6. Repeat this process for each row until the ball either gets stuck or reaches the bottom of the grid.
  7. If the ball gets stuck, record that it got stuck at the current column. If it reaches the bottom, record its final column position.

Code Implementation

def where_will_the_ball_fall(grid):
    number_of_columns = len(grid[0])
    results = []

    for starting_column in range(number_of_columns):
        current_column = starting_column
        
        for row_index in range(len(grid)):
            current_value = grid[row_index][current_column]
            
            # Check for rightward movement
            if current_value == 1:
                next_column = current_column + 1
                if next_column == number_of_columns or grid[row_index][next_column] == -1:

                    results.append(-1)
                    current_column = -1
                    break
                else:
                    current_column = next_column

            # Check for leftward movement
            elif current_value == -1:
                next_column = current_column - 1
                if next_column < 0 or grid[row_index][next_column] == 1:

                    results.append(-1)
                    current_column = -1
                    break
                else:
                    current_column = next_column
        
        # Ball made it to the bottom
        if current_column != -1:
            results.append(current_column)
            
    return results

Big(O) Analysis

Time Complexity
O(m * n) – The algorithm iterates through each ball's path through the grid. The outer loop implicitly considers each ball (though there is no loop over balls specifically mentioned in the above description - if there were B balls it would be B*m*n, however the described algorithm performs the operation for a single ball's path). For a single ball, the algorithm then traverses each row (m rows) in the grid. Within each row, a constant number of operations are performed: checking the current cell and potentially the adjacent cell. Therefore, the time complexity is determined by the number of rows (m) multiplied by the number of columns (n) that the ball traverses. The total operations are then approximately m * n, which simplifies to O(m * n).
Space Complexity
O(1) – The algorithm operates in place and does not create any auxiliary data structures whose size depends on the dimensions of the input grid. Only a few integer variables are used to track the ball's current column position. Therefore, the extra space used is constant regardless of the input grid's size (number of rows and columns), resulting in O(1) space complexity.

Edge Cases

Empty grid
How to Handle:
Return an array of -1s with the same length as the number of columns.
Grid with zero columns
How to Handle:
Return an empty array since there are no columns to process.
Ball gets stuck at the top row due to a 'V' shape at the beginning
How to Handle:
Handle by immediately returning -1 if the ball gets stuck in the first row.
Ball gets stuck in the middle due to a 'V' shape
How to Handle:
The algorithm should correctly detect if the ball gets stuck on any row and return -1.
Ball reaches the bottom row successfully but falls off to the left
How to Handle:
The algorithm must check for boundary conditions after the simulated path to make sure it doesn't fall off the edge, and return -1 if it does.
Ball reaches the bottom row successfully but falls off to the right
How to Handle:
The algorithm must check for boundary conditions after the simulated path to make sure it doesn't fall off the edge, and return -1 if it does.
Grid with very large dimensions that could cause performance issues
How to Handle:
The algorithm has a time complexity proportional to the number of cells so it can be optimized using techniques like memoization if needed for extremely large grids.
The grid has only one row
How to Handle:
Handle the case where a ball immediately falls off after the first move.
0/1916 completed