c++, map based short solution


  • 3
    J

    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;
        }
    

  • 0
    S

    @JadenPan said in c++, map based short solution:

    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;
    }

    Bad case: [[1,2],[2,3],[6,1],[3,3],[6,20]]


  • 1
    S

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

  • 0
    J

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


Log in to reply
 

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