Empty Rectangle From Marked Points

Medium

Some points dots are marked on a grid, each given as a pair of coordinates [x, y]. Pick four of them that form the corners of an axis-aligned rectangle such that no other marked point lies inside the rectangle or on its sides. Return the largest area of such a rectangle, or -1 if no suitable rectangle exists.

Example 1

dots=[[0, 0], [0, 2], [4, 0], [4, 2], [0, 5], [4, 5], [2, 3]] → 8

The rectangle with corners (0, 0) and (4, 2) is empty and has area 8. The one from (0, 2) to (4, 5) is bigger, but (2, 3) lies inside it, and the largest one, from (0, 0) to (4, 5), has (0, 2) and (4, 2) on its sides.

Example 2

dots=[[1, 1], [1, 4], [6, 1], [6, 4], [3, 4]] → -1

The only rectangle is spoiled by (3, 4) on its top side, so the answer is -1.

Example 3

dots=[[7, 7]] → -1

Constraints

1 ≤ len(dots) ≤ 10
dots[i] = [x, y], 0 ≤ x, y ≤ 100
All points are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Geometry Array Math Enumeration Sorting

Similar problems

Clean Rectangle on Pins Hard Empty Boxes Between Points Medium Corner Pairs With No One Between Hard Rebuild the Line from Height Records Medium Smallest Paddock Medium

Input

dots=[[0, 0], [0, 2], [4, 0], [4, 2], [0, 5], [4, 5], [2, 3]]

Expected

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