#302 - Smallest Rectangle Enclosing Black Pixels

Hard • View on LeetCode • View on GitHub

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

Problem 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

Solution

/**
 * @param {character[][]} image
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var minArea = function(image, x, y) {
  const rows = image.length;
  const cols = image[0].length;
  const top = binarySearch(0, x, true, true);
  const bottom = binarySearch(x, rows - 1, true, false);
  const left = binarySearch(0, y, false, true);
  const right = binarySearch(y, cols - 1, false, false);

  return (bottom - top + 1) * (right - left + 1);

  function binarySearch(start, end, isRow, isMin) {
    let result = isMin ? end : start;
    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      let hasBlack = false;
      for (let i = 0; i < (isRow ? cols : rows); i++) {
        const pixel = isRow ? image[mid][i] : image[i][mid];
        if (pixel === '1') {
          hasBlack = true;
          break;
        }
      }
      if (hasBlack) {
        result = mid;
        if (isMin) {
          end = mid - 1;
        } else {
          start = mid + 1;
        }
      } else {
        if (isMin) {
          start = mid + 1;
        } else {
          end = mid - 1;
        }
      }
    }
    return result;
  }
};