## Falling Squares

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> fallingSquares(vector<vector<int>>& positions) {
vector<int> ans;
map<pair<int, int>, int> xsToHeight;  // {{xStart, xEnd}, height}
int maxHeight = INT_MIN;

for (const auto& p : positions) {
const int left = p[0];
const int sideLength = p[1];
const int right = left + sideLength;
// first range intersect with [left, right)
auto it = xsToHeight.upper_bound({left, right});
if (it != begin(xsToHeight) && (--it)->first.second <= left)
++it;
int maxHeightInRange = 0;
vector<tuple<int, int, int>> ranges;
while (it != end(xsToHeight) && it->first.first < right) {
const int l = it->first.first;
const int r = it->first.second;
const int h = it->second;
if (l < left)
ranges.emplace_back(l, left, h);
if (right < r)
ranges.emplace_back(right, r, h);
maxHeightInRange = max(maxHeightInRange, h);
it = xsToHeight.erase(it);
}
const int newHeight = maxHeightInRange + sideLength;
xsToHeight[{left, right}] = newHeight;
for (const auto& [l, r, h] : ranges)
xsToHeight[{l, r}] = h;
maxHeight = max(maxHeight, newHeight);
ans.push_back(maxHeight);
}

return ans;
}
};
``````