370. Defense of a Kingdom

A rectangular kingdom is a grid W columns wide and H rows tall. n crossbow towers stand on distinct integer cells (xi, yi), no two sharing a column or a row; each tower defends its entire row and its entire column. The undefended cells form one or more rectangular blocks. Find the area (number of cells) of the largest such undefended block. (Classic SPOJ 'DEFKIN' problem.)

Input: The first line contains W, the kingdom's width. The second line contains H, the kingdom's height. The third line contains n, the number of towers. Each of the next n lines contains two space-separated integers, a tower's column and row. Output: Print a single integer - the area of the largest undefended rectangular block.

1 <= W, H <= 10^4, 0 <= n <= min(W, H)

Don't forget the two BOUNDARY gaps (before the first tower and after the last tower, against 0 and W+1/H+1) - these are easy to miss but can sometimes produce the actual largest gap, especially when towers cluster away from the grid's edges.

Given crossbow towers defending entire rows and columns of a grid, find the largest undefended rectangular block. Brute force: Check every possible rectangular region of the grid directly for being entirely undefended - this costs O(W²*H²) or worse, far too slow for W,H up to 10^4. Optimised: Since towers block entire ROWS and COLUMNS (not just their own cell), the undefended region's shape is entirely determined by the GAPS between consecutive tower x-coordinates and, independently, between consecutive tower y-coordinates - reducing a seemingly 2D search to two independent 1D gap-finding problems, each solved with a simple sort and linear scan.

Sort the tower x-coordinates together with the grid boundaries 0 and W+1, and scan once to find the largest gap between consecutive values; do the exact same thing independently for the y-coordinates with boundaries 0 and H+1. Because no tower's x lies inside the widest x-gap and no tower's y lies inside the widest y-gap, the rectangle formed by crossing those two gaps is guaranteed free of every tower's row and column, so the answer is simply the largest x-gap multiplied by the largest y-gap. Sorting is the only real cost, making this both simple and asymptotically optimal. Time: O(n log n) Space: O(n)

Realize that only the gaps between two towers that are immediate neighbors along the x-axis (and separately along the y-axis) can ever bound a maximal undefended rectangle, since any wider span would contain another tower's row or column inside it. For each tower, scan all other towers in O(n) to find its immediate next neighbor by x-coordinate, and do the same independently for y-coordinates, collecting every consecutive gap this way instead of testing every possible rectangle. This cuts the problem down to just comparing gap sizes, but still relies on an O(n) neighbor scan per tower instead of sorting. Time: O(n^2) Space: O(n)

Try every possible rectangle by picking any two candidate column boundaries and any two candidate row boundaries (from the grid edges and tower coordinates), then scan all n towers to check whether any of them sits inside that column or row span. Keep the largest rectangle that passes the check. This works because it exhaustively considers every possible undefended region, but it repeats a huge amount of redundant validation work since most candidate rectangles are never actually maximal. Time: O(n^5) Space: O(n)

1. Sort the towers' x-coordinates and, separately, their y-coordinates. 2. The largest undefended HORIZONTAL gap is the biggest difference between consecutive x-coordinates (minus 1), also checking the two boundary gaps against 0 and W+1; do the same for the y-coordinates. 3. The largest undefended rectangle's area is exactly (largest x-gap) times (largest y-gap).

Time: O(n log n), dominated by sorting the x and y coordinates independently. Space: O(n), for the sorted coordinate lists.

n = 0 (no towers, the whole grid is undefended), towers positioned at the kingdom's edge rows/columns, and W or H at their maximum of 10^4 to confirm the gap computation runs efficiently.

Be ready to explain WHY the 2D problem decomposes into two independent 1D problems - since a tower blocks its ENTIRE row and column, the undefended area's width only depends on x-gaps and its height only depends on y-gaps, completely independently of each other.