C++, map with explanation, O(nlogn) solution 36ms


  • 0
    Z

    The idea is to store all non-overlapping intervals in a tree map, and to update the new height while adding new intervals into the map.
    The interval is represented by left bound l, right bound r, and height h. The format in the map is
    '''
    invals[l] = {r, h};
    '''
    The number of intervals in the map is at most 2n. The run time for search, insert and erase is O(nlogn) when adding n intervals. The iteration from iterator low to up seems time consuming, but all those intervals will be deleted after the loop. So the run time for this part in total is O(2n) because there are at most 2n intervals to delete.

    For some reasons possibly related to Leetcode platform, the low and up iterators part is very sensitive to revision. I have another version "equal" to this one, but it results in undefined behavior/random output.

    class Solution {
    public:
        vector<int> fallingSquares(vector<pair<int, int>>& positions) {
            map<int, vector<int>> invals;
            int n = positions.size();
            vector<int> ht(n, 0);
            int l = positions[0].first, h = positions[0].second;
            ht[0] = h;
            invals[l] = {l+h, h};
            for (int i = 1; i < n; i++) {
                int h = drop(invals, positions[i]);
                ht[i] = max(h, ht[i-1]);
            }
            return ht;
        }
    private:
        // return the height of current square
        int drop(map<int, vector<int>>& invals, pair<int, int>& square) {
            int l = square.first, h = square.second, r = l+h, pre_ht = 0;
            auto low = invals.lower_bound(l), up = invals.lower_bound(r);
            // consider intervals in range [low-1, up) 
            if (low != invals.begin()) low--;
            for (auto it = low; it != up; it++) 
                if (it->second[0] > l) pre_ht = max(pre_ht, it->second[1]);
            // erase overlapping intervals, add current interval and update the interval at low and up-1
            int l1 = low->first, r1 = low->second[0], h1 = low->second[1], r2 = 0, h2 = 0;
            if (up != invals.begin()) {
                up--;
                r2 = up->second[0];
                h2 = up->second[1];
                up++;
            }
            invals.erase(low, up);
            invals[l] = {r, pre_ht+h};
            if (l1 < l) invals[l1] = {min(l, r1), h1};
            if (r2 > r) invals[r] = {r2, h2};
            return pre_ht+h;
        }
    };
    

Log in to reply
 

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