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

You're given a matrix of 0s and 1s. Among all rectangular sub-matrices you could carve out of it, find the one with the largest area where the count of 1s exactly matches the count of 0s, and return that area. A common way to approach this: treat every 0 as -1, then the problem reduces to finding a sub-matrix whose values sum to zero, which can be tackled with prefix sums combined with a search for the longest zero-sum subarray.

Input Format
Implement largestAreaEqual(matrix). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
matrix = [[0,0,1,1],[0,1,1,0],[1,1,1,0],[1,0,0,1]]
Output
8

Example 2

Input
matrix = [[1]]
Output
0
Constraints
  • 1 <= R, C <= 50
Test Cases (2)
Case 1
Args: [[[0,0,1,1],[0,1,1,0],[1,1,1,0],[1,0,0,1]]] Expected: 8
Case 2
Args: [[[1]]] Expected: 0
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.

javascript
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