Area Under Two Tarps
MediumMath & Geometry
Problem
Two rectangular tarps are laid on a flat field, sides parallel to the axes. Each is given as [x1, y1, x2, y2]: its bottom-left corner (x1, y1) and top-right corner (x2, y2), with x1 < x2 and y1 < y2.
Return the total ground area covered by at least one tarp. Ground covered by both counts once.
Example 1
- Input:
- first = [0, 0, 4, 3], second = [2, 1, 6, 5]
- Output:
- 24
12 + 16 minus the shared 2 × 2 square = 24.
Example 2
- Input:
- first = [0, 0, 2, 2], second = [2, 0, 4, 2]
- Output:
- 8
They only touch along a line, which has no area.
Example 3
- Input:
- first = [0, 0, 10, 10], second = [2, 2, 4, 4]
- Output:
- 100
The second tarp lies entirely on the first.
Constraints
- first.length = second.length = 4
- -10^7 ≤ coordinates ≤ 10^7
- x1 < x2 and y1 < y2 for both tarps
Hint
Show the first hint
Covered area = area(first) + area(second) - area(overlap).
Walkthrough
How to approach it
01Clarify before coding
- Are edges parallel to the axes? Yes, so no rotation is involved.
- Do touching edges count as overlap? They share a line of zero area, which changes nothing.
- How large can the area get? Up to 4 · 10^14 per tarp, still a safe integer in JavaScript.
02Brute force
Mark every unit cell covered by either tarp in a grid and count the marks.
Cost: O(area): up to 4 · 10^14 cells.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.