C++ O(n) solution, 20+ lines code with some explaination


  • 0
    W
    class Solution {
    private:
        unordered_map<long, int>pivots;
        bool addPivot(int x, int y, int pos) {
            long key = x << 15 ^ y;
            if (pivots.find(key) != pivots.end() && pivots[key] & pos) {
                return false;
            }
            pivots[key] ^= (pos | 16); // extra bit for even or odd appear times
            return true;
        }
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            for (auto rect: rectangles) {
                if (!addPivot(rect[0], rect[1], 1)) return false;
                if (!addPivot(rect[2], rect[3], 2)) return false;
                if (!addPivot(rect[0], rect[3], 4)) return false;
                if (!addPivot(rect[2], rect[1], 8)) return false;
            }
            int count = 0;
            for (auto it = pivots.begin(); it != pivots.end(); it++) {
                if (it -> second == 3 || it -> second == 12) return false; // check diagonal position
                if ((it -> second & 16) != 0) count++;
            }
            return count == 4;
        }
    };
    

    Initially I have the idea to count vertexes appears odd times and if the number is exact 4, then it is true, otherwise it is false. Then I read the post wrote by @hxtang and get inspired.

    First of all, count all the vertexes same as hxtang's solution, but I use long instead of pair<int, int> because I don't know how to hash the pair at first :P. Also I use an extra bit to record whether the vertex appears even times or odd times.

    Then with the check, I checked if a vertex has even appearance but in a diagonal position, if this is true, then the results must be false. After this check, there is another count for all odd appearance vertexes.

    Finally if the number of odd times vertexes is 4, then the result is true, otherwise it is false.

    I don't know how to prove this, but just got passed the submission. Any counterexample is welcome :) and thanks to hxtang's post.


Log in to reply
 

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