Introduction

In this blog post, we will explore how to solve the LeetCode problem "850" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner. Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once. Return the total area. Since the answer may be too large, return it modulo 109 + 7. Example 1: Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] Output: 6 Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture. From (1,1) to (2,2), the green and red rectangles overlap. From (1,0) to (2,3), all three rectangles overlap. Example 2: Input: rectangles = [[0,0,1000000000,1000000000]] Output: 49 Explanation: The answer is 1018 modulo (109 + 7), which is 49. Constraints: 1 <= rectangles.length <= 200 rectanges[i].length == 4 0 <= xi1, yi1, xi2, yi2 <= 109 xi1 <= xi2 yi1 <= yi2 All rectangles have non zero area.

Explanation

Here's a breakdown of the solution:

• Sweep Line Algorithm: Process the rectangles by sweeping a vertical line from left to right. Maintain an active set of rectangles that intersect the sweep line.
• Active Set Management: Use a segment tree to efficiently track the union of the y-intervals of the active rectangles. The segment tree stores the total length of the covered y-intervals.

• Area Calculation: As the sweep line moves, calculate the area added between consecutive x-coordinates by multiplying the change in x by the total covered y-length from the segment tree.

• Runtime Complexity: O(n log n), where n is the number of rectangles. Storage Complexity: O(n).

Code

    class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total_length = 0
        self.count = 0
        self.left = None
        self.right = None

class SegmentTree:
    def __init__(self, y_coords):
        self.y_coords = sorted(list(set(y_coords)))
        self.root = self.build_tree(0, len(self.y_coords) - 1)

    def build_tree(self, start, end):
        node = SegmentTreeNode(self.y_coords[start], self.y_coords[end])
        if start != end:
            mid = (start + end) // 2
            node.left = self.build_tree(start, mid)
            node.right = self.build_tree(mid + 1, end)
        return node

    def update(self, node, y1, y2, val):
        if node.start == y1 and node.end == y2:
            node.count += val
            self.update_length(node)
            return

        if node.left is None or node.right is None:
            return # Should not happen, but handle it gracefully

        mid = node.left.end
        if y2 <= mid:
            self.update(node.left, y1, y2, val)
        elif y1 > mid:
            self.update(node.right, y1, y2, val)
        else:
            self.update(node.left, y1, mid, val)
            self.update(node.right, mid, y2, val)

        self.update_length(node)

    def update_length(self, node):
        if node.count > 0:
            node.total_length = node.end - node.start
        else:
            if node.left is None or node.right is None:
              node.total_length = 0
              return
            node.total_length = node.left.total_length + node.right.total_length

class Solution:
    def rectangleArea(self, rectangles):
        events = []
        y_coords = []
        for x1, y1, x2, y2 in rectangles:
            events.append((x1, y1, y2, 1))  # Start of rectangle
            events.append((x2, y1, y2, -1)) # End of rectangle
            y_coords.append(y1)
            y_coords.append(y2)

        events.sort()

        segment_tree = SegmentTree(y_coords)
        total_area = 0
        prev_x = events[0][0]
        MOD = 10**9 + 7

        for x, y1, y2, type in events:
            total_area = (total_area + (x - prev_x) * segment_tree.root.total_length) % MOD
            segment_tree.update(segment_tree.root, y1, y2, type)
            prev_x = x

        return total_area