Largest rectangular sub-matrix whose sum is 0

The problem, simply

You get a grid of whole numbers with R rows and C columns. Some are negative. Find a rectangle of neighboring cells whose numbers add up to exactly 0, and make its area (rows times columns) as big as possible. Give back that area, or 0 if no rectangle works.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every rectangle.

1. Pick a top row and a bottom row.
2. Pick a left column and a right column.
3. Add up every number inside. If the total is 0, compare its area with the best.

class Solution {
    public int largestZeroSumArea(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 sum = 0;
                        for (int i = top; i <= bottom; i++)          // add every cell inside
                            for (int j = left; j <= right; j++)
                                sum += grid[i][j];
                        if (sum == 0) {
                            best = Math.max(best, (bottom - top + 1) * (right - left + 1));
                        }
                    }
        return best;
    }
}

How long it takes: about R^2 * C^2 rectangles, and adding one up can take R * C steps, O(R^3 * C^3). Extra room: a few counters, O(1). A table of prefix sums makes each total cost O(1), which brings this down to O(R^2 * C^2).

Way 2: the clever way

Turn the 2D problem into many 1D problems.

1. Pick a left column L. Start a list rowSum of R zeros.
2. Move the right column Rt from L to the end. Each time, add column Rt into rowSum. Now rowSum[i] is the sum of row i between L and Rt.
3. In rowSum, find the longest run of rows with sum 0. Walk down with a running total. Keep a hash map from each total to the first row where it appeared, starting with total 0 at row -1. If a total shows up again, the rows in between add to 0.
4. That run, times the strip width Rt - L + 1, is a zero rectangle. Keep the biggest area.

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

class Solution {
    public int largestZeroSumArea(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]; // widen the strip
                int rows = longestZeroRun(rowSum);
                best = Math.max(best, rows * (right - left + 1));
            }
        }
        return best;
    }

    // Longest run of neighbors in arr that adds up to 0.
    private int longestZeroRun(int[] arr) {
        Map<Integer, Integer> first = new HashMap<>();  // running total -> first row it appeared
        first.put(0, -1);                               // total 0 before the first row
        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)); // rows in between add to 0
            } else {
                first.put(total, i);                    // keep only the first time, for the longest run
            }
        }
        return best;
    }
}

How long it takes: C^2 / 2 strips, and each strip costs O(R) to widen and O(R) to scan, O(C^2 * R). If the grid has more columns than rows, pick strips of rows instead, for O(R^2 * C). Extra room: rowSum and the map, O(R).

Watch out for

• Start the map with total 0 at row -1. Without it, runs that start at row 0 are missed.
• The answer is an area, so multiply the run length by the strip width.
• Sums can get big. Use long for totals if numbers or grids are large.
• If the problem asks for the rectangle itself, remember top, bottom, left and right whenever the best changes.

What interviewers ask next

• Equal number of 0s and 1s in a binary grid: turn every 0 into -1, then run this same algorithm.
• Biggest sum rectangle (any total): same strips, but run Kadane's algorithm on rowSum instead of the zero run search.
• Count the rectangles with total 0, or with total k: same strips, and in the 1D step count how many earlier running totals equal total - k.
• Largest rectangle with sum at most k: same strips, with a sorted set of running totals and a ceiling search, O(C^2 * R log R).

Remember this

Grown-up words: squashing columns is column compression, the running total is a prefix sum, the notebook is a hash map from prefix sum to first index, and the whole method is "fix two boundaries, solve the 1D problem", the same trick as the maximum sum rectangle.