Falling Squares

Problem Statement

The challenge presents a scenario where squares are sequentially dropped onto a 2D plane along the X-axis, each with specified starting positions and side lengths. The 2D array positions provides details for each square dropping operation, where positions[i] = [lefti, sideLengthi] defines the starting left-edge X-coordinate and the side length of the ith square. The simulation of the drop involves the square descending vertically until it lands either on another square (not by merely touching sides, but fully landing on top) or directly on the X-axis.

The task requires calculating the maximum height of the stacks formed by these squares after each square is dropped. The result should be an array ans, where each element ans[i] reflects the new height of the tallest stack after the ith square has been added. This problem combines spatial reasoning with incremental construction and querying of data structures to simulate and solve the sequence of drops effectively.

Examples

Example 1

Input:

positions = [[1,2],[2,3],[6,1]]

Output:

[2,5,5]

Explanation:

After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].

Example 2

Input:

positions = [[100,100],[200,100]]

Output:

[100,100]

Explanation:

After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of [100, 100].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.

Constraints

• 1 <= positions.length <= 1000
• 1 <= lefti <= 108
• 1 <= sideLengthi <= 106

Approach and Intuition

The simulation of this problem requires careful placement and tracking of squares. Here's a step-by-step breakdown of the intuitive approach to solve this problem:

1. Initialize Heights Tracking: Use a data structure, typically a map or dictionary, to maintain the heights at each relevant X-coordinate on the axis. This allows for efficient updates and queries.

2. Simulate Each Drop: For each square given in the positions array:

   • Determine its landing position based on the current stack heights. Calculate the maximum height it will rest upon by checking the range of X-coordinates it would cover based on its left position and side length.
   • Update this maximum height by adding the square's own side length to account for its contribution to the stack height.

3. Update Data Structures: After determining where a square will land and how high it will pile up, update the height tracking data structure for each relevant X-coordinate that the square covers.

4. Record Maximum Height: Post each drop, scan through the height tracking structure to find the maximum stack height and record this in the result array.

5. Result Compilation: After processing each drop, compile the results from each drop into the output array and return it.

This approach ensures an accurate simulation of each drop and proper tracking of resultant heights, adapting dynamically to each new square's landing and the evolving structure of the stack on the plane. This methodology supports the underlying need for correct, efficient height calculations and maximally utilizes the structural properties given in the constraints.

Solutions

class BoxFalls {
    // Process squares after they fall in positions provided
    public List<Integer> calculateFalls(int[][] placements) {
        TreeMap<Integer, Integer> compressed = new TreeMap<>();
        SegmentTree segTree = new SegmentTree(compressed.size());
        int maxHeight = 0;
        List<Integer> results = new ArrayList();

        for (int[] placement : placements) {
            int start = compressed.get(placement[0]);
            int end = compressed.get(placement[0] + placement[1] - 1);
            int height = segTree.rangeQuery(start, end) + placement[1];
            segTree.rangeUpdate(start, end, height);
            maxHeight = Math.max(maxHeight, height);
            results.add(maxHeight);
        }
        return results;
    }
}

class SegmentTree {
    int size, height;
    int[] tree, refresh;

    public SegmentTree(int size) {
        this.size = size;
        height = 1;
        while ((1 << height) < size) {
            height++;
        }
        tree = new int[2 * size];
        refresh = new int[size];
    }

    private void applyUpdate(int x, int value) {
        tree[x] = Math.max(tree[x], value);
        if (x < size) {
            refresh[x] = Math.max(refresh[x], value);
        }
    }

    private void pullUp(int x) {
        while (x > 1) {
            x >>= 1;
            tree[x] = Math.max(tree[2 * x], tree[2 * x + 1]);
            tree[x] = Math.max(tree[x], refresh[x]);
        }
    }

    private void pushDown(int x) {
        for (int h = height; h > 0; h--) {
            int y = x >> h;
            if (refresh[y] > 0) {
                applyUpdate(2 * y, refresh[y]);
                applyUpdate(2 * y + 1, refresh[y]);
                refresh[y] = 0;
            }
        }
    }

    public void rangeUpdate(int left, int right, int value) {
        left += size;
        right += size;
        int start = left, end = right;
        while (left <= right) {
            if ((left & 1) == 1) {
                applyUpdate(left++, value);
            }
            if ((right & 1) == 0) {
                applyUpdate(right--, value);
            }
            left >>= 1;
            right >>= 1;
        }
        pullUp(start);
        pullUp(end);
    }

    public int rangeQuery(int left, int right) {
        left += size;
        right += size;
        int result = 0;
        pushDown(left);
        pushDown(right);
        while (left <= right) {
            if ((left & 1) == 1) {
                result = Math.max(result, tree[left++]);
            }
            if ((right & 1) == 0) {
                result = Math.max(result, tree[right--]);
            }
            left >>= 1;
            right >>= 1;
        }
        return result;
    }
}