Falling Squares - Leetcode Solution

The Falling Squares problem on LeetCode is about finding the maximum height of the stack of squares that will be created when a set of squares falls on a horizontal axis. The problem involves calculating the height of the stack each time a square falls and then finding the maximum height of the stack.

Here is a detailed solution for the Falling Squares problem on LeetCode:

Approach: The basic idea is to maintain a list of intervals. Each interval represents the height of squares in a particular range.

The solution maintains a hashmap "heights", which stores the heights of each square and the range of squares to which the height corresponds. For each square, the solution calculates the range of squares over which the square will fall and finds the maximum height in that range.

The solution then updates the ranges and heights of the squares in this range. The maximum height in this range is also updated if the height of the current square is greater than the height of the previous maximum.

Algorithm:

1. Initialize an empty list intervals to represent the current stack of squares.
2. Initialize an empty hashmap heights to store the heights of squares in each range.
3. Initialize a variable max_height to store the maximum height of the stack.
4. For each square, find the range of squares over which the square falls using the formula range = [left, right].
5. For each square, find the maximum height of squares in the range [left, right] and update max_height if necessary.
6. For each square, update the heights of squares in the range [left, right] to the maximum height of the square and add the range to intervals if it is not already in intervals.
7. Append the current height of the stack, max_height, to a result list.
8. Return the result list.

Here's the code:

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        intervals = [] # to store the intervals of the current stack
        heights = {} # to store the heights of squares in each range
        max_height = 0 # to store the maximum height of the stack
        res = [] # to store the results
        
        for left, size in positions:
            right = left + size - 1
            # calculate the range of squares over which the square will fall
            range = [left, right]
            # find the maximum height of squares in the range [left, right] 
            height = max(heights.get(l, 0) for l,r in intervals if r>=left and l<=right) + size
            # update max_height
            max_height = max(max_height, height)
            # update the heights of squares in the range [left, right]
            for l,r in list(intervals):
                if r<left or l>right: #not overlapping
                    continue
                h = heights.pop(l)
                intervals.remove([l,r])
                if l<left:
                    intervals.append([l, left-1])
                    heights[l] = h
                if r>right:
                    intervals.append([right+1,r])
                    heights[right+1] = h
            intervals.append(range)
            heights[left] = height
            res.append(max_height)
        return res

Time Complexity: The time complexity of this solution is O(n^2), where n is the number of squares. The reason for this is that we are iterating over a list of intervals for each square. However, it can be improved to O(n log n) using segment trees or lazy propagation.

Space Complexity: The space complexity of this solution is O(n), where n is the number of squares. The reason for this is that we are storing a list of intervals and a hashmap of heights for each square.

1