497: Space 95.52%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Initialize the Solution class with a list of non-overlapping axis-alig
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Initialize the Solution class with a list of non-overlapping axis-aligned rectangles rects.\n\n2. Inside the init function, calculate the total area covered by all the rectangles and store it in a variable called total_area.\n\n3. Create a list called areas to store the area of each rectangle cumulatively, starting from the first rectangle to the last.\n\n4. Loop through each rectangle in the input list rects and calculate the area of the rectangle using the formula: (xi - ai + 1) * (yi - bi + 1), where xi, yi are the top-right corner points of the ith rectangle and ai, bi are the bottom-left corner points of the ith rectangle.\n\n5. Add the area of each rectangle to the previous cumulative area, starting from the first rectangle, and append the result to the list areas.\n\n6. Inside the pick function, generate a random integer r between 1 and the total area covered by all the rectangles.\n\n7. Loop through each rectangle in the input list rects and compare the value of r with the cumulative area stored in the list areas for that rectangle. If r is less than or equal to the cumulative area, then the random point should be generated inside that rectangle.\n\n8. Generate two random integers x and y using the randint function from the random module, such that ai <= x <= xi and bi <= y <= yi, where ai, bi, xi, yi are the corner points of the current rectangle.\n\n9. Return the random point [x, y] as the output of the pick function.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def __init__(self, rects: List[List[int]]):\n        self.rects = rects\n        self.areas = []\n        self.total_area = 0\n        \n        # Calculate the total area covered by all the rectangles\n        for rect in rects:\n            area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)\n            self.total_area += area\n            self.areas.append(self.total_area)\n        \n    def pick(self) -> List[int]:\n        # Generate a random integer between 0 and the total area covered by all the rectangles\n        r = random.randint(1, self.total_area)\n        \n        # Loop through each rectangle, subtracting its area from r\n        for i in range(len(self.rects)):\n            if r <= self.areas[i]:\n                # Once we find the rectangle, generate a random point inside it\n                rect = self.rects[i]\n                x = random.randint(rect[0], rect[2])\n                y = random.randint(rect[1], rect[3])\n                return [x, y]\n\n```
['Array', 'Math', 'Binary Search', 'Python', 'Python3']