Question

302. Smallest Rectangle Enclosing Black Pixels

中文文档

Description

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

 

Example 1:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

Example 2:

Input: image = [["1"]], x = 0, y = 0
Output: 1

 

Constraints:

• m == image.length
• n == image[i].length
• 1 <= m, n <= 100
• image[i][j] is either '0' or '1'.
• 0 <= x < m
• 0 <= y < n
• image[x][y] == '1'.
• The black pixels in the image only form one component.

Solutions

Solution 1

class Solution:
  def minArea(self, image: List[List[str]], x: int, y: int) -> int:
    m, n = len(image), len(image[0])
    left, right = 0, x
    while left < right:
      mid = (left + right) >> 1
      c = 0
      while c < n and image[mid][c] == '0':
        c += 1
      if c < n:
        right = mid
      else:
        left = mid + 1
    u = left
    left, right = x, m - 1
    while left < right:
      mid = (left + right + 1) >> 1
      c = 0
      while c < n and image[mid][c] == '0':
        c += 1
      if c < n:
        left = mid
      else:
        right = mid - 1
    d = left
    left, right = 0, y
    while left < right:
      mid = (left + right) >> 1
      r = 0
      while r < m and image[r][mid] == '0':
        r += 1
      if r < m:
        right = mid
      else:
        left = mid + 1
    l = left
    left, right = y, n - 1
    while left < right:
      mid = (left + right + 1) >> 1
      r = 0
      while r < m and image[r][mid] == '0':
        r += 1
      if r < m:
        left = mid
      else:
        right = mid - 1
    r = left
    return (d - u + 1) * (r - l + 1)

class Solution {

  public int minArea(char[][] image, int x, int y) {
    int m = image.length, n = image[0].length;
    int left = 0, right = x;
    while (left < right) {
      int mid = (left + right) >> 1;
      int c = 0;
      while (c < n && image[mid][c] == '0') {
        ++c;
      }
      if (c < n) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    int u = left;
    left = x;
    right = m - 1;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      int c = 0;
      while (c < n && image[mid][c] == '0') {
        ++c;
      }
      if (c < n) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    int d = left;
    left = 0;
    right = y;
    while (left < right) {
      int mid = (left + right) >> 1;
      int r = 0;
      while (r < m && image[r][mid] == '0') {
        ++r;
      }
      if (r < m) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    int l = left;
    left = y;
    right = n - 1;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      int r = 0;
      while (r < m && image[r][mid] == '0') {
        ++r;
      }
      if (r < m) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    int r = left;
    return (d - u + 1) * (r - l + 1);
  }
}

class Solution {
public:
  int minArea(vector<vector<char>>& image, int x, int y) {
    int m = image.size(), n = image[0].size();
    int left = 0, right = x;
    while (left < right) {
      int mid = (left + right) >> 1;
      int c = 0;
      while (c < n && image[mid][c] == '0') ++c;
      if (c < n)
        right = mid;
      else
        left = mid + 1;
    }
    int u = left;
    left = x;
    right = m - 1;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      int c = 0;
      while (c < n && image[mid][c] == '0') ++c;
      if (c < n)
        left = mid;
      else
        right = mid - 1;
    }
    int d = left;
    left = 0;
    right = y;
    while (left < right) {
      int mid = (left + right) >> 1;
      int r = 0;
      while (r < m && image[r][mid] == '0') ++r;
      if (r < m)
        right = mid;
      else
        left = mid + 1;
    }
    int l = left;
    left = y;
    right = n - 1;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      int r = 0;
      while (r < m && image[r][mid] == '0') ++r;
      if (r < m)
        left = mid;
      else
        right = mid - 1;
    }
    int r = left;
    return (d - u + 1) * (r - l + 1);
  }
};

func minArea(image [][]byte, x int, y int) int {
  m, n := len(image), len(image[0])
  left, right := 0, x
  for left < right {
    mid := (left + right) >> 1
    c := 0
    for c < n && image[mid][c] == '0' {
      c++
    }
    if c < n {
      right = mid
    } else {
      left = mid + 1
    }
  }
  u := left
  left, right = x, m-1
  for left < right {
    mid := (left + right + 1) >> 1
    c := 0
    for c < n && image[mid][c] == '0' {
      c++
    }
    if c < n {
      left = mid
    } else {
      right = mid - 1
    }
  }
  d := left
  left, right = 0, y
  for left < right {
    mid := (left + right) >> 1
    r := 0
    for r < m && image[r][mid] == '0' {
      r++
    }
    if r < m {
      right = mid
    } else {
      left = mid + 1
    }
  }
  l := left
  left, right = y, n-1
  for left < right {
    mid := (left + right + 1) >> 1
    r := 0
    for r < m && image[r][mid] == '0' {
      r++
    }
    if r < m {
      left = mid
    } else {
      right = mid - 1
    }
  }
  r := left
  return (d - u + 1) * (r - l + 1)
}