You are given a 2D binary array grid. You need to find 3 non-overlapping rectangles having non-zero areas with horizontal and vertical sides such that all the 1's in grid lie inside these rectangles. Return the minimum possible sum of the area of th

minimumSum.js

/**
 * Finds the minimum total area of 3 non-overlapping rectangles
 * that cover all the 1s in a binary grid.
 * @param {number[][]} grid
 * @return {number}
 */
var minimumSum = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const memo = new Map();

  /**
   * Computes the area of the smallest bounding rectangle
   * that covers all 1s in the subgrid from (i1,j1) to (i2,j2).
   * If there are no 1s, returns 0.
   */
  function getOne(i1, j1, i2, j2) {
    let minRow = Infinity, maxRow = -Infinity;
    let minCol = Infinity, maxCol = -Infinity;

    for (let i = i1; i <= i2; i++) {
      for (let j = j1; j <= j2; j++) {
        if (grid[i][j] === 1) {
          minRow = Math.min(minRow, i);
          maxRow = Math.max(maxRow, i);
          minCol = Math.min(minCol, j);
          maxCol = Math.max(maxCol, j);
        }
      }
    }

    // No 1s found in this region
    if (minRow === Infinity) return 0;

    return (maxRow - minRow + 1) * (maxCol - minCol + 1);
  }

  /**
   * Recursively computes the minimum area to cover all 1s
   * in the subgrid from (i1,j1) to (i2,j2) using k rectangles.
   * Uses memoization to avoid redundant computation.
   */
  function getNext(i1, j1, i2, j2, k) {
    const key = `${i1},${j1},${i2},${j2},${k}`;
    if (memo.has(key)) return memo.get(key);

    let minArea = Infinity;

    if (k === 1) {
      // Base case: cover with one rectangle
      minArea = getOne(i1, j1, i2, j2);
    } else if (k === 2) {
      // Try all vertical splits
      for (let i = i1; i < i2; i++) {
        minArea = Math.min(
          minArea,
          getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 1)
        );
      }
      // Try all horizontal splits
      for (let j = j1; j < j2; j++) {
        minArea = Math.min(
          minArea,
          getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 1)
        );
      }
    } else if (k === 3) {
      // Try all vertical splits with 1+2 and 2+1 rectangle combinations
      for (let i = i1; i < i2; i++) {
        minArea = Math.min(
          minArea,
          getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 2),
          getNext(i1, j1, i, j2, 2) + getNext(i + 1, j1, i2, j2, 1)
        );
      }
      // Try all horizontal splits with 1+2 and 2+1 combinations
      for (let j = j1; j < j2; j++) {
        minArea = Math.min(
          minArea,
          getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 2),
          getNext(i1, j1, i2, j, 2) + getNext(i1, j + 1, i2, j2, 1)
        );
      }
    }

    memo.set(key, minArea);
    return minArea;
  }

  // Start with the full grid and 3 rectangles
  return getNext(0, 0, m - 1, n - 1, 3);
};