Largest area rectangular sub-matrix with equal number of 1s and 0s [IMP]
Problem Statement
Given a binary matrix (containing only 0s and 1s), find the largest area rectangular sub-matrix that has an equal number of 1s and 0s. Return the area of this sub-matrix.
Example:
- Input:
0 0 1 1
0 1 1 0
1 1 1 0
- Output:
8 - Explanation: The sub-matrix from rows 0-1 and columns 0-3 has four 0s and four 1s. Area = 2×4 = 8.
Noob-Friendly Explanation
Imagine a checkerboard-like grid where each cell is either black (0) or white (1). You want to find the biggest rectangle inside this grid that has exactly the same number of black and white cells. It's like finding the biggest balanced team where the number of boys equals the number of girls!
The trick is: if we replace all 0s with -1s, then the problem becomes finding the largest sub-matrix whose sum is 0 (because equal 1s and -1s cancel out to zero).
Approach 1: Brute Force
Intuition
Check every possible rectangle in the matrix. Count the number of 0s and 1s in each. If they're equal, track the area.
Algorithm
- Fix all four boundaries (top, bottom, left, right).
- Count 0s and 1s in the sub-matrix.
- If counts are equal, update the maximum area.
class Solution {
public int largestAreaEqual01(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++) {
int ones = 0, zeros = 0;
for (int i = top; i <= bottom; i++) {
for (int j = left; j <= right; j++) {
if (matrix[i][j] == 1) ones++;
else zeros++;
}
}
if (ones == zeros) {
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 boundaries, two for counting.
- Space Complexity: O(1) - Only variables.
Approach 2: Optimal (Replace 0 with -1 + Column Compression)
Intuition
Replace all 0s with -1s. Now, "equal 0s and 1s" becomes "sum = 0". This transforms the problem into finding the largest sub-matrix with sum 0, which we solve using column compression and HashMap.
Algorithm
- Replace all 0s in the matrix with -1.
- Fix left column
land right columnr. - Compute compressed row sums for rows between columns
landr. - Find the longest subarray with sum 0 using prefix sum + HashMap.
- Area = length × width.
import java.util.HashMap;
class Solution {
public int largestAreaEqual01(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
// Replace 0 with -1
int[][] modified = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
modified[i][j] = matrix[i][j] == 0 ? -1 : 1;
}
}
int maxArea = 0;
for (int left = 0; left < cols; left++) {
int[] rowSum = new int[rows];
for (int right = left; right < cols; right++) {
for (int i = 0; i < rows; i++) {
rowSum[i] += modified[i][right];
}
// Find longest subarray with sum 0
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);
int prefixSum = 0;
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
prefixSum += arr[i];
if (map.containsKey(prefixSum)) {
maxLen = Math.max(maxLen, i - map.get(prefixSum));
} else {
map.put(prefixSum, i);
}
}
return maxLen;
}
}Complexity Analysis
- Time Complexity: O(n * m^2) - Two loops for column pairs and O(n) for each subarray.
- Space Complexity: O(n) - For rowSum array and HashMap.