O(n) time and space - readable interview solution
Intuition\nThis problem is essentially a counting problem. With our given w (width)\n constraint, we must start our first rectangle at the left most x coordinat
# Intuition\nThis problem is essentially a counting problem. With our given w (width)\n constraint, we must start our first rectangle at the left most x coordinate. From that point, our rectangle will capture all other points that have their x coordinate fall under leftMost+w. From there we can add a rectangle used to our result, and move our left most point to the right w spaces - looking for more coordinates to capture with our next rectangle.\n# Approach\nWe only care about x-cords here, there is no constraint for the y coordinates. We will create a set to store all x values, and also get the range of our x values (left boundary and right boundary).\n\nWith our set created, we need only to traverse from our left boundary to our right boundary, scanning for zones where there exists x values. If there exists an x-cord in this current zone, increase our result (count of rectangles needed), and move our traversal value up w spaces for our next potential rectangle.\n\n# Complexity\n- Time complexity:\nBest(O(n),O(RightBoundary-LeftBoundary) - We are traversing our points to build our set at linear n time. The we are going through our boundaries, if the boundary size is greater than our input size, that will be the final time complexity - still in some linear time.\n\n- Space complexity:\nO(n) - using a set.\n\n# Code\n```\nclass Solution {\npublic:\n    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {\n\n        std::set<int> pointSet;\n        int res = 0;\n        int leftBoundary = INT_MAX;\n        int rightBoundary = INT_MIN;\n\n        //(space - o(n)) and time o(n)\n        for(auto &cord: points){\n            int x = cord[0];\n            pointSet.insert(x);\n            leftBoundary  = std::min(leftBoundary,x);\n            rightBoundary = std::max(rightBoundary,x);\n        }\n\n        for(int i = leftBoundary; i <= rightBoundary; ++i){\n            //There is a coordinate that requires a rectangle.\n            if(pointSet.count(i)){\n                ++res;\n                //Move traversal pointer to next possile rectangle spot.\n                i += w;\n            }\n        }\n        return res;\n        \n    }\n};\n```
['C++']