Falling Squares

  • 1

    Click here to see the full article post

  • 0

    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.

  • 0

    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;
        // 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 {
        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);
                ter.replace(l, r, h);
            return ret;

  • 0

    For your approach #2
    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];

  • 0

    resolved. I just understand the compression method you mentioned.

    Never mind :)

  • 0

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

Log in to reply

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