Find the minimum area to cover all ones ii

Array Matrix Enumeration

63.6% acceptance

Feb 24, 2026

402

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 these rectangles. Note that the rectangles are allowed to touch.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_sum(grid: Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();

    // min_rect(r1,c1,r2,c2) = area of bounding box of 1s in rectangle
    let min_area = |r1: usize, c1: usize, r2: usize, c2: usize| -> i32 {
      let mut min_r = rows;
      let mut max_r = 0usize;
      let mut min_c = cols;
      let mut max_c = 0usize;
      let mut found = false;
      for r in r1..=r2 {
        for c in c1..=c2 {
          if grid[r][c] == 1 {
            if r < min_r { min_r = r; }
            if r > max_r { max_r = r; }
            if c < min_c { min_c = c; }
            if c > max_c { max_c = c; }
            found = true;
          }
        }
      }
      if !found { 0 } else { ((max_r - min_r + 1) * (max_c - min_c + 1)) as i32 }
    };

    let mut ans = i32::MAX;

    // Split horizontally into 3 parts: rows [0..r1], [r1..r2], [r2..rows-1]
    for r1 in 1..rows {
      for r2 in r1 + 1..rows {
        let a = min_area(0, 0, r1 - 1, cols - 1);
        let b = min_area(r1, 0, r2 - 1, cols - 1);
        let c = min_area(r2, 0, rows - 1, cols - 1);
        ans = ans.min(a + b + c);
      }
    }

    // Split vertically into 3 parts
    for c1 in 1..cols {
      for c2 in c1 + 1..cols {
        let a = min_area(0, 0, rows - 1, c1 - 1);
        let b = min_area(0, c1, rows - 1, c2 - 1);
        let c = min_area(0, c2, rows - 1, cols - 1);
        ans = ans.min(a + b + c);
      }
    }

    // Split: horizontal then vertical (2 different combinations)
    // First horiz split at r1 (top/bottom), then vert split at c1 in bottom
    for r1 in 1..rows {
      for c1 in 1..cols {
        // Top rect: rows 0..r1, all cols
        let top = min_area(0, 0, r1 - 1, cols - 1);
        // Bottom-left: rows r1..rows, cols 0..c1
        let bl = min_area(r1, 0, rows - 1, c1 - 1);
        // Bottom-right: rows r1..rows, cols c1..cols
        let br = min_area(r1, c1, rows - 1, cols - 1);
        ans = ans.min(top + bl + br);

        // Bottom rect: rows r1..rows, all cols
        let bot = min_area(r1, 0, rows - 1, cols - 1);
        // Top-left: rows 0..r1, cols 0..c1
        let tl = min_area(0, 0, r1 - 1, c1 - 1);
        // Top-right: rows 0..r1, cols c1..cols
        let tr = min_area(0, c1, r1 - 1, cols - 1);
        ans = ans.min(bot + tl + tr);
      }
    }

    // Split: vertical then horizontal (2 more combinations)
    for c1 in 1..cols {
      for r1 in 1..rows {
        // Left rect: all rows, cols 0..c1
        let left = min_area(0, 0, rows - 1, c1 - 1);
        // Right-top: rows 0..r1, cols c1..cols
        let rt = min_area(0, c1, r1 - 1, cols - 1);
        // Right-bottom: rows r1..rows, cols c1..cols
        let rb = min_area(r1, c1, rows - 1, cols - 1);
        ans = ans.min(left + rt + rb);

        // Right rect: all rows, cols c1..cols
        let right = min_area(0, c1, rows - 1, cols - 1);
        // Left-top: rows 0..r1, cols 0..c1
        let lt = min_area(0, 0, r1 - 1, c1 - 1);
        // Left-bottom: rows r1..rows, cols 0..c1
        let lb = min_area(r1, 0, rows - 1, c1 - 1);
        ans = ans.min(right + lt + lb);
      }
    }

    ans
  }
}