O(sqrt(N)) extra Space, O(NlogN) Time solution.


  • 0
    F

    It is average case O(sqrt(n)) space solution (worst case still O(n))
    I will add more explanation when I got time.

    struct Pos {int x, y;};
    struct CompareIter{
        bool operator()(list<Pos>::iterator ia, list<Pos>::iterator ib){
            return make_pair(ia->y, ia->x) > make_pair(ib->y, ib->x);// i.e. ia->y < ib->y || (ia->y == ib->y && ia->x < ib->x);
        }
    };
    class Histogram
    {
        list<Pos> outline;
        bool is_first_layer_done = false;
        priority_queue<list<Pos>::iterator, vector<list<Pos>::iterator>, CompareIter> lcorner_heap;
    public:
        //assume no invalid rectangles
        bool add(const vector<int> & rect)
        {
            Pos topleft {rect[0], rect[3]}, bottomright {rect[2], rect[1]};
            if (outline.empty()) //First time, set up the "base block".
            {
                outline.push_back(topleft);
                outline.push_back(bottomright);
                lcorner_heap.push(outline.begin());
                lcorner_heap.push(++outline.begin());
                return true;
            }
            //assert lcorner_heap.size() > 0
            auto lcorner_iter = lcorner_heap.top();
            lcorner_heap.pop();
            if (lcorner_iter->x != topleft.x || lcorner_iter->y != bottomright.y)
            {
                if (!is_first_layer_done)
                {
                    is_first_layer_done = true;
                    return add(rect); //retry adding this one to higher layer.
                }
                return false;
            }
            //assert: nextpos_iter will never be outline.end() after first layer is done.
            auto nextpos_iter = next(lcorner_iter);
            if (nextpos_iter == outline.end() || nextpos_iter->x > bottomright.x)
                lcorner_heap.push(outline.insert(nextpos_iter, bottomright));
            else if (nextpos_iter->x < bottomright.x)
                return false;
            else if (nextpos_iter->y < topleft.y && nextpos_iter->y > bottomright.y)
                lcorner_heap.push(nextpos_iter);
            else if (nextpos_iter->y == topleft.y)
                outline.erase(nextpos_iter);
            *lcorner_iter = topleft;
            if (lcorner_iter == outline.begin() || prev(lcorner_iter)->y > topleft.y)
                lcorner_heap.push(lcorner_iter);
            else if (prev(lcorner_iter)->y == topleft.y)
                outline.erase(lcorner_iter);
            return true;
        }
        bool isRectangle()
        {
            return outline.size() == 2;
        }
    };
    
    class Solution {
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            sort(rectangles.begin(), rectangles.end(), [] (vector<int> va, vector<int> vb){
                return make_pair(va[1], va[0]) < make_pair(vb[1], vb[0]);});
            Histogram hist;
            for (auto & rect : rectangles)
                if (!hist.add(rect))
                    return false;
            return hist.isRectangle();
        }
    };
    

Log in to reply
 

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