Largest area rectangular sub-matrix with equal number of 1s and 0s

The problem, simply

You get a grid with R rows and C columns. Every cell is 0 or 1. Find a rectangle of neighboring cells that holds the same number of 0s and 1s, and make its area as big as possible. Give back the area, or 0 if there is none.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every rectangle and count.

1. Pick a top and bottom row, and a left and right column.
2. Count the 0s and 1s inside.
3. If the counts are equal, compare the area with the best.

class Solution {
    public int largestEqualArea(int[][] grid) {
        int R = grid.length, C = grid[0].length, best = 0;
        for (int top = 0; top < R; top++)
            for (int bottom = top; bottom < R; bottom++)
                for (int left = 0; left < C; left++)
                    for (int right = left; right < C; right++) {
                        int ones = 0, zeros = 0;
                        for (int i = top; i <= bottom; i++)
                            for (int j = left; j <= right; j++) {
                                if (grid[i][j] == 1) ones++;
                                else zeros++;
                            }
                        if (ones == zeros) {
                            best = Math.max(best, (bottom - top + 1) * (right - left + 1));
                        }
                    }
        return best;
    }
}

How long it takes: about R^2 * C^2 rectangles and up to R * C cells to count in each, O(R^3 * C^3). Extra room: two counters, O(1).

Way 2: the clever way

1. Treat every 0 as -1 (you can do it on the fly, without copying the grid).
2. Pick a left column. Keep rowSum, one number per row, starting at 0.
3. Move the right column across. Add that column into rowSum.
4. In rowSum, find the longest run of rows that adds up to 0, using a running total and a hash map from each total to the first row it appeared (total 0 starts at row -1).
5. Run length times strip width is a balanced rectangle. Keep the biggest.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int largestEqualArea(int[][] grid) {
        int R = grid.length, C = grid[0].length, best = 0;
        for (int left = 0; left < C; left++) {
            int[] rowSum = new int[R];
            for (int right = left; right < C; right++) {
                for (int i = 0; i < R; i++) {
                    rowSum[i] += grid[i][right] == 1 ? 1 : -1;   // a 0 counts as -1
                }
                int rows = longestZeroRun(rowSum);
                best = Math.max(best, rows * (right - left + 1));
            }
        }
        return best;
    }

    private int longestZeroRun(int[] arr) {
        Map<Integer, Integer> first = new HashMap<>();   // running total -> first row
        first.put(0, -1);
        int total = 0, best = 0;
        for (int i = 0; i < arr.length; i++) {
            total += arr[i];
            if (first.containsKey(total)) best = Math.max(best, i - first.get(total));
            else first.put(total, i);
        }
        return best;
    }
}

How long it takes: C^2 / 2 strips, O(R) work each, O(C^2 * R). Choose strips along the shorter side to get O(min(R, C)^2 * max(R, C)). Extra room: rowSum and the map, O(R).

Since running totals in one strip stay between -R * width and R * width, you can swap the hash map for an array with an offset. It is faster in practice but the same big O.

Watch out for

• Put total 0 at row -1 in the map before the scan, or runs that start at the top row are missed.
• Keep the first row for each total. Overwriting it makes runs shorter.
• The answer is an area: rows times columns, not just rows.
• A balanced rectangle always has an even area. If you get an odd answer, something is off.

What interviewers ask next

• The one row version: longest subarray with equal 0s and 1s. It is the longestZeroRun step alone, O(n).
• Largest rectangle with sum 0 in any integer grid: exactly this algorithm without the -1 step.
• Largest rectangle of only 1s: a different trick. Build bar heights row by row and use the largest rectangle in a histogram with a stack, O(R * C).
• Count balanced rectangles instead of finding the largest: in the 1D step, add how many times the current total was seen before.
• Equal numbers of three kinds (0, 1, 2): track two differences, like (count1 - count0, count2 - count0), as the map key.

Remember this

Grown-up words: the minus sign trick is a transformation to a zero sum problem, squashing columns is column compression, the running total is a prefix sum, and the notebook is a hash map from prefix sum to first index.