Rectangle Area II

HardIntervalssweep line

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of axis-aligned rectangles. Each entry rectangles[i] = [x1, y1, x2, y2] gives the bottom-left corner (x1, y1) and the top-right corner (x2, y2) of one rectangle. Compute the total area of the plane covered by **at least one** rectangle. Regions where rectangles overlap are counted only once. Coordinates can be as large as 10^9, so the area can overflow; return it modulo 1_000_000_007.

Examples

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
The union consists of the 2x2 square, the 1x1 strip above it at x in [1,2], and the 1x1 cell at x in [2,3], y in [0,1]: 4 + 1 + 1 = 6.
Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
The area is 10^18, and 10^18 mod 1_000_000_007 = 49.

Constraints

  • 1 <= rectangles.length <= 200
  • rectangles[i].length == 4
  • 0 <= x1 < x2 <= 10^9
  • 0 <= y1 < y2 <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.