/302. Smallest Rectangle Enclosing Black Pixels
Previous|Next

302. Smallest Rectangle Enclosing Black Pixels

Hard
Arrays60.8% acceptance

Given a 2D binary matrix image of size m x n, where each element is either 0 (white pixel) or 1 (black pixel), and the coordinates (row_index, col_index) of one black pixel, return the area of the smallest axis-aligned rectangle that encloses all black pixels (1) in the matrix.

Example 1

Input: [["0","1","0","0"],["0","1","0","0"],["0","1","1","0"],["0","0","0","0"], 1, 1]

Output: 6

Explanation: The rectangle from (1,1) to (2,2) covers all black pixels. Area = 2 x 3 = 6.

Example 2

Input: [["0","0","0"],["1","1","0"],["0","1","0"], 2, 1]

Output: 4

Explanation: The rectangle from (1,0) to (2,1) covers all black pixels. Area = 2 x 2 = 4.

Constraints

  • 1 <= len(image) <= 200
  • 1 <= len(image[0]) <= 200
  • image[i][j] is 0 or 1
  • 0 <= row_index < len(image)
  • 0 <= col_index < len(image[0])
  • image[row_index][col_index] == 1
Python (current runtime)

Case 1

Input: [["0","0","0","0"],["0","1","1","0"],["0","1","1","0"],["0","0","0","0"], 1, 2]

Expected: 4

Case 2

Input: [["1","0","0"],["0","0","0"],["0","0","1"], 0, 0]

Expected: 9

Case 3

Input: [["0","0","0"],["0","0","0"],["0","0","1"], 2, 2]

Expected: 1