Square Plot by Pulling Fences

Medium

A field is a rectangle where one coordinate runs from 1 to length and the other from 1 to width. Its boundary is fenced, and those four fences cannot be removed. Straight fences also run across the whole field: cross fences at the marks cross_fences[i] along the length, and long fences at the marks long_fences[j] along the width. You may pull out any of the inner fences, or none. Afterwards, one of the fully enclosed plots must be a square. Return the largest possible area of such a square modulo 10⁹ + 7, or -1 if no square can be made. In other words, look for the largest distance that occurs both between two fences along the length and between two fences along the width (the field boundary counts as fences).

Example 1

length=5, width=4, cross_fences=[2, 4], long_fences=[3] → 9

Along the length the fences stand at 1, 2, 4, 5; along the width at 1, 3, 4. A gap of 3 exists in both directions (5 − 2 and 4 − 1), so a 3 × 3 plot of area 9 is possible.

Example 2

length=8, width=6, cross_fences=[3], long_fences=[5] → 25

The possible gaps along the length are 2, 5, 7 and along the width 1, 4, 5. Only 5 is shared, giving area 25.

Example 3

length=4, width=6, cross_fences=[2], long_fences=[3] → 9

Gaps along the length are 1, 2, 3 and along the width 2, 3, 5. The largest shared one is 3, so the area is 9.

Constraints

3 ≤ length, width ≤ 10⁹
1 ≤ len(cross_fences), len(long_fences) ≤ 600
1 < cross_fences[i] < length
1 < long_fences[j] < width
The marks within each list are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Enumeration