O(log n) Problem 2 and O(n) Problem 3 solution


  • 0
    H

    Problem 2
    Idea is to maintain first and last number of each round
    at round t, the gap among consecutive numbers is pow(2, t-1)

    int lastRemaining(int n) {
        int base = 1, first = 1, last = n;
        bool check_first = false;
        while (first < last) { //remaining number is first, first + base, ..., last
            base *= 2;
            check_first = !check_first;
            int r = (check_first?first:last) % base; //first (last) mod base cannot be r
            if (first % base == r) first += base/2;
            if (last % base == r) last -= base/2;
        }
        return first;
    }
    

    Problem 3
    Idea is to count occurrence of all corners of the sub-rectangles
    The four corners of the large rectangles should appear once
    Others may appear 2 or 4 times.

    bool isRectangleCover(vector<vector<int>>& rectangles) {
        unordered_map<int, unordered_map<int, int>> corner_count;
        int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
        for (auto& rect : rectangles) {
            minx = min(minx, rect[0]);
            maxx = max(maxx, rect[2]);
            miny = min(miny, rect[1]);
            maxy = max(maxy, rect[3]);
    
            corner_count[rect[0]][rect[1]]++;
            corner_count[rect[2]][rect[1]]++;
            corner_count[rect[0]][rect[3]]++;
            corner_count[rect[2]][rect[3]]++;
        }
        
        for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
            int x = itx->first;
            for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
                int y = ity->first;
                int count = ity->second;
                if ((x == minx || x == maxx) && (y == miny || y == maxy)) {
                    if ( count != 1 ) return false;
                }
                else {
                    if (count !=2 && count !=4) return false;
                }
            }
        }
        return true;
    }
    

  • 0
    L

    I think your code fails the following case:

    [[1, 1, 2, 2], [2, 1, 3, 2],  [2, 1, 3, 2], [2, 1, 3, 2], [3, 1, 4, 2]]
    

    @hxtang said in O(log n) Problem 2 and O(n) Problem 3 solution:

    bool isRectangleCover(vector<vector<int>>& rectangles) {
    unordered_map<int, unordered_map<int, int>> corner_count;
    int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
    for (auto& rect : rectangles) {
    minx = min(minx, rect[0]);
    maxx = max(maxx, rect[2]);
    miny = min(miny, rect[1]);
    maxy = max(maxy, rect[3]);

        corner_count[rect[0]][rect[1]]++;
        corner_count[rect[2]][rect[1]]++;
        corner_count[rect[0]][rect[3]]++;
        corner_count[rect[2]][rect[3]]++;
    }
    
    for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
        int x = itx->first;
        for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
            int y = ity->first;
            int count = ity->second;
            if ((x == minx || x == maxx) && (y == miny || y == maxy)) {
                if ( count != 1 ) return false;
            }
            else {
                if (count !=2 && count !=4) return false;
            }
        }
    }
    return true;
    

    }


  • 1
    H

    @lzb700m I see. The code does not check for rectangles sharing top-left / top-right / bottom-left /bottom-right corners.
    A naive solution would just be adding additional masks to each entry of the unordered_map to check whether the corner has been added as TL/TR/BL/BR...

    The method is still O(n) as the mask is checked in O(1) time for each corner.

    // pos encoding: 1 - TL 2- TR 4- BL 8-BR
    // return false if a conflict in mask occurs (i.e. there used to be a rectangle with corner (x, y) at pos
    inline bool insert_corner(unordered_map<int, unordered_map<int, int>>& corner_count, int x, int y, int pos) {
        int& m = corner_count[x][y];
        if (m & pos) return false;
        m |= pos;
        return true;
    }
    
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        // step 1: counting
        unordered_map<int, unordered_map<int, int>> corner_count;
        int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
        for (auto& rect : rectangles) {
            minx = min(minx, rect[0]);
            maxx = max(maxx, rect[2]);
            miny = min(miny, rect[1]);
            maxy = max(maxy, rect[3]);
            if (!insert_corner(corner_count, rect[0], rect[1], 1)) return false;
            if (!insert_corner(corner_count, rect[2], rect[1], 2)) return false;
            if (!insert_corner(corner_count, rect[0], rect[3], 4)) return false;
            if (!insert_corner(corner_count, rect[2], rect[3], 8)) return false;
        }
        
        //step2: checking
        bool valid_corner[16] = {false};
        bool valid_interior[16] = {false};
    
        valid_corner[1] = valid_corner[2] = valid_corner[4] = valid_corner[8] = true;
        valid_interior[3] = valid_interior[5] = valid_interior[10] = valid_interior[12] = valid_interior[15] = true;
        
        for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
            int x = itx->first;
            for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
                int y = ity->first;
                int mask = ity->second;
                if ((x == minx || x == maxx) && (y == miny || y == maxy)) {
                    if ( !valid_corner[mask] ) return false;
                }
                else {
                    if ( !valid_interior[mask]) {
                        cout << mask << endl;
                        return false;
                    }
                }
            }
        }
        return true;
    }
    

  • 0

    @lzb700m said in O(log n) Problem 2 and O(n) Problem 3 solution:

    I think your code fails the following case:
    [[1, 1, 2, 2], [2, 1, 3, 2], [2, 1, 3, 2], [2, 1, 3, 2], [3, 1, 4, 2]]

    Thanks, just added this test case.


Log in to reply
 

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