We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Falling Squares

Number: 699

Difficulty: Hard

Paid? No

Companies: Uber, Block

Problem Description

Given an array positions where each element is [left, sideLength], a square with side length sideLength is dropped with its left edge at x = left. The square falls vertically until it either lands on the X-axis or on top of previously dropped squares (only counting a landing if there is a horizontal overlap, not just a touch). After each drop, return the height of the current highest stack of squares.

Key Insights

  • Each square’s final height is determined by checking for overlap with all previously placed squares.
  • Two squares overlap if the interval [left, left + sideLength) of the current square and [prevLeft, prevLeft + prevSideLength) of a previous square intersect.
  • The height at which a new square lands is equal to its side length plus the maximum height of any square that overlaps its horizontal interval.
  • While a brute-force O(n^2) solution is feasible for up to 1000 positions, more efficient approaches can be implemented using segment trees or ordered sets when scaling to larger inputs.
  • Coordinate compression might be used along with advanced data structures if deciding for performance optimizations.

Space and Time Complexity

Time Complexity: O(n^2) in the brute-force approach since for each square we scan all previously dropped squares
Space Complexity: O(n) for storing the square information and the answer array

Solution

The idea is to iterate over each square in the order provided. For the current square, determine its horizontal range using its left coordinate and side length. Check all previous squares to see if their horizontal range overlaps with the current square. If there is an overlap, the current square will land on top of that square, and its height becomes the height of that square plus its own side length. The final height for the current drop is the maximum height determined by all overlapping squares, or simply its side length if there is no overlap. Update the answer list with the maximum height seen so far.
This approach uses an array (or list) to store the details (left coordinate, right coordinate, and height) of each dropped square. The brute force check of overlapping intervals is intuitive and sufficient given the problem constraints.

Code Solutions

# Python implementation for Falling Squares
def fallingSquares(positions):
    # List to record the results after each drop
    ans = []
    # List to keep each square's (left, right, height)
    squares = []
    # The current global maximum height so far
    current_max = 0

    # Iterate through each position in the input list
    for left, side in positions:
        new_left, new_right = left, left + side  # calculate boundaries for the new square
        base_height = 0  # start with height 0 for the landing base

        # Check all previous squares for overlapping intervals
        for prev_left, prev_right, prev_height in squares:
            # If the horizontal intervals overlap (not just touching)
            if not (new_right <= prev_left or new_left >= prev_right):
                # Update base_height to the maximum height this new square can land on
                base_height = max(base_height, prev_height)
        # The height of the current square is the base height plus its side length
        cur_square_height = base_height + side
        # Add the current square info to the squares list
        squares.append((new_left, new_right, cur_square_height))
        # Update the overall maximum height
        current_max = max(current_max, cur_square_height)
        # Append the current maximum height to the results list
        ans.append(current_max)

    # Return the results after dropping each square
    return ans

# Example usage:
#print(fallingSquares([[1,2],[2,3],[6,1]]))  # Expected output: [2, 5, 5]
← Back to All Questions