Where Will the Ball Fall - Practice Coding Problems

Where Will the Ball Fall - Problem

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.

Input & Output

Example 1 — Basic Grid

$ 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]

💡 Note: Ball 0 drops at column 0, follows right-pointing boards and exits at column 1. Other balls get stuck due to V-patterns or hitting walls.

Example 2 — Simple Case

$ Input: grid = [[-1]]

› Output: [-1]

💡 Note: Single cell with left-pointing board. Ball hits the left wall immediately and gets stuck.

Example 3 — All Pass Through

$ 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: [-1,-1,-1,-1,-1,-1]

💡 Note: All balls get stuck because row 0 directs right but row 1 directs left, creating V-patterns everywhere.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with 1 (right-pointing) and -1 (left-pointing) diagonal boards

Ball Simulation

Each ball follows board directions, gets stuck on V-patterns or walls

Output Array

Final exit column for each ball, or -1 if stuck

Key Takeaway

🎯 Key Insight: A ball gets stuck when adjacent boards create a V-pattern (point toward each other) or when it hits a wall

Asked in

a Amazon 25 M Microsoft 18 G Google 12

The key insight is that a ball gets stuck when it encounters a V-shaped pattern (adjacent boards pointing toward each other) or hits a wall. We simulate each ball's path by following board directions and checking for these collision conditions. Best approach is simulation with Time: O(m×n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Simulation	O(m × n)	O(1)	Simulate each ball's path through the grid row by row

Simulation — Algorithm Steps

For each starting column, simulate the ball's journey
At each row, move ball based on board direction (1=right, -1=left)
Check for V-patterns and walls that would trap the ball
Return final column or -1 if stuck

Visualization

Tap to expand

Step-by-Step Walkthrough

Drop Balls

Start one ball at top of each column

Follow Boards

Each ball follows diagonal board direction (1=right, -1=left)

Check Collisions

Ball gets stuck on V-patterns or walls, otherwise continues down

Final Position

Record exit column or -1 if stuck

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int** grid, int gridSize, int* gridColSize, int* returnSize) {
    int m = gridSize, n = gridColSize[0];
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = n;
    
    for (int startCol = 0; startCol < n; startCol++) {
        int col = startCol;
        
        for (int row = 0; row < m; row++) {
            // Current board direction
            int direction = grid[row][col];
            // Next column after following the board
            int nextCol = col + direction;
            
            // Check if ball hits wall
            if (nextCol < 0 || nextCol >= n) {
                col = -1;
                break;
            }
            
            // Check for V-pattern (ball gets stuck)
            if (grid[row][nextCol] != direction) {
                col = -1;
                break;
            }
            
            col = nextCol;
        }
        
        result[startCol] = col;
    }
    
    return result;
}

int main() {
    // Simple parsing for demonstration - in practice would need more robust JSON parsing
    int grid[4][4] = {{1,-1,-1,1},{1,-1,-1,-1},{-1,1,1,1},{1,1,1,-1}};
    int* gridArray[4] = {grid[0], grid[1], grid[2], grid[3]};
    int gridColSize[4] = {4, 4, 4, 4};
    int returnSize;
    
    int* result = solution(gridArray, 4, gridColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

We simulate n balls, each traversing m rows in worst case

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for tracking ball position

✓ Linear Space

67.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler