Falling Squares


@awice
Here's one more approach  using standard map.
Time: O(N log N) worst case, O(N) best case depending on data.
Space: O(N) worst case, O(1) best case depending on data.
Unfortunately I came up with this approach after contest was over :)class terrain { // operator < for segment which use in std::map results in segments treated // as equal if they intersect struct lt { bool operator()(const pair<int, int>& a, const pair<int, int>& b) const { return a.first <= b.second && a.second <= b.first; } }; // key  pair of coordinates, value  height map<pair<int, int>, unsigned, lt> _data; public: // return max height of terrain between l and r unsigned height(int l, int r) const { unsigned ret = 0; // get range of segments that intersect given segment [l, r] auto range = _data.equal_range({l, r}); for (auto it = range.first; it != range.second; ++it) ret = max(ret, it>second); return ret; } // replace terrain between l and r with height void replace(int l, int r, unsigned height) { // get range of segments that intersect given segment [l, r] auto range = _data.equal_range({l, r}); // remove all segments that intersect [l, r], also take additional care // of first and last one if they extend out of [l, r] for (auto it = range.first; it != range.second;) { auto first = it == range.first, last = next(it) == range.second; auto val = *it; it = _data.erase(it); if (first && val.first.first < l) _data.insert({{val.first.first, l}, val.second}); if (last && val.first.second > r) _data.insert({{r, val.first.second}, val.second}); } // insert [l, r] instead of removed ones _data.insert({{l, r}, height}); } }; class Solution { public: vector<int> fallingSquares(vector<pair<int, int>>& positions) { terrain ter; unsigned maxh = 0; vector<int> ret; for (const auto& p: positions) { int l = p.first, r = l + p.second; unsigned h = ter.height(l, r) + p.second; maxh = max(maxh, h); ret.push_back(maxh); ter.replace(l, r, h); } return ret; } };

For your approach #2
you said:Time Complexity: O(N^2), where N is the length of positions. We use two forloops, each of complexity O(N)(because of coordinate compression.)
Space Complexity: O(N), the space used by heights.
but the array heights[i] should be a infinite array, as mentioned in the issue description.
as you don't know what number the Left and Right will be in the X axisSame question for the array you set in approach #4
tree = new int[2 * N];
lazy = new int[N];