Rectangle Area II

Rectangle Area II

What is this problem about?

The Rectangle Area II problem gives you multiple axis-aligned rectangles and asks for the total area covered by at least one rectangle (counting overlaps only once). This hard coding problem uses coordinate compression with a line sweep or segment tree to compute union area efficiently. The array, line sweep, ordered set, and segment tree interview pattern is the core.

Why is this asked in interviews?

Flipkart and Google ask this because union area computation for multiple rectangles is a classic computational geometry challenge. Brute force fails; coordinate compression + event-based sweep is the efficient approach.

Algorithmic pattern used

Line sweep + coordinate compression. Compress y-coordinates. Sort all rectangle events (left edge = +1, right edge = -1) by x-coordinate. Sweep from left to right: maintain a "coverage count" for each y-interval segment. Active coverage gives the height at each x-step; multiply by the width (next_x - current_x) for area contribution.

Example explanation

Rectangles: [(0,0,2,2),(1,0,3,3)]. Sort events by x: x=0(add 0-2), x=1(add 0-3), x=2(remove 0-2), x=3(remove 0-3).

• x=0 to x=1: covered y=[0,2]. Height=2. Width=1. Area+=2.
• x=1 to x=2: covered y=[0,3] (both rects). Height=3. Width=1. Area+=3.
• x=2 to x=3: covered y=[0,3] (rect2 only). Height=3. Width=1. Area+=3. Total = 2+3+3 = 8. Mod 10^9+7.

Common mistakes candidates make

• Not applying modulo 10^9+7 (problem requires it).
• Double-counting overlapping areas.
• Incorrect event ordering (must sort by x, with remove events before add at same x).
• Not compressing y-coordinates before segment tree operations.

Interview preparation tip

Rectangle Area II is a classic line sweep problem. The approach: (1) compress y-coordinates, (2) process x-events (left/right edges) sorted by x, (3) maintain active y-coverage with a segment tree or sorted set. The area contribution at each sweep step = active_y_coverage × delta_x. Practice line sweep on similar "area of union of geometric shapes" problems.