LeetCode 699: Falling Squares Solution in Python – A Step-by-Step Guide

Imagine you’re an architect watching squares fall onto a flat plane, with a list like [[1, 2], [2, 3], [6, 1]] telling you where they land (position) and how big they are (side length), and your task is to track the tallest stack after each drop—like heights [2, 5, 5]. That’s the challenge of LeetCode 699: Falling Squares, a hard-level problem that’s all about simulating a skyline’s growth as squares pile up. Using Python, we’ll explore two solutions: the Best Solution, an interval tracking with binary search approach for efficiency, and an Alternative Solution, a brute-force height tracking method that’s simpler but less optimized. With detailed examples, beginner-friendly breakdowns—especially for the interval method—and clear code, this guide will help you build that skyline, whether you’re new to coding or leveling up. Let’s drop those squares and start stacking!

What Is LeetCode 699: Falling Squares?

In LeetCode 699: Falling Squares, you’re given a list positions where each element [left, side] represents a square with left edge at left and side length side, falling onto a 1D plane. Each square lands on the highest point within its range, and your task is to return a list of the maximum height of the skyline after each square falls. The height at any point is the tallest stack of squares covering that point. For example, with positions = [[1, 2], [2, 3], [6, 1]], the heights after each drop are [2, 5, 5], reflecting the tallest stack at each step. This problem tests your ability to track overlapping intervals and compute maximum heights efficiently.

Problem Statement

  • Input:
    • positions: List of lists, where each [left, side] is a square’s left position and side length.
  • Output: A list of integers—maximum height after each square falls.
  • Rules:
    • Square: Falls from left to left + side - 1, lands on highest point in range.
    • Height: Maximum stack height after each drop.
    • Process squares sequentially.

Constraints

  • 1 ≤ positions.length ≤ 1000.
  • 1 ≤ positions[i][0] ≤ 10⁸ (left position).
  • 1 ≤ positions[i][1] ≤ 10⁶ (side length).

Examples

  • Input: positions = [[1, 2], [2, 3], [6, 1]]
    • Output: [2, 5, 5] (Heights: 2, 5, 5)
  • Input: positions = [[100, 100], [200, 100]]
    • Output: [100, 100] (No overlap, both 100)
  • Input: positions = [[1, 2]]
    • Output: [2] (Single square, height 2)

These examples set the squares—let’s solve it!

Understanding the Problem: Tracking Falling Squares

To solve LeetCode 699: Falling Squares in Python, we need to track the maximum height of a skyline as squares fall, each landing on the tallest existing height within its range, and return the max height after each drop. A brute-force approach—checking all previous squares for overlap—would be O(n²), inefficient for n ≤ 1000 with large ranges. Since we’re managing intervals and heights, an interval tracking approach with binary search or a full sweep can optimize this. We’ll use:

  • Best Solution (Interval Tracking with Binary Search): O(n log n) time, O(n) space—fast and scalable.
  • Alternative Solution (Brute-Force Height Tracking): O(n²) time, O(n) space—simple but slow.

Let’s start with the interval tracking solution, breaking it down for beginners.

Alternative Solution: Brute-Force Height Tracking

Why an Alternative Approach?

The brute-force height tracking approach checks all previous squares—O(n²) time, O(n) space. It’s simpler, maintaining a list of intervals and heights, but inefficient for n ≤ 1000 with large ranges. It’s like checking every past drop for overlap each time!

How It Works

Picture this as a drop checker:

  • Step 1: Track intervals and heights:
    • List of (left, right, height) tuples.
  • Step 2: Process each square:
    • Find max height in range, add new square’s height.
  • Step 3: Update max height:
    • Track global max after each drop.
  • Step 4: Return result.

It’s like a full scanner—check and pile!

Step-by-Step Example

Example: Same as above

  • Step 1: Init: intervals = [], result = [], max_height = 0.
  • Step 2: Process:
    • [1, 2]: Range [1, 2], max = 0, height = 2, intervals = [(1, 2, 2)], max_height = 2, result = [2].
    • [2, 3]: Range [2, 4], max = 2, height = 2 + 3 = 5, intervals = [(1, 2, 2), (2, 4, 5)], max_height = 5, result = [2, 5].
    • [6, 1]: Range [6, 6], max = 0, height = 1, intervals = [(1, 2, 2), (2, 4, 5), (6, 6, 1)], max_height = 5, result = [2, 5, 5].
  • Step 4: Return [2, 5, 5].
  • Output: [2, 5, 5].

Code for Brute-Force Approach

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        # Step 1: Initialize intervals and result
        intervals = []  # (left, right, height)
        result = []
        max_height = 0

        # Step 2: Process each square
        for left, side in positions:
            right = left + side - 1
            curr_height = 0
            for l, r, h in intervals:
                if left <= r and right >= l:  # Overlap
                    curr_height = max(curr_height, h)
            new_height = curr_height + side
            intervals.append((left, right, new_height))

            # Step 3: Update max height
            max_height = max(max_height, new_height)
            result.append(max_height)

        # Step 4: Return result
        return result
  • Lines 4-7: Init: Intervals list, result, max_height.
  • Lines 10-17: Process:
    • Check overlaps, compute new height, add interval.
  • Lines 20-21: Update: Track max_height, append to result.
  • Line 24: Return result.
  • Time Complexity: O(n²)—n squares, n checks each.
  • Space Complexity: O(n)—intervals list.

It’s a stack checker—overlap and pile!

Comparing the Two Solutions

  • Interval Tracking (Best):
    • Pros: O(n log n) time, O(n) space, efficient and scalable.
    • Cons: Binary search logic less obvious.
  • Brute-Force (Alternative):
    • Pros: O(n²) time, O(n) space, straightforward.
    • Cons: Slower, less efficient.

Interval tracking wins for efficiency.

Additional Examples and Edge Cases

  • Input: positions = [[1, 1]]
    • Output: [1].
  • Input: positions = [[1, 2], [1, 2]]
    • Output: [2, 4].

Interval tracking handles these well.

Complexity Breakdown

  • Interval Tracking: Time O(n log n), Space O(n).
  • Brute-Force: Time O(n²), Space O(n).

Interval tracking is optimal.

Key Takeaways

  • Interval Tracking: Search stacking—smart!
  • Brute-Force: Full checking—clear!
  • Skyline: Building is fun.
  • Python Tip: Bisect rocks—see Python Basics.

Final Thoughts: Build That Skyline

LeetCode 699: Falling Squares in Python is a fun skyline challenge. Interval tracking with binary search offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 218: The Skyline Problem or LeetCode 715: Range Module. Ready to stack? Head to Solve LeetCode 699 on LeetCode and drop those squares today!