Prison Break
Description
A prisoner is planning to escape from prison!
The prison’s gate consists of horizontal and vertical bars that are spaced one unit apart, so the area of each hole between the bars is 1 x 1.
The prisoner manages to remove certain bars to make some bigger holes. Determine the area of the largest hole in the gate after the bars are removed.
Example
n = 6
m = 6
h = [4]
v = [2]In the images below, the left image depicts the initial prison gate with n = 6 horizontal and m = 6 vertical bars. The area of the biggest hole in the bars is 1 x 1. The right image depicts that same gate after the prisoner removes horizontal bar 4 and vertical bar 2, at which point the area of the biggest hole in the bars becomes 2 x 2 = 4.
This problem reduces to finding the longest consecutive run of removed horizontal bars and the longest consecutive run of removed vertical bars. Each consecutive run expands one dimension of the hole by one extra unit, so a run of length k creates a size of k + 1 in that direction. After sorting the removed-bar indices, scan each array to compute the maximum consecutive segment length, then return (max_horizontal_run + 1) × (max_vertical_run + 1). For the example, both runs have length 1, so the largest hole area is 2 × 2 = 4.
