335. Largest Rectangular Sub-Matrix Whose Sum Is 0

Given a matrix of integers, find the area (rows x cols) of the largest rectangular sub-matrix whose elements sum to exactly 0. Print 0 if no such sub-matrix exists.

Input: The first line contains rows and cols. Each of the next rows lines contains cols space-separated integers (which may be negative) forming the matrix. Output: Print a single integer - the area of the largest zero-sum rectangular sub-matrix, or 0 if none exists.

1 <= rows, cols <= 200

This is the DIRECT 2D generalization of 'Find if There Is a Subarray With Sum Equal to 0' from the Hashing category - recognizing the shared prefix-sum-hashmap foundation connects a 1D array technique to this harder 2D matrix problem.

Find the area of the largest rectangular sub-matrix whose elements sum to exactly 0. Brute force: Check every possible rectangle directly and sum its elements from scratch, checking for exactly 0 - this costs O(rows²*cols²) or worse, far too slow for larger matrices. Optimised: Collapsing rows into a 1D column-sum array reduces this to the well-known 'longest zero-sum subarray' technique (using a hashmap of prefix sums, where a REPEATED prefix sum value directly reveals a zero-sum range between the two occurrences) - applying this efficient 1D technique across every possible row-pair turns an expensive 2D search into O(rows²) efficient O(cols) scans.

Precompute a 2D prefix-sum table where prefix[i][j] holds the sum of all cells from (0,0) to (i,j). Then, for the same nested loop over every pair of corners, compute each rectangle's sum in O(1) using inclusion-exclusion on the prefix table instead of re-scanning its interior, keeping the same number of candidate rectangles but removing the per-rectangle summation cost entirely. Time: O(rows^2 * cols^2) Space: O(rows * cols)

For every possible pair of a top-left corner and a bottom-right corner, compute the sum of all cells inside that rectangle by iterating over every cell within it, and if the sum is exactly 0, compare its area against the best found so far. This checks every rectangle directly, but recomputes each rectangle's sum entirely from scratch, including heavy re-summation of overlapping regions shared by many candidate rectangles. Time: O(rows^3 * cols^3) Space: O(1)

Fix every pair of a left column and a right column; for each pair, collapse all rows between those columns into one 1D array of row-sums using row-prefix sums, then find the largest all-zero-sum sub-array of that 1D array in a single scan by recording, in a hash map, the earliest row index at which each running prefix-sum value was first seen - a repeated sum means everything between those two occurrences sums to zero. Multiplying the best such height by the fixed column width and taking the best over all column pairs solves the whole problem in far less work than examining every individual rectangle. Time: O(rows * cols^2) Space: O(rows)

1. Fix a pair of top and bottom rows, and collapse every column between them into a single running column-sum array - reducing the 2D problem to the classic 1D 'longest subarray summing to zero' problem. 2. For the 1D problem, track PREFIX SUMS and the FIRST column index at which each prefix-sum value was seen (using a hash map, with prefix sum 0 mapped to index -1 before the array starts) - a REPEATED prefix sum means the subarray between those two indices sums to 0. 3. Try every pair of top and bottom rows (O(rows²) pairs), and for each, the 1D scan is O(cols) - track the best area (height*width) seen across all of them.

Time: O(rows² * cols) - O(rows²) row-pairs, each with an O(cols) prefix-sum scan. Space: O(cols), for the prefix-sum hashmap reused across row-pairs.

Test a matrix with no zero-sum sub-matrix at all (print 0), a single row or single column matrix, and rows = cols = 200 (upper bound) for the O(rows^2 * cols) row-collapsing approach.

Be ready to explain the prefix-sum-hashmap technique for '1D zero-sum subarray' clearly, since it's the foundational sub-routine this 2D problem builds on - mapping prefix sum 0 to index -1 (before the array starts) is the key trick for correctly handling a zero-sum subarray starting from position 0.