Problem Description:

You are given an image that is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel.

The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically. Given the location ( x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

Input:

board = [ ["0", "0", "1", "0"], ["0", "1", "1", "0"], ["0", "1", "0", "0"] ]

Input: x = 0, y = 2

Output: 6

Explanation: The answer is the blue rectangle that encloses the black pixels.

Solution:

The idea is to find the leftmost, rightmost, topmost, and bottommost black pixels, which can be used to construct the smallest rectangle enclosing all black pixels. For this, we can use binary search on every row and column.

We will first find the leftmost black pixel by applying binary search on each row, and then find the rightmost black pixel by applying binary search from right to left. Similarly, we can find the topmost and bottommost black pixels using binary search from top to bottom and bottom to top, respectively.

Once we have the coordinates of the leftmost, rightmost, topmost, and bottommost black pixels, we can calculate the area of the smallest rectangle enclosing them.

Pseudo Code:

function minArea(board, x, y): n = board.length, m = board[0].length

Finding the leftmost black pixel

left = binarySearch(0, y, 0, n, true, board)

Finding the rightmost black pixel

right = binarySearch(y, m, 0, n, false, board)

Finding the topmost black pixel

top = binarySearch(0, x, left, right, true, board)

Finding the bottommost black pixel

bottom = binarySearch(x, n, left, right, false, board)

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

function binarySearch(start, end, lo, hi, opt, board): while start <= end: mid = (start + end) / 2 foundBlackPixel = false for i in range(lo, hi): if board[i][mid] == "1": foundBlackPixel = true break

  if foundBlackPixel == opt:
     end = mid - 1
     best = mid
  else:
     start = mid + 1

return best

Time Complexity:

The time complexity of the above algorithm is O(m log n + n log m), where m and n are the dimensions of the given binary matrix.

Space Complexity:

The space complexity of the above algorithm is O(1).

Example:

board = [ ["0", "0", "1", "0"], ["0", "1", "1", "0"], ["0", "1", "0", "0"] ]

minArea(board, 0, 2) # Output: 6

Explanation: The leftmost black pixel is at (0,2), the rightmost black pixel is at (1,1), the topmost black pixel is at (0,2), and the bottommost black pixel is at (1,2). Therefore, the area of the smallest rectangle enclosing all black pixels is (1-0+1) * (2-0+1) = 6.

1