LeetCode 699: Falling Squares Solution

Master LeetCode problem 699 (Falling Squares), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

699. Falling Squares

Hard

Array Segment Tree Ordered Set

Problem Explanation

Explanation

To solve this problem, we can simulate the dropping of squares one by one and keep track of the heights of the tallest stack after each drop. We can represent the positions and heights of the squares using an interval tree data structure.

Initialize an empty list to store the heights of the tallest stack after each drop.
Iterate through each square in the input array.
For each square, update the interval tree with the current square's interval and height.
Update the height of the tallest stack after dropping the current square.
Append the updated height to the result list.
Return the result list.

Time Complexity:
The time complexity of updating the interval tree for each square is O(n log n), where n is the number of squares. Thus, the overall time complexity is O(n^2 log n) due to the n squares and the log n factor for updating the interval tree.

Space Complexity:
The space complexity is O(n) to store the result list and the interval tree.

Solution Code

class Solution {
    class Interval {
        int start;
        int end;
        int height;
        
        public Interval(int start, int end, int height) {
            this.start = start;
            this.end = end;
            this.height = height;
        }
    }
    
    public List<Integer> fallingSquares(int[][] positions) {
        List<Interval> intervals = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        int maxHeight = 0;
        
        for (int[] pos : positions) {
            int left = pos[0];
            int sideLength = pos[1];
            int right = left + sideLength;
            int height = 0;
            
            for (Interval interval : intervals) {
                if (left < interval.end && right > interval.start) {
                    height = Math.max(height, interval.height);
                }
            }
            
            height += sideLength;
            
            for (Interval interval : new ArrayList<>(intervals)) {
                if (left < interval.end && right > interval.start) {
                    if (interval.height < height) {
                        intervals.add(new Interval(left, right, height));
                    }
                }
            }
            
            maxHeight = Math.max(maxHeight, height);
            result.add(maxHeight);
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 699 (Falling Squares)?

This page provides optimized solutions for LeetCode problem 699 (Falling Squares) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 699 (Falling Squares)?

The time complexity for LeetCode 699 (Falling Squares) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 699 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 699 in Java, C++, or Python.

Back to LeetCode Solutions