# Falling Squares

• I think your coordinate compression would be nicer if you used `left + size` instead of `left + size - 1`. Currently it looks like you're subtracting and adding 1 for no reason.

• @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;
}
};
``````

you said:

Time Complexity: O(N^2), where N is the length of positions. We use two for-loops, 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 axis

Same question for the array you set in approach #4
tree = new int[2 * N];
lazy = new int[N];

• resolved. I just understand the compression method you mentioned.

Never mind :)

• Can someone please explain the test case:
Input : {9,7},{1,9},{3,1}
Output expected: [7,16,17]

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