Falling Squares - Practice Coding Problems

Falling Squares - Problem

There are several squares being dropped onto the X-axis of a 2D plane. You are given a 2D integer array positions where positions[i] = [left_i, sideLength_i] represents the i-th square with a side length of sideLength_i that is dropped with its left edge aligned with X-coordinate left_i.

Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.

After each square is dropped, you must record the height of the current tallest stack of squares. Return an integer array ans where ans[i] represents the height described above after dropping the i-th square.

Input & Output

Example 1 — Basic Falling Squares

$ Input: positions = [[1,2],[2,3],[6,1]]

› Output: [2,5,5]

💡 Note: Square 1: [1,2] lands on ground, height = 2, max = 2. Square 2: [2,3] overlaps with Square 1, lands at height 2, new height = 2+3 = 5, max = 5. Square 3: [6,1] no overlap, lands on ground, height = 1, max = 5.

Example 2 — Stacking High

$ Input: positions = [[0,2],[1,2]]

› Output: [2,4]

💡 Note: Square 1: [0,2] lands on ground, height = 2. Square 2: [1,2] overlaps Square 1 (range [1,3] overlaps [0,2]), lands on top, height = 2+2 = 4.

Example 3 — No Overlaps

$ Input: positions = [[0,1],[2,1],[4,1]]

› Output: [1,1,1]

💡 Note: All squares land on ground separately with no overlaps. Each has height 1, so maximum remains 1.

Constraints

1 ≤ positions.length ≤ 1000
1 ≤ left_i ≤ 10⁸
1 ≤ sideLength_i ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of [position, size] for each square

Process

Drop squares one by one, they stack on overlapping squares

Output

Height of tallest stack after each drop

Key Takeaway

🎯 Key Insight: Track the maximum height efficiently by finding overlaps and stacking squares on the highest overlapping base

Asked in

G Google 25 a Amazon 20 f Facebook 15

The key insight is that each square lands on the highest existing square it overlaps with horizontally. Best approach uses coordinate compression + segment tree for efficient range maximum queries. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n²)	O(n)	For each square, check all previously dropped squares to find landing height
Coordinate Compression + Segment Tree	O(n log n)	O(n)	Use coordinate compression and segment tree for efficient range maximum queries

Brute Force Simulation — Algorithm Steps

For each new square, find its horizontal range [left, right]
Check all existing squares for overlaps
Find maximum height among overlapping squares
Place new square and update maximum height

Visualization

Tap to expand

Step-by-Step Walkthrough

Drop Square

New square falls from above

Check Overlaps

Compare with all existing squares

Find Landing

Land on highest overlapping square

Code -

solution.c — C

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

int* solution(int** positions, int positionsSize, int* positionsColSize, int* returnSize) {
    *returnSize = positionsSize;
    if (positionsSize == 0) return NULL;
    
    int* result = (int*)malloc(positionsSize * sizeof(int));
    int squares[1000][3]; // [left, right, height] - assuming max 1000 squares
    int squareCount = 0;
    int maxHeight = 0;
    
    for (int i = 0; i < positionsSize; i++) {
        int left = positions[i][0];
        int size = positions[i][1];
        int right = left + size;
        
        // Find the maximum height this square will land on
        int landHeight = 0;
        for (int j = 0; j < squareCount; j++) {
            int sqLeft = squares[j][0], sqRight = squares[j][1], sqHeight = squares[j][2];
            // Check if squares overlap horizontally
            if (!(right <= sqLeft || left >= sqRight)) {
                if (sqHeight > landHeight) {
                    landHeight = sqHeight;
                }
            }
        }
        
        // New square's height
        int newHeight = landHeight + size;
        squares[squareCount][0] = left;
        squares[squareCount][1] = right;
        squares[squareCount][2] = newHeight;
        squareCount++;
        
        // Update maximum height
        if (newHeight > maxHeight) {
            maxHeight = newHeight;
        }
        result[i] = maxHeight;
    }
    
    return result;
}

int main() {
    // Simple parsing for basic test cases
    int positions[][2] = {{1, 2}, {2, 3}, {6, 1}};
    int positionsSize = 3;
    int positionsColSize[] = {2, 2, 2};
    int returnSize;
    
    int* result = solution((int**)positions, positionsSize, positionsColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n squares, we check all previously placed squares

⚠ Quadratic Growth

Space Complexity

O(n)

Store positions and heights of all squares

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

450 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

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler