n axis-aligned rectangles on the plane. Rectangle i has its bottom-left corner at lower[i] = [x1, y1] and its top-right corner at upper[i] = [x2, y2].
Find the largest area of an axis-aligned square that fits entirely inside the shared part of some two rectangles. If no pair overlaps in a region of positive area, return 0.lower=[[1, 1], [3, 2], [11, 11]], upper=[[6, 5], [9, 10], [13, 13]] → 9
The first two rectangles overlap from (3, 2) to (6, 5), a 3 × 3 square with area 9. The third overlaps nothing.
lower=[[1, 1], [3, 1]], upper=[[3, 5], [6, 5]] → 0
The rectangles only touch along the line x = 3; the shared region has zero width, so the answer is 0.
lower=[[1, 1], [2, 3]], upper=[[9, 4], [5, 10]] → 1
The overlap is a 3 × 1 rectangle, so only a 1 × 1 square fits.
lower=[[1, 1], [3, 2], [11, 11]], upper=[[6, 5], [9, 10], [13, 13]]
9
Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.