Falling Squares

The problem involves simulating the dropping of squares onto a 2D plane. The height of the tallest stack of squares needs to be recorded after each drop.

Algorithm

Initialize Heights: Start with a list to store the heights of each position on the X-axis.
Iterate Through Squares: Iterate through each square in positions, simulating the dropping process: a. Find the Landing Height: Calculate the height at which the current square will land by checking the heights of the squares that it overlaps. b. Update Heights: Update the heights for the X-axis positions covered by the current square. c. Record the Tallest Height: After each drop, append the tallest height to the result.
Return the Result: Return the list of heights after all squares have been dropped.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        heights = [] # List to store height intervals
        ans = [] # Result
        max_height = 0 # Maximum height at any moment

        for left, side_length in positions:
            right = left + side_length # Right edge of the current square
            base_height = 0 # Initial height where the square will land

            # Iterate through existing heights to find landing height
            for l, r, h in heights:
                if l < right and r > left:
                    base_height = max(base_height, h)

            height = base_height + side_length # Final height of the current square
            heights.append((left, right, height)) # Update heights list
            max_height = max(max_height, height) # Update maximum height
            ans.append(max_height) # Record the result
            
        return ans

Explanation

Iterate through the positions, calculating the height where each square will land by examining the existing heights of the squares that it overlaps.
Update the heights and record the maximum height after each drop.

Insights

Time Complexity: (O(n^2)), where (n) is the length of positions. We iterate through positions and, for each square, check all existing heights.
Space Complexity: (O(n)), as we store the heights of each square.

This algorithm provides a straightforward simulation of the process, correctly handling the landing of each square and tracking the tallest stack’s height after each drop.

Identifying Problem Isomorphism

“Falling Squares” can be mapped to “The Skyline Problem”.

“Falling Squares” and “The Skyline Problem” share similarities in the sense that both involve calculations based on the skyline or profile generated by placing blocks or buildings in a 2D plane.

In “Falling Squares”, you have a sequence of squares falling from the top of the 2D plane and stacking on top of each other, and you’re required to return the height of the highest stack of squares after each square is dropped.

In “The Skyline Problem”, you’re given the locations and heights of buildings in a city and required to determine the skyline formed by these buildings, represented as a list of the x-coordinates of the key points in the skyline ordered by their x-coordinate.

The mapping here is that the squares in the “Falling Squares” problem can be viewed as the buildings in “The Skyline Problem”, and the height of the highest stack of squares maps to the highest key point in the skyline.

This is an approximate mapping, as the specifics of how the squares stack in the “Falling Squares” problem may not map exactly to how buildings form a skyline in “The Skyline Problem”.

Both problems involve sorting and scanning through the inputs, and maintaining the current highest point. “Falling Squares” is more complex due to the added complexity of the squares falling and stacking on top of each other.

“Falling Squares” (LeetCode 699) is a more advanced problem that involves interval scheduling, priority queue, and sorting. This problem can be one of the first problems you try when you have some experience with interval scheduling, segment trees, and priority queue. However, you should have solved a variety of simpler problems that deal with similar concepts before you tackle this one.

10 Prerequisite LeetCode Problems

Here are some problems that you should consider solving before:

Meeting Rooms II (LeetCode 253): Understanding the basic interval scheduling problem.
Insert Interval (LeetCode 57): Getting used to manipulating intervals.
Range Sum Query - Mutable (LeetCode 307): Basic understanding of segment trees.
Merge Intervals (LeetCode 56): More practice with interval scheduling.
Top K Frequent Elements (LeetCode 347): Understanding the usage of priority queue.
Find Right Interval (LeetCode 436): Deeper understanding of interval scheduling.
My Calendar I (LeetCode 729): Similar to the falling squares problem but simpler.
Find K Pairs with Smallest Sums (LeetCode 373): Getting used to working with priority queue.
Range Sum Query 2D - Mutable (LeetCode 308): Two-dimensional segment tree problem.
Kth Smallest Element in a Sorted Matrix (LeetCode 378): More practice with priority queue.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        max_h_of_p = [0]*len(positions)

        for i,(left,size) in enumerate(positions):
            right = left+size-1
            max_h_of_p[i] += size
            for offset,(left2,size2) in enumerate(positions[i+1:]):
                j = offset+i+1
                right2 = left2+size2-1
                if left2 <= right and left <= right2: # intersect
                    max_h_of_p[j] = max(max_h_of_p[j], max_h_of_p[i])

        res = [] 
        for h in max_h_of_p:
            res.append(max(res[-1],h)) if res else res.append(h)
        return res

Problem Classification

The problem involves concepts of 2D Geometry, Simulation, Arrays, and Optimization.

Here are the ‘What’ aspects:

A 2D integer array positions is given, where each element represents a square that is being dropped onto the X-axis of a 2D plane. Each square is represented by a 2-element array, where the first element is the X-coordinate of the square’s left edge and the second element is the side length of the square.
The squares are dropped one at a time from a height above any landed squares. A square falls downward until it lands on the top side of another square or on the X-axis. Once a square lands, it freezes in place and cannot be moved.
The task is to simulate this process and after each square is dropped, record the height of the tallest stack of squares.
The goal is to return an array where the ith element represents the height of the tallest stack of squares after the ith square is dropped.

We can further classify this problem as a Simulation Problem because it involves simulating a physical process of dropping squares and stacking them. It’s also an Optimization Problem because after each drop, we are interested in the tallest stack of squares, which is a form of optimization. The problem also involves Array Manipulation as the input is provided as a 2D array and the output is also expected to be an array. Lastly, it is a 2D Geometry Problem because it involves geometrical calculations in a 2D plane, specifically, the heights and positions of squares.

Language Agnostic Coding Drills

Dissecting the code and identifying distinct concepts:

Here are the distinct concepts involved:

a. Lists and list comprehension b. Enumeration and Iteration c. Conditions in if statements d. Variables and assignments e. Mathematical operations, particularly addition and subtraction f. Function definitions and returns g. Maximum function usage

Listing the concepts in increasing order of difficulty and providing a brief description:

a. Variables and assignments - Basic element of any programming language, where a value is assigned to a variable. Difficulty level: 1

b. Mathematical operations, particularly addition and subtraction - Fundamental arithmetic operations. Difficulty level: 1

c. Lists and list comprehension - Lists are a built-in data type in Python. List comprehension is a way of generating a new list where each element is the result of some operations applied to each member of another sequence or iterable. Difficulty level: 2

d. Conditions in if statements - If statements are used to test for particular conditions and respond appropriately. Difficulty level: 2

e. Enumeration and Iteration - Enumeration is a built-in function of Python used for iterating over an iterable. Iteration involves looping over elements. Difficulty level: 2

f. Function definitions and returns - Functions are defined to provide a certain functionality which can be reused. They accept inputs and return outputs. Difficulty level: 3

g. Maximum function usage - The max function is used to find the maximum value in an iterable or between two or more parameters. Difficulty level: 3

Problem-solving approach:

a. Define a function fallingSquares that takes a 2D list as input. Initialize a list max_h_of_p with the same length as the input list, filled with zeros.

b. Iterate over the positions list with index i and unpack the values to (left, size). Calculate the right boundary of the current square.

c. For each square, add its size to the corresponding position in max_h_of_p.

d. For every other square that comes after the current one, if they intersect (meaning their left and right boundaries overlap), update the maximum height at the position of the subsequent square with the maximum height of the current square.

e. After calculating the maximum heights for all positions, iterate over the max_h_of_p list. If the result list is not empty, append the maximum of the last element of the result list and the current height. Otherwise, just append the current height.

f. Finally, return the result list which stores the maximum height after dropping each square.

Each drill from creating and manipulating lists, using enumeration and iteration, to applying conditions and using the max function, all contribute to building up the final solution.

Targeted Drills in Python

Coding Drills for each concept:

a. Variables and assignments:

1
2
3
a = 10
b = 5
print(a, b)

b. Mathematical operations, particularly addition and subtraction:

1
2
3
4
a = 10
b = 5
print(a + b)
print(a - b)

c. Lists and list comprehension:

1
2
3
lst = [1, 2, 3, 4, 5]
lst_squared = [i**2 for i in lst]
print(lst_squared)

d. Conditions in if statements:

1
2
3
4
a = 10
b = 5
if a > b:
    print("a is greater than b")

e. Enumeration and Iteration:

1
2
3
lst = ['a', 'b', 'c']
for i, item in enumerate(lst):
    print(f"Index: {i}, Item: {item}")

f. Function definitions and returns:

1
2
3
def add(a, b):
    return a + b
print(add(5, 10))

g. Maximum function usage:

1
2
lst = [1, 5, 2, 4, 3]
print(max(lst))

Problem-specific concepts:

a. Checking overlap of ranges:

1
2
3
4
5
6
7
range1 = (1, 5)
range2 = (4, 6)

if max(range1[0], range2[0]) <= min(range1[1], range2[1]):
    print("Ranges overlap")
else:
    print("Ranges do not overlap")

This drill is essential to our problem as we need to determine if the “squares” or ranges overlap when they are dropped, which is a key part of the solution logic.

Integration of the drills:

The concept drills mentioned above form the building blocks of the problem solution.

a. The problem solution starts by defining a function, using the function definition drill.

b. Inside the function, we initialize some variables and lists to store our results and intermediate calculations. This uses the variable assignment and list comprehension drills.

c. We then enumerate over the input list, using enumeration and iteration concepts.

d. During the enumeration, we check for overlap between different squares. This is done using the range overlap drill.

e. Based on the overlap, we update the maximum height list using the max function drill.

f. Finally, we iterate over the maximum height list to calculate the result after each drop. This again uses the enumeration and iteration, max function, and if statement drills.

By combining these drills in the appropriate order, we can construct the final solution for our problem.