# c++, map based short solution

• The running time complexity should be O(n²), since the bottleneck is given by finding the maxHeight in certain range.
Idea is simple, we use a map, and `map[i] = h` means, from `i` to next adjacent x-coordinate, inside this range, the height is `h`.
To handle edge cases like adjacent squares, I applied STL functions, for left bound, we call `upper_bound` while for right bound, we call `lower_bound`.
Special thanks to @storypku for pointing out bad test cases like [[1,2],[2,3],[6,1],[3,3],[6,20]]

``````    vector<int> fallingSquares(vector<pair<int, int>>& positions) {
map<int,int> mp = {{0,0}, {INT_MAX,0}};
vector<int> res;
int cur = 0;
for(auto &p : positions){
int l = p.first, r = p.first + p.second, h = p.second, maxH = 0;
auto ptri = mp.upper_bound(l), ptrj = mp.lower_bound(r);        // find range
int tmp = ptrj->first == r? ptrj->second : (--ptrj)++->second;  // tmp will be applied by new right bound
for(auto i = --ptri; i != ptrj; ++i)
maxH = max(maxH, i->second);                                // find biggest height
mp.erase(++ptri, ptrj);                                         // erase range
mp[l] = h+maxH;                                                 // new left bound
mp[r] = tmp;                                                    // new right bound
cur = max(cur, mp[l]);
res.push_back(cur);
}
return res;
}
``````

• vector<int> fallingSquares(vector<pair<int, int>>& positions) {
map<int,int> mp = {{0,0}, {INT_MAX,0}};
vector<int> res;
int cur = 0;
for(auto &p : positions){
int l = p.first, r = p.first + p.second, h = p.second, maxH = 0;
auto ptri = mp.upper_bound(l), ptrj = mp.lower_bound(r); // find range
int tmp = (--ptrj)++->second; // tmp will be applied by new right bound
for(auto i = --ptri; i != ptrj; ++i)
maxH = max(maxH, i->second); // find biggest height
mp.erase(++ptri, ptrj); // erase range
mp[l] = h+maxH; // new left bound
mp[r] = tmp; // new right bound
cur = max(cur, mp[l]);
res.push_back(cur);
}
return res;
}

• @JadenPan Your solution with bug fixed. Point it out if it still has other bugs.

``````class Solution {
public:
vector<int> fallingSquares(vector<pair<int, int>>& positions) {
std::map<int, int> distro = { { 0, 0 }, { INT_MAX, 0 } };
int n = positions.size();
vector<int> result(n, 0);

int maxH = 0, k = 0;
for (auto& p : positions) {
int start = p.first, end = p.first + p.second;
auto itr1 = distro.upper_bound(start), itr2 = distro.lower_bound(end);

int borderH = itr2->first == end ? itr2->second : (--itr2)++->second;

int localMaxH = 0;
for (auto iter = --itr1; iter != itr2; ++iter) {
localMaxH = std::max(localMaxH, iter->second);
}
localMaxH += p.second;

distro.erase(++itr1, itr2);

distro[start] = localMaxH;
distro[end] = borderH;

maxH = std::max(maxH, localMaxH);
result[k++] = maxH;
}
return result;
}
};
``````

• @storypku Than you so much for pointing that out! I've updated my post.

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