Problem Description

You have a binary matrix image of size m x n where each cell contains either '0' (white pixel) or '1' (black pixel).

The key properties of this matrix are:

• All black pixels ('1') form a single connected region
• Black pixels are connected horizontally and vertically (not diagonally)
• You're given coordinates (x, y) of one black pixel in this region

Your task is to find the area of the smallest axis-aligned rectangle that can enclose all the black pixels in the matrix.

For example, if you have black pixels scattered in various positions, you need to find the tightest bounding box that contains all of them. The area would be calculated as (height × width) of this bounding rectangle.

Important constraint: Your algorithm must run in less than O(mn) time complexity, meaning you cannot simply scan through every cell in the matrix.

The solution uses binary search to efficiently find the boundaries of the black pixel region:

• Finds the topmost row containing a black pixel (upper boundary u)
• Finds the bottommost row containing a black pixel (lower boundary d)
• Finds the leftmost column containing a black pixel (left boundary l)
• Finds the rightmost column containing a black pixel (right boundary r)

The final area is calculated as (d - u + 1) * (r - l + 1), representing the height times the width of the bounding rectangle.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While the problem presents as a 2D matrix, we can conceptualize it as a graph where each pixel is a node and adjacent pixels (horizontally and vertically) form edges. The black pixels form a connected component in this graph.

Is it a tree?

• No: The pixel connectivity structure is not a tree - it can have cycles. For example, four black pixels forming a square would create a cycle.

Is the problem related to directed acyclic graphs?

• No: The pixel connectivity is undirected (if pixel A connects to pixel B, then B connects to A).

Is the problem related to shortest paths?

• No: We're not finding shortest paths between pixels. We're finding the boundaries of a connected region.

Does the problem involve connectivity?

• Yes: The core property is that all black pixels form a single connected region. We need to explore this connected component to find its boundaries.

Does the problem have small constraints?

• No: The problem explicitly requires less than O(mn) complexity, suggesting the constraints are not small enough for exhaustive exploration.

Conclusion: Following the flowchart, we arrive at BFS as a potential solution. However, the problem's constraint of less than O(mn) complexity means we cannot use traditional DFS/BFS to explore all black pixels.

Note: While the flowchart suggests BFS for connectivity problems with larger constraints, the actual solution uses binary search instead of DFS/BFS traversal. This is because:

1. We know there's only one connected black region
2. We have a starting black pixel coordinate (x, y)
3. Binary search can find boundaries in O(m log n + n log m) time, which satisfies the complexity requirement

The DFS pattern would typically be used if we needed to explore the entire connected component, but here the optimization comes from using binary search to find the extreme boundaries without visiting every black pixel.

Intuition

The key insight comes from understanding what we're really looking for and the properties of the black pixel region.

Since all black pixels form a single connected region, and we need the smallest rectangle that encloses them all, we're essentially finding the extreme boundaries of this region - the topmost, bottommost, leftmost, and rightmost black pixels.

The naive approach would be to perform DFS/BFS from the given black pixel (x, y) to explore all connected black pixels and track the min/max coordinates. However, this would take O(mn) time in the worst case, violating our complexity requirement.

Here's the crucial observation: If we know there's at least one black pixel in a row or column, we can use binary search to find the boundary rows and columns.

Think about finding the topmost row with a black pixel:

• We know row x has a black pixel (given)
• We know rows above some boundary have no black pixels
• We know rows at or below the boundary have at least one black pixel
• This creates a binary property we can search on!

For each boundary:

1. Upper boundary: Binary search rows [0, x] to find the smallest row index that contains a black pixel
2. Lower boundary: Binary search rows [x, m-1] to find the largest row index that contains a black pixel
3. Left boundary: Binary search columns [0, y] to find the smallest column index that contains a black pixel
4. Right boundary: Binary search columns [y, n-1] to find the largest column index that contains a black pixel

To check if a row has a black pixel, we scan through all columns in that row (O(n) time). Similarly, checking a column takes O(m) time.

This gives us a total complexity of O(m log n + n log m):

• Finding horizontal boundaries: 2 binary searches × O(log m) iterations × O(n) per check
• Finding vertical boundaries: 2 binary searches × O(log n) iterations × O(m) per check

The area of the bounding rectangle is then simply (bottom - top + 1) × (right - left + 1).

Solution Approach

The implementation uses binary search to find the four boundaries of the black pixel region. Let's walk through each part:

Finding the Upper Boundary (topmost row with black pixel):

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:  # Found a black pixel in row mid
        right = mid
    else:  # No black pixel in row mid
        left = mid + 1
u = left

• Search range: [0, x] (we know row x has a black pixel)
• For each mid row, scan all columns to check if any black pixel exists
• If found (c < n), the boundary is at mid or above, so move right = mid
• If not found, the boundary is below mid, so move left = mid + 1

Finding the Lower Boundary (bottommost row with black pixel):

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:  # Found a black pixel in row mid
        left = mid
    else:  # No black pixel in row mid
        right = mid - 1
d = left

• Search range: [x, m-1]
• Note the mid = (left + right + 1) >> 1 to avoid infinite loop when finding maximum
• If black pixel found, boundary is at mid or below, so move left = mid
• If not found, boundary is above mid, so move right = mid - 1

Finding the Left Boundary (leftmost column with black pixel):

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:  # Found a black pixel in column mid
        right = mid
    else:  # No black pixel in column mid
        left = mid + 1
l = left

• Search range: [0, y] (we know column y has a black pixel)
• For each mid column, scan all rows to check if any black pixel exists
• Similar binary search logic as upper boundary

Finding the Right Boundary (rightmost column with black pixel):

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:  # Found a black pixel in column mid
        left = mid
    else:  # No black pixel in column mid
        right = mid - 1
r = left

• Search range: [y, n-1]
• Similar to finding the lower boundary, using mid = (left + right + 1) >> 1

Calculating the Area:

return (d - u + 1) * (r - l + 1)

• Height: d - u + 1 (inclusive of both boundaries)
• Width: r - l + 1 (inclusive of both boundaries)

The bit shift operation >> 1 is used instead of division by 2 for efficiency. The algorithm leverages the fact that the black region is connected, ensuring that if we find boundaries correctly, all black pixels will be enclosed within the rectangle defined by these boundaries.

Example Walkthrough

Let's walk through a concrete example to illustrate how the binary search solution finds the bounding rectangle.

Consider this 5×7 matrix with a connected black pixel region:

    0 1 2 3 4 5 6
0   0 0 0 0 0 0 0
1   0 0 1 1 1 0 0
2   0 1 1 1 0 0 0
3   0 0 1 0 0 0 0
4   0 0 0 0 0 0 0

Given: Starting black pixel at position (x=2, y=3) (row 2, column 3).

Step 1: Find Upper Boundary (topmost row with black pixel)

• Binary search range: [0, 2] (from row 0 to row x)
• Iteration 1: mid = 1, scan row 1 → find '1' at column 2 → black pixel found
  • Move right = 1, range becomes [0, 1]
• Iteration 2: mid = 0, scan row 0 → all '0's → no black pixel
  • Move left = 1, range becomes [1, 1]
• Result: u = 1 (row 1 is the topmost row with black pixels)

Step 2: Find Lower Boundary (bottommost row with black pixel)

• Binary search range: [2, 4] (from row x to last row)
• Iteration 1: mid = 3, scan row 3 → find '1' at column 2 → black pixel found
  • Move left = 3, range becomes [3, 4]
• Iteration 2: mid = 4, scan row 4 → all '0's → no black pixel
  • Move right = 3, range becomes [3, 3]
• Result: d = 3 (row 3 is the bottommost row with black pixels)

Step 3: Find Left Boundary (leftmost column with black pixel)

• Binary search range: [0, 3] (from column 0 to column y)
• Iteration 1: mid = 1, scan column 1 → find '1' at row 2 → black pixel found
  • Move right = 1, range becomes [0, 1]
• Iteration 2: mid = 0, scan column 0 → all '0's → no black pixel
  • Move left = 1, range becomes [1, 1]
• Result: l = 1 (column 1 is the leftmost column with black pixels)

Step 4: Find Right Boundary (rightmost column with black pixel)

• Binary search range: [3, 6] (from column y to last column)
• Iteration 1: mid = 5, scan column 5 → all '0's → no black pixel
  • Move right = 4, range becomes [3, 4]
• Iteration 2: mid = 4, scan column 4 → find '1' at row 1 → black pixel found
  • Move left = 4, range becomes [4, 4]
• Result: r = 4 (column 4 is the rightmost column with black pixels)

Step 5: Calculate Area

• Height = d - u + 1 = 3 - 1 + 1 = 3
• Width = r - l + 1 = 4 - 1 + 1 = 4
• Area = 3 × 4 = 12

The bounding rectangle encompasses rows [1,3] and columns [1,4], perfectly enclosing all black pixels:

    0 1 2 3 4 5 6
0   0 0 0 0 0 0 0
1   0 [1 1 1 1] 0 0
2   0 [1 1 1 0] 0 0
3   0 [0 1 0 0] 0 0
4   0 0 0 0 0 0 0

Time Complexity Analysis:

• Each binary search performs O(log m) or O(log n) iterations
• Each iteration scans a row (O(n)) or column (O(m))
• Total: O(m log n + n log m), which is better than the naive O(mn) approach

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * log n + n * log m) where m is the number of rows and n is the number of columns in the image.

The algorithm performs 4 binary searches:

• Two binary searches on rows (finding upper and lower boundaries): Each binary search takes O(log m) iterations, and in each iteration, we scan through all n columns to check if there's a '1' in that row, taking O(n) time. Total: 2 * O(log m * n) = O(n * log m)
• Two binary searches on columns (finding left and right boundaries): Each binary search takes O(log n) iterations, and in each iteration, we scan through all m rows to check if there's a '1' in that column, taking O(m) time. Total: 2 * O(log n * m) = O(m * log n)

Combined time complexity: O(m * log n + n * log m)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables (left, right, mid, u, d, l, r, c) regardless of the input size. No additional data structures are created that scale with the input dimensions.

Common Pitfalls

1. Incorrect Mid Calculation for Finding Maximum Boundaries

The Pitfall: When searching for the bottommost row or rightmost column (finding maximum boundaries), using the standard mid = (left + right) >> 1 can cause an infinite loop. Consider when left = 4 and right = 5:

• mid = (4 + 5) >> 1 = 4
• If a black pixel is found at position 4, we set left = mid = 4
• The loop continues with the same left = 4, right = 5, creating an infinite loop

The Solution: Use mid = (left + right + 1) >> 1 when finding maximum boundaries. This ensures:

• When left = 4 and right = 5: mid = (4 + 5 + 1) >> 1 = 5
• The search space properly reduces in each iteration

2. Off-by-One Error in Area Calculation

The Pitfall: Calculating the area as (bottom - top) * (right - left) instead of (bottom - top + 1) * (right - left + 1). This mistake comes from forgetting that both boundary positions are inclusive.

Example: If top = 2, bottom = 4, left = 1, right = 3:

• Wrong: (4 - 2) * (3 - 1) = 2 * 2 = 4
• Correct: (4 - 2 + 1) * (3 - 1 + 1) = 3 * 3 = 9

3. Incorrect Binary Search Boundary Updates

The Pitfall: Mixing up when to use right = mid vs right = mid - 1 and left = mid vs left = mid + 1. The wrong choice can either skip valid positions or cause infinite loops.

The Solution: Remember the pattern:

• When finding minimum (top/left boundaries):
  • If target found at mid: right = mid (mid could be the answer)
  • If not found: left = mid + 1 (answer is strictly greater than mid)
• When finding maximum (bottom/right boundaries):
  • If target found at mid: left = mid (mid could be the answer)
  • If not found: right = mid - 1 (answer is strictly less than mid)

4. Not Leveraging the Known Black Pixel Position

The Pitfall: Setting initial search ranges as [0, rows-1] and [0, cols-1] for all boundaries, which wastes the given information that position (x, y) contains a black pixel.

The Solution: Use the known position to optimize search ranges:

• Top boundary: search in [0, x] (answer must be ≤ x)
• Bottom boundary: search in [x, rows-1] (answer must be ≥ x)
• Left boundary: search in [0, y] (answer must be ≤ y)
• Right boundary: search in [y, cols-1] (answer must be ≥ y)

This reduces the search space and improves efficiency.