LeetCode: 302. Smallest Rectangle Enclosing Black Pixels

Perhaps, the most thinkable solution would be DFS or BFS.

Traverse all the '1' points and update mins and maxs.

Time complexity would be O(M*N) in this case.

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        ymin, ymax, xmin, xmax = m, -1, n, -1
        dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
        stack, visited = [(x, y)], set()
        while stack:
            i, j = stack.pop()
            ymin, ymax, xmin, xmax = \
            min(ymin, i), max(ymax, i), min(xmin, j), max(xmax, j)
            visited.add((i, j))
            for d in range(4):
                next_y, next_x = i + dy[d], j + dx[d]
                if 0 <= next_y < m and 0 <= next_x < n and \
                image[next_y][next_x] == '1' and (next_y, next_x) not in visited:
                    stack.append((next_y, next_x))
        return (ymax - ymin + 1) * (xmax - xmin + 1)

 

There's a more efficient way to solve this problem, however. We can binary-search mins and maxs of each coordinate. Time complexity would be O(N*logM).

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        y, x = x, y
        # search ymin
        ymin = y
        l, r = 0, y
        while l <= r:
            mid = (l + r) // 2
            if '1' in image[mid]:
                ymin = min(ymin, mid)
                r = mid - 1
            else:
                l = mid + 1
        # search ymax
        ymax = y
        l, r = y, m - 1
        while l <= r:
            mid = (l + r) // 2
            if '1' in image[mid]:
                ymax = max(ymax, mid)
                l = mid + 1
            else:
                r = mid - 1
        # search xmin
        xmin = x
        l, r = 0, x
        while l <= r:
            mid = (l + r) // 2
            if '1' in [image[i][mid] for i in range(m)]:
                xmin = min(xmin, mid)
                r = mid - 1
            else:
                l = mid + 1
        # search xmax
        xmax = x
        l, r = x, n - 1
        while l <= r:
            mid = (l + r) // 2
            if '1' in [image[i][mid] for i in range(m)]:
                xmax = max(xmax, mid)
                l = mid + 1
            else:
                r = mid - 1
        return (ymax - ymin + 1) * (xmax - xmin + 1)