336. Largest Area Rectangular Sub-Matrix With Equal Number of 1s and 0s

Given a binary matrix (every entry is 0 or 1), find the area of the largest rectangular sub-matrix that contains an equal number of 0s and 1s. Print 0 if no such non-empty sub-matrix exists.

Input: The first line contains rows and cols. Each of the next rows lines contains cols space-separated binary digits (0 or 1) forming the matrix. Output: Print a single integer - the area of the largest sub-matrix with an equal count of 0s and 1s, or 0 if none exists.

1 <= rows, cols <= 200

This is a perfect example of REDUCING a new-looking problem to an ALREADY-SOLVED one via a simple value substitution - once you see that 0->-1 turns 'equal counts' into 'sum is zero', the rest of the solution is just reusing prior work.

Find the area of the largest rectangular sub-matrix with an equal count of 0s and 1s. Brute force: Check every possible rectangle directly, counting 0s and 1s and checking for equality - this costs O(rows²*cols²) or worse, far too slow for larger matrices. Optimised: The relabeling trick (0->-1, 1->+1) transforms 'equal counts of 0s and 1s' into 'sum equals zero' - a problem ALREADY SOLVED efficiently by the row-collapsing plus prefix-sum-hashmap technique, meaning this problem requires NO new algorithm at all, just a clever preprocessing step before reusing an existing one.

Build the same 2D prefix-sum table after mapping 0 to -1. For every pair of rows (r1, r2), collapse the band into a 1D running-sum array across columns and use the classic 'longest zero-sum subarray via hashmap of first-seen prefix sums' technique: as the running sum is computed column by column, look up whether that exact running-sum value has occurred before; if so, the subarray between those two positions sums to zero, and its width times the row-band height gives a candidate area. This finds the best column range for each row pair in a single linear pass instead of checking every column-pair combination. Time: O(rows^2 * cols) Space: O(rows*cols + cols)

Convert every 0 to -1 so a sub-matrix has an equal count of 0s and 1s exactly when its sum is zero, and build a 2D prefix-sum table in O(rows*cols). For every pair of rows (r1, r2), use the prefix sums to get, in O(1) per column, a collapsed array of column sums over that row band; then check every pair of column boundaries (c1, c2) directly against that collapsed array with a nested loop to find ranges summing to zero. This removes the need to rescan individual cells but still checks all column-pair combinations explicitly for each row pair. Time: O(rows^2 * cols^2) Space: O(rows*cols)

For every choice of top row r1, bottom row r2, left column c1, and right column c2 with r1<=r2 and c1<=c2, scan every cell inside that rectangle to count how many are 1s and how many are 0s, and check if the counts are equal. Track the maximum area among all rectangles that satisfy the condition. This checks the definition exhaustively but redoes the full cell scan for every one of the many candidate rectangles. Time: O(rows^3 * cols^3) in the worst case Space: O(1) extra

1. RELABEL every 0 in the matrix as -1, leaving every 1 as +1 - a sub-matrix now has an equal count of original 0s and 1s exactly when its SUM (under this relabeling) is 0. 2. This turns the problem into 'largest rectangular sub-matrix whose sum is 0' on the relabeled matrix, solvable with the same row-collapsing plus prefix-sum-hashmap technique. 3. A sub-matrix of a single 0 or single 1 alone is never valid on its own (unequal counts) - the smallest valid answer needs at least one of each.

Time: O(rows² * cols) - identical to the zero-sum rectangle problem's complexity, since the relabeling itself is O(rows*cols) and doesn't change the asymptotic cost. Space: O(cols), for the prefix-sum hashmap reused across row-pairs.

Test a matrix that is entirely 0s or entirely 1s (no valid sub-matrix exists, print 0) and rows = cols = 200 (upper bound) for the row-collapsing plus prefix-sum-hashmap approach.

Be ready to state the relabeling trick explicitly and immediately connect this problem to 'Largest Rectangular Sub-Matrix Whose Sum Is 0' - recognizing that a seemingly new problem is just a KNOWN problem with a simple value transformation is a valuable, broadly reusable interview skill.