Problem Informations

• Problem Index: 302
• Problem Link: Smallest Rectangle Enclosing Black Pixels
• Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Matrix

Problem Description

You are given an $m \times 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 represent 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 == \text{image.length}$
• $n == \text{image}[i].\text{length}$
• $1 \leq m, n \leq 100$
• $\text{image}[i][j]$ is either '0' or '1'.
• $0 \leq x < m$
• $0 \leq y < n$
• $\text{image}[x][y] == ‘1’.$
• The black pixels in the image only form one component.

Intuition

The problem is to determine the area of the smallest axis-aligned rectangle that can enclose all the black pixels in a given binary matrix. The black pixels form a single connected component, meaning that they are connected horizontally or vertically. Given the constraints that the matrix can have a size of up to $100 \times 100$, the task requires determining the boundaries of the black region to calculate the area efficiently.

Approach

The approach involves iterating through the binary matrix to find the minimum and maximum coordinates of the black pixels, which will determine the bounds of the rectangle. Specifically, we will:

1. Initialize boundary variables up, down, left, and right to their respective extreme values. up is initialized to the number of rows minus one (m - 1), down to zero, left to the number of columns minus one (n - 1), and right to zero. These variables will be updated as more black pixels are discovered.

2. Traverse each cell in the matrix using two nested loops. The outer loop iterates over the rows, while the inner loop iterates over the columns.

3. For each cell, check if the pixel is black ('1'). If it is, update the boundaries:

   • up is updated to the smaller value between its current value and the current row index i.
   • down is updated to the larger value between its current value and the current row index i.
   • left is updated to the smaller value between its current value and the current column index j.
   • right is updated to the larger value between its current value and the current column index j.

4. After completing the traversal, the smallest enclosing rectangle will have its top-left corner at (up, left) and its bottom-right corner at (down, right).

5. The area of the rectangle can be computed by the formula: $$\text{Area} = (down - up + 1) \times (right - left + 1)$$ This will give the number of pixels in the smallest rectangle that can enclose all the black pixels.

As a result, the implementation efficiently calculates the desired area without exceeding the constraints, given that the loops together cover the matrix once with a time complexity of $O(m \cdot n)$.

Code

C++

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int m = image.size(); // Number of rows in the image
        int n = image[0].size(); // Number of columns in the image
        
        // Initialize the boundaries of the black pixel region
        int up = m - 1, down = 0, left = n - 1, right = 0;
        
        // Iterate through the entire matrix to find boundaries of the black region
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (image[i][j] == '1') { // If the pixel is black
                    up = min(up, i);   // Update the upper boundary
                    down = max(down, i); // Update the lower boundary
                    left = min(left, j); // Update the left boundary
                    right = max(right, j); // Update the right boundary
                }
            }
        }
        
        // Calculate and return the area of the enclosing rectangle
        return (down - up + 1) * (right - left + 1);
    }
};

Python

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m = len(image)  # Number of rows in the image
        n = len(image[0])  # Number of columns in the image

        # Initialize the boundaries of the black pixel region
        up = m - 1
        down = 0
        left = n - 1
        right = 0

        # Iterate through the entire matrix to find boundaries of the black region
        for i in range(m):
            for j in range(n):
                if image[i][j] == '1':  # If the pixel is black
                    up = min(up, i)  # Update the upper boundary
                    down = max(down, i)  # Update the lower boundary
                    left = min(left, j)  # Update the left boundary
                    right = max(right, j)  # Update the right boundary

        # Calculate and return the area of the enclosing rectangle
        return (down - up + 1) * (right - left + 1)

Complexity

• Time complexity: $O(m \times n)$
  The solution iterates through the entire $m \times n$ matrix to determine the boundaries of the black pixel region. It checks each element in the matrix exactly once, leading to a time complexity of $O(m \times n)$.

• Space complexity: $O(1)$
  The space complexity is $O(1)$ because the solution uses a fixed amount of extra space, regardless of the size of the input matrix. The variables used to store boundaries (up, down, left, right) and loop counters do not scale with the input size.