A Square Window in a Lattice

Medium

A lattice is made of bars: rows + 2 horizontal and cols + 2 vertical ones, splitting it into 1 × 1 cells. Horizontal bars are numbered top to bottom from 1 to rows + 2, vertical bars left to right from 1 to cols + 2. Some bars can be pulled out: the horizontal bars listed in loose_rows and the vertical bars listed in loose_cols. All other bars are fixed in place. Remove any of the loose bars (possibly none) so that a square opening appears in the lattice, and return the largest possible area of such an opening.

Example 1

rows=4, cols=3, loose_rows=[2, 3, 4], loose_cols=[3, 4] → 9

Removing horizontal bars 2–4 opens a gap 4 cells tall; removing vertical bars 3 and 4 opens one 3 cells wide. The square is limited by the smaller side: 3 × 3 = 9.

Example 2

rows=5, cols=5, loose_rows=[2, 4, 6], loose_cols=[2, 3] → 4

No two removable horizontal bars are adjacent, so the gap can be at most 2 cells tall. The answer is 2 × 2 = 4.

Constraints

1 ≤ rows, cols ≤ 10⁹
1 ≤ len(loose_rows), len(loose_cols) ≤ 10⁴
2 ≤ loose_rows[i] ≤ rows + 1
2 ≤ loose_cols[i] ≤ cols + 1
The numbers within each list are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sorting

Similar problems

Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Distinct Orderings With Repeats Medium Anagram Buckets Medium

Input

rows=4, cols=3, loose_rows=[2, 3, 4], loose_cols=[3, 4]

Expected

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