Smallest rectangle enclosing black pixels

Array Binary Search Depth-First Search Breadth-First Search Matrix

60.8% acceptance

Mar 31, 2026

564

107

You are given an m x n binary matrix image where 0 represents a white pixel and 1 represents a black pixel. The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically. Given two integers x and y that represents the location of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels. You must write an algorithm with less than O(mn) runtime complexity

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_area(image: Vec<Vec<char>>, x: i32, y: i32) -> i32 {
    let m = image.len();
    let n = image[0].len();
    let x = x as usize;
    let y = y as usize;

    // Binary search for top boundary (first row with '1')
    let top = {
      let (mut lo, mut hi) = (0, x);
      while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if image[mid].iter().any(|&c| c == '1') {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }
      lo
    };

    // Binary search for bottom boundary (last row with '1')
    let bottom = {
      let (mut lo, mut hi) = (x, m - 1);
      while lo < hi {
        let mid = lo + (hi - lo + 1) / 2;
        if image[mid].iter().any(|&c| c == '1') {
          lo = mid;
        } else {
          hi = mid - 1;
        }
      }
      lo
    };

    // Binary search for left boundary (first col with '1')
    let left = {
      let (mut lo, mut hi) = (0, y);
      while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if (0..m).any(|r| image[r][mid] == '1') {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }
      lo
    };

    // Binary search for right boundary (last col with '1')
    let right = {
      let (mut lo, mut hi) = (y, n - 1);
      while lo < hi {
        let mid = lo + (hi - lo + 1) / 2;
        if (0..m).any(|r| image[r][mid] == '1') {
          lo = mid;
        } else {
          hi = mid - 1;
        }
      }
      lo
    };

    ((bottom - top + 1) * (right - left + 1)) as i32
  }
}