Is LeetCode 302. Smallest Rectangle Enclosing Black Pixels a premium problem?

Yes. LeetCode 302. Smallest Rectangle Enclosing Black Pixels is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Smallest Rectangle Enclosing Black Pixels — LeetCode 302 Python Solution

HardLeetCode PremiumDepth-First SearchBreadth-First SearchArrayBinary SearchMatrix

Problem: #302
Pattern: Matrix and Grid
Reading time: 8 min
Source: leetcode.com

The 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).

Example

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

Python solution

Python

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        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:
                right = mid
            else:
                left = mid + 1
        u = left
        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:
                left = mid
            else:
                right = mid - 1
        d = left
        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:
                right = mid
            else:
                left = mid + 1
        l = left
        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:
                left = mid
            else:
                right = mid - 1
        r = left
        return (d - u + 1) * (r - l + 1)

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(1) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 302. Smallest Rectangle Enclosing Black Pixels is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 302. Smallest Rectangle Enclosing Black Pixels?: LeetCode 302. Smallest Rectangle Enclosing Black Pixels is rated Hard on LeetCode.
What topics does LeetCode 302. Smallest Rectangle Enclosing Black Pixels cover?: LeetCode 302. Smallest Rectangle Enclosing Black Pixels is tagged Depth-First Search, Breadth-First Search, Array, Binary Search and Matrix on LeetCode.
Is LeetCode 302. Smallest Rectangle Enclosing Black Pixels a premium problem?: Yes. LeetCode 302. Smallest Rectangle Enclosing Black Pixels is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.