Largest rectangular sub-matrix whose sum is 0
Problem Statement
Given a 2D matrix of integers, find the largest rectangular sub-matrix whose sum is 0. Return the area (number of elements) of this sub-matrix.
Example:
- Input:
1, 2, 3
-3, -2, -1
1, 1, 1
- Output:
6 - Explanation: The sub-matrix formed by the first two rows has sum = 1+2+3+(-3)+(-2)+(-1) = 0. Its area is 2×3 = 6.
Noob-Friendly Explanation
Imagine you have a grid of numbers (positive and negative). You want to find the biggest rectangle inside this grid where all the numbers add up to exactly zero. Think of it like finding the largest piece of a spreadsheet where the total is perfectly balanced — positives and negatives cancel out completely.
Approach 1: Brute Force
Intuition
Try every possible rectangle (defined by top-left and bottom-right corners). Compute the sum of each rectangle and check if it's zero. Track the largest one.
Algorithm
- Fix top row and bottom row.
- Fix left column and right column.
- Compute the sum of the sub-matrix.
- If sum is 0, check if this rectangle is the largest so far.
class Solution {
public int largestZeroSumSubMatrix(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int maxArea = 0;
for (int top = 0; top < rows; top++) {
for (int bottom = top; bottom < rows; bottom++) {
for (int left = 0; left < cols; left++) {
for (int right = left; right < cols; right++) {
// Compute sum of sub-matrix
int sum = 0;
for (int i = top; i <= bottom; i++) {
for (int j = left; j <= right; j++) {
sum += matrix[i][j];
}
}
if (sum == 0) {
int area = (bottom - top + 1) * (right - left + 1);
maxArea = Math.max(maxArea, area);
}
}
}
}
}
return maxArea;
}
}Complexity Analysis
- Time Complexity: O(n^4 * m^2) - Four loops for rectangle bounds and two for sum computation (n=rows, m=cols).
- Space Complexity: O(1) - Only a few variables.
Approach 2: Optimal (Column Compression + HashMap)
Intuition
Fix the left and right columns. Compress each row between these columns into a single value (row sum). Now the problem reduces to finding the longest subarray with sum 0 in a 1D array, which can be solved with a HashMap.
Algorithm
- Fix left column
land right columnr. - Compute
rowSum[i]= sum ofmatrix[i][l..r]for each row. - Find the longest subarray in
rowSum[]with sum 0 using prefix sum + HashMap. - The area = length of that subarray × (r - l + 1).
import java.util.HashMap;
class Solution {
public int largestZeroSumSubMatrix(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int maxArea = 0;
for (int left = 0; left < cols; left++) {
int[] rowSum = new int[rows];
for (int right = left; right < cols; right++) {
// Add current column to rowSum
for (int i = 0; i < rows; i++) {
rowSum[i] += matrix[i][right];
}
// Find longest subarray with sum 0 in rowSum
int width = right - left + 1;
int longestLen = longestZeroSumSubarray(rowSum);
maxArea = Math.max(maxArea, longestLen * width);
}
}
return maxArea;
}
private int longestZeroSumSubarray(int[] arr) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // prefix sum 0 at index -1
int prefixSum = 0;
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
prefixSum += arr[i];
if (map.containsKey(prefixSum)) {
int len = i - map.get(prefixSum);
maxLen = Math.max(maxLen, len);
} else {
map.put(prefixSum, i);
}
}
return maxLen;
}
}Complexity Analysis
- Time Complexity: O(n * m^2) - Two loops for column pairs (m^2) and O(n) for each subarray search.
- Space Complexity: O(n) - For the rowSum array and HashMap.