Clean Rectangle on Pins

Hard

Pins are stuck into a large corkboard. Pin i sits at (xs[i], ys[i]), and no two pins share a spot. Stretch a rubber band over four pins so that it forms a rectangle with sides parallel to the axes. The rectangle is clean if no pin other than its four corners lies inside it or on its sides. Return the largest area of a clean rectangle, or -1 if there is none.

Example 1

xs=[0, 0, 4, 4], ys=[0, 2, 0, 2] → 8

The four pins form a 4 × 2 rectangle with no other pins around, so the area is 8.

Example 2

xs=[0, 0, 4, 4, 2], ys=[0, 2, 0, 2, 2] → -1

The only rectangle is spoiled: pin (2, 2) sits on its top side.

Example 3

xs=[0, 0, 2, 2, 5, 5], ys=[0, 3, 0, 3, 0, 3] → 9

The 2 × 3 and 3 × 3 rectangles are clean, while the big 5 × 3 one touches pins (2, 0) and (2, 3). The answer is 9.

Constraints

1 ≤ len(xs) = len(ys) ≤ 2 · 10⁵
0 ≤ xs[i], ys[i] ≤ 8 · 10⁷
All pins are at distinct points

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Geometry Array Math Sorting

Similar problems

Empty Rectangle From Marked Points Medium Best View for a Turning Camera Hard Nearest Pair of Sensors Hard Deal Out From the Lowest Card Hard Best Pair Above the Bars Hard

Input

xs=[0, 0, 4, 4], ys=[0, 2, 0, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.