# C++ O(nlogn)

• Similar to skyline concept, going from left to right the path is decomposed to consecutive segments, and each segment has a height. Each time we drop a new square, then update the level map by erasing & creating some new segments with possibly new height. There are at most 2n segments that are created / removed throughout the process, and the time complexity for each add/remove operation is O(log(n)).

``````class Solution {
public:
vector<int> fallingSquares(vector<pair<int, int>>& p) {
map<pair<int,int>, int> mp;
mp[{0,1000000000}] = 0;
vector<int> ans;
int mx = 0;
for (auto &v:p) {
cout << endl;
int len = v.second, a = v.first, b =v.first + v.second, h = 0;
auto it = mp.upper_bound({a,a});
if (it != mp.begin() && (--it)->first.second <= a) ++it;
while (it != mp.end() && it->first.first <b) {
h = max(h, it->second);
it = mp.erase(it);
}
mp[{a,b}] = h + len;
for (auto &t:toAdd) mp[{t[0],t[1]}] = t[2];
mx = max(mx, h + len);
ans.push_back(mx);
}

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

• Why upper_bound for {a,a} ? Instead of using upper_bound and going back 1 position, can we use lower_bound and use the result directly.

• @bhaumik13 Using lower_bound can miss interval. Example if you have (1,3) and you are updating (2,4), using lower_bound you will ignore (1,3) completely.

• @elastico Thanks for the quick response. I understand now.

• best solution so far

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.