Problem

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

Examples

Example 1: $$ \begin{array}{c c c c} 0 & 0 & \colorbox{gray}{1} & 0 \\ 0 & \colorbox{gray}{1} & \colorbox{gray}{1} & 0 \\ 0 & \colorbox{gray}{1} & 0 & 0 \\ \end{array} $$

1
2
3
4
5
6

Input: image = [
  "0010",
  "0110",
  "0100"
], x = 0, y = 2
Output: 6

Example 2:

1
2

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

Solution

Method 1 - Binary Search

To find the smallest rectangle enclosing all black pixels, one intuitive approach would be to perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from the given black pixel. However, to achieve a runtime complexity of less than O(mn), we can use a binary search.

Approach

  1. Binary Search:
    • Left Boundary: Use binary search to find the smallest column index with a black pixel.
    • Right Boundary: Use binary search to find the largest column index with a black pixel.
    • Top Boundary: Use binary search to find the smallest row index with a black pixel.
    • Bottom Boundary: Use binary search to find the largest row index with a black pixel.
  2. Calculate the area of the rectangle formed by these boundaries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length, n = image[0].length;
        int left = searchColumns(image, 0, y, 0, m, true);
        int right = searchColumns(image, y + 1, n, 0, m, false);
        int top = searchRows(image, 0, x, left, right, true);
        int bottom = searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

    private int searchColumns(char[][] image, int i, int j, int top, int bottom, boolean opt) {
        while (i != j) {
            int k = top, mid = (i + j) / 2;
            while (k < bottom && image[k][mid] == '0') k++;
            if (k < bottom == opt) j = mid;
            else i = mid + 1;
        }
        return i;
    }

    private int searchRows(char[][] image, int i, int j, int left, int right, boolean opt) {
        while (i != j) {
            int k = left, mid = (i + j) / 2;
            while (k < right && image[mid][k] == '0') k++;
            if (k < right == opt) j = mid;
            else i = mid + 1;
        }
        return i;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] image = {
                {'0', '0', '1', '0'},
                {'0', '1', '1', '0'},
                {'0', '1', '0', '0'}
        };
        System.out.println(sol.minArea(image, 1, 2)); // Output: 6
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m = len(image)
        n = len(image[0])
        
        left = self.searchColumns(image, 0, y, 0, m, True)
        right = self.searchColumns(image, y + 1, n, 0, m, False)
        top = self.searchRows(image, 0, x, left, right, True)
        bottom = self.searchRows(image, x + 1, m, left, right, False)
        
        return (right - left) * (bottom - top)
    
    def searchColumns(self, image: List[List[str]], i: int, j: int, top: int, bottom: int, opt: bool) -> int:
        while i != j:
            mid = (i + j) // 2
            k = top
            while k < bottom and image[k][mid] == '0':
                k += 1
            if (k < bottom) == opt:
                j = mid
            else:
                i = mid + 1
        return i
    
    def searchRows(self, image: List[List[str]], i: int, j: int, left: int, right: int, opt: bool) -> int:
        while i != j:
            mid = (i + j) // 2
            k = left
            while k < right and image[mid][k] == '0':
                k += 1
            if (k < right) == opt:
                j = mid
            else:
                i = mid + 1
        return i

Complexity

  • ⏰ Time complexity: O(m log n + n log m) because each binary search runs in O(\log n) and it is run for each row and column.
  • 🧺 Space complexity: O(1) as we use a constant amount of extra space.