Practice/Meta/Leetcode 302. Smallest Rectangle Enclosing Black Pixels

Leetcode 302. Smallest Rectangle Enclosing Black Pixels

CodingOptional

Problem

You are given a 2D binary matrix image where each cell contains either '0' (white) or '1' (black). All black pixels in the image form a single connected component (region).

You are also given the coordinates (x, y) of one black pixel within this connected region.

Your task is to compute the area of the smallest axis-aligned rectangle that completely encloses all black pixels in the image.

The rectangle must be axis-aligned, meaning its edges are parallel to the matrix's row and column axes.

Requirements

Return the area (width × height) of the minimum bounding rectangle
The solution should be more efficient than scanning every cell in the matrix
All black pixels are guaranteed to be connected (you can reach any black pixel from any other black pixel through adjacent black pixels)
The given coordinates (x, y) are guaranteed to point to a black pixel

Constraints

1 <= image.length, image[0].length <= 200
image[i][j] is either '0' or '1'
0 <= x < image.length
0 <= y < image[0].length
image[x][y] == '1'
All '1' pixels form a connected component
Time complexity: Aim for O(m log n + n log m) where m = number of rows, n = number of columns
Space complexity: O(m + n) or better

Examples

Example 1:

` Input: image = [ ['0','0','1','0'], ['0','1','1','0'], ['0','1','0','0'] ] x = 1, y = 2

Output: 6

Explanation: The black pixels are at positions: (0,2), (1,1), (1,2), (2,1)

The minimum bounding rectangle:

Top row: 0
Bottom row: 2
Left column: 1
Right column: 2

Height = 2 - 0 + 1 = 3 Width = 2 - 1 + 1 = 2 Area = 3 × 2 = 6 `

Example 2:

` Input: image = [['1']] x = 0, y = 0

Output: 1

Explanation: Single pixel forms a 1×1 rectangle with area 1. `

Example 3:

` Input: image = [ ['0','1','0'], ['0','1','0'], ['0','1','0'], ['0','1','0'] ] x = 2, y = 1

Output: 4

Explanation: Four pixels in a vertical line form a 4×1 rectangle with area 4. `