DEFKIN - Defense of a Kingdom

The problem, simply

A kingdom is a grid w columns wide and h rows tall. There are k towers, each standing on one cell (x, y). A tower guards every cell in its column and every cell in its row.

Give back the area of the biggest rectangle of cells that no tower guards. (This is SPOJ DEFKIN.)

A story to remember it

Picture it

Examples

Way 1: the simple way

Draw the map. Mark every guarded column and every guarded row. Then walk the columns and find the longest run of unmarked ones, and do the same for the rows.

1. Make colGuarded[1..w] and rowGuarded[1..h], all false.
2. For every tower (x, y), set colGuarded[x] and rowGuarded[y].
3. Find the longest run of free columns and the longest run of free rows. Multiply them.

Why can you multiply? A free run of columns and a free run of rows always cross in a block where no cell shares a row or column with a tower.

class Solution {
    public long largestUndefended(int w, int h, int[][] towers) {
        boolean[] colGuarded = new boolean[w + 1];
        boolean[] rowGuarded = new boolean[h + 1];
        for (int[] t : towers) {
            colGuarded[t[0]] = true;     // the tower sees its column
            rowGuarded[t[1]] = true;     // and its row
        }
        return (long) longestFree(colGuarded, w) * longestFree(rowGuarded, h);
    }

    private int longestFree(boolean[] guarded, int n) {
        int best = 0, run = 0;
        for (int i = 1; i <= n; i++) {
            run = guarded[i] ? 0 : run + 1;
            best = Math.max(best, run);
        }
        return best;
    }
}

How long it takes: one pass over the towers, columns and rows, O(w + h + k). Extra room: the two marks arrays, O(w + h). Fine for a 40,000 wide kingdom, but useless if w could be a billion.

Way 2: the clever way

You do not need the whole map, only where the towers stand.

1. Put all tower x values in a list, plus two walls: 0 and w + 1. Sort it.
2. The free columns between two neighbors a and b in the sorted list are b - a - 1. Take the biggest.
3. Do the same with the y values and walls 0 and h + 1.
4. Multiply the two biggest gaps.

class Solution {
    public long largestUndefended(int w, int h, int[][] towers) {
        int k = towers.length;
        int[] xs = new int[k + 2], ys = new int[k + 2];
        xs[0] = 0; xs[k + 1] = w + 1;          // the two walls
        ys[0] = 0; ys[k + 1] = h + 1;
        for (int i = 0; i < k; i++) {
            xs[i + 1] = towers[i][0];
            ys[i + 1] = towers[i][1];
        }
        Arrays.sort(xs);
        Arrays.sort(ys);
        return (long) biggestGap(xs) * biggestGap(ys);
    }

    private int biggestGap(int[] sorted) {
        int best = 0;
        for (int i = 1; i < sorted.length; i++) {
            best = Math.max(best, sorted[i] - sorted[i - 1] - 1);  // free lines strictly between
        }
        return best;
    }
}

How long it takes: two sorts of k + 2 numbers, O(k log k). Extra room: the two lists, O(k).

Watch out for

• Add the walls at 0 and w + 1, not at 1 and w. Otherwise you lose the edge columns.
• Two towers can share a column. The gap between equal numbers is -1, which max ignores, so no special case is needed.
• With no towers the answer is w * h. The walls handle it.
• w * h can pass the int range on some versions. Multiply as long.

What interviewers ask next

• Why are rows and columns independent? A cell is safe exactly when its column is free and its row is free. So a rectangle is safe exactly when all its columns and all its rows are free.
• What if a tower only guarded nearby cells? Then the independence breaks, and you need the maximal rectangle in a binary matrix: histogram plus a stack, O(w * h).
• Towers are added one at a time and you must answer after each? Keep sorted sets of tower columns and rows plus a multiset of gaps. Each insert splits one gap into two, O(log k).
• Same trick elsewhere: "Maximum area of a piece of cake after horizontal and vertical cuts" (LeetCode 1465) is this problem with cut lines instead of towers.

Remember this

Grown-up words: the seekers are towers that block a full row and column, the free runs are gaps between sorted coordinates, and the walls at 0 and w + 1 are sentinels.