🔷 Coordinate Compression for Falling Squares 🎯 |  Beats 88% - Efficient Height Tracking
IntuitionThe problem requires tracking the maximum height of stacked squares at each step. My initial insight was that we only need to track height changes at t
# Intuition
The problem requires tracking the maximum height of stacked squares at each step. My initial insight was that we only need to track height changes at the specific coordinates where squares begin and end. Since the actual positions can range up to 10^8, we can use coordinate compression to map these positions to a smaller range, making the problem more manageable.

# Approach
The solution uses coordinate compression to efficiently track heights across the board:

1. **Coordinate Compression**:
   - Extract all unique coordinates where squares begin and end
   - Sort these coordinates and map them to sequential indices
   - This transforms the potentially large coordinate space into a compact array

2. **Height Tracking**:
   - Initialize a heights array to track the height at each compressed coordinate
   - For each square:
     - Find the maximum height in the range the square will land on
     - Calculate the new height by adding the square's size to this maximum
     - Update all coordinates within the square's range with this new height
     - Track the maximum height seen so far for the result

3. **Result Generation**:
   - After processing each square, append the maximum height seen so far to the result

This approach elegantly handles the key challenge of efficiently representing a potentially sparse area where squares may land far apart from each other.

# Complexity
- Time complexity: **O(n²)**
  - We process n squares
  - For each square, we potentially need to update O(n) positions in the heights array
  - Finding the maximum height in a range is also O(n) in the worst case

- Space complexity: **O(n)**
  - We store at most 2n coordinates (each square contributes two coordinates)
  - The heights array size is at most 2n
  - The result array stores n heights

# Code
```python3 []
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        coords = set()
        for left, size in positions:
            coords.add(left)
            coords.add(left + size)

        coord_map = {coord: idx for idx, coord in enumerate(sorted(coords))}

        heights = [0] * len(coord_map)
        
        result = []
        max_height_so_far = 0
        
        for left, size in positions:
            left_idx = coord_map[left]
            right_idx = coord_map[left + size]

            current_max_height = max(heights[left_idx:right_idx])

            new_height = current_max_height + size

            for i in range(left_idx, right_idx):
                heights[i] = new_height
            max_height_so_far = max(max_height_so_far, new_height)
            result.append(max_height_so_far)
        
        return result
```

The key insight of this solution is recognizing that we only need to track heights at the specific coordinates where changes happen, rather than modeling the entire range. By compressing the coordinates, we transform a potentially sparse problem into a dense one that's easier to handle.

If you found this solution helpful, please consider upvoting! Happy coding! 💻
['Ordered Set', 'Python3']