Largest area rectangular sub-matrix with equal number of 1’s and 0’s Hard 0 attempts
GeeksforGeeks ↗

Largest area rectangular sub-matrix with equal number of 1’s and 0’s

Hard Dynamic ProgrammingMemoization GeeksforGeeks

Given a binary matrix, find the largest area rectangular sub-matrix that has an equal number of 1s and 0s. Return the area of this sub-matrix. The approach converts 0s to -1s and uses a combination of prefix sums and longest subarray with zero sum.

Example:

Input: matrix = [[0,0,1,1],[0,1,1,0],[1,1,1,0],[1,0,0,1]]
Output: 8
Sample Input
—
Sample Output
—
Constraints
  • 1 <= R, C <= 50
Test Cases
Case 1
Args: [[[0,0,1,1],[0,1,1,0],[1,1,1,0],[1,0,0,1]]] Expected: 8
Topics
Dynamic ProgrammingMemoization

Convert 0→-1 then Largest Zero-Sum Submatrix

Replace 0s with -1s. For each pair of rows, compute column prefix sums and find longest zero-sum subarray.

function largestAreaEqual(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let maxArea = 0;
  for (let top = 0; top < m; top++) {
    const colSum = Array(n).fill(0);
    for (let bot = top; bot < m; bot++) {
      for (let j = 0; j < n; j++) colSum[j] += matrix[bot][j] === 0 ? -1 : 1;
      const map = new Map([[0, -1]]);
      let sum = 0;
      for (let j = 0; j < n; j++) {
        sum += colSum[j];
        if (map.has(sum)) maxArea = Math.max(maxArea, (bot-top+1) * (j - map.get(sum)));
        else map.set(sum, j);
      }
    }
  }
  return maxArea;
}

Time: O(m²n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript