Optimized Approach with Binary Search
Intuition\nwe can use a greedy approach. Each square\'s height will depend on the heights of the squares already placed on the line. We maintain a list of the c
# Intuition\nwe can use a greedy approach. Each square\'s height will depend on the heights of the squares already placed on the line. We maintain a list of the current heights and use binary search to efficiently find where each new square starts and ends relative to the squares already placed.\n\n# Approach\nWe maintain two lists: one for positions and another for heights. For each new square, we:\n1. Use binary search to find the range of existing squares it overlaps with.\n2. Calculate the new height based on the maximum height in that range.\n3. Insert the new position and height into our lists.\n4. Track and update the maximum height seen so far.\n\n# Complexity\n- Time complexity: $$O(n^2)$$ due to potentially checking all previous squares for each new square.\n- Space complexity: $$O(n)$$ for storing the positions and heights of the squares.\n\n\n# Code\n```python3 []\nclass Solution:\n    def fallingSquares(self, positions):\n        pos, height, res, max_h = [0], [0], [], 0\n        for l, s in positions:\n            i, j = bisect_right(pos, l), bisect_left(pos, l + s)\n            h = max(height[i-1:j] or [0]) + s\n            pos[i:j], height[i:j] = [l, l + s], [h, height[j-1]]\n            res.append(max_h := max(max_h, h))\n        return res\n\n```
['Python3']