Problem statement

https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/

Solution

One idea is just to traverse our array with dfs or bfs and calculate bounds, it $O(mn)$ time and space. However we can do better! Let us try to find the most left $1$ we can have and we can do it using binary search. The same for the most right, top and bottom elements. We use the same idea of binary search several times, so let us wrap it inside function which will return [beg, end] pair. I need to return pair, because sometimes I need beg and sometimes I need end. There is a way to write it down with just one output, but it is what I did.

Complexity

Time complexity is $O(m\log n + n\log m)$ to perform all $4$ binary searches. Space complexity is $O(m + n)$.

Code

class Solution:
    def minArea(self, image, x, y):
        m, n = len(image), len(image[0])
        def bs(beg, end, func):
            while beg + 1 < end:
                mid = (beg + end) // 2
                if func(mid):
                    end = mid
                else:
                    beg = mid
            return [beg, end]
        
        top = bs(-1, x, lambda x: "1" in image[x])[1]
        bot = bs(x,  m, lambda x: "1" not in image[x])[0]
        rgh = bs(y,  n, lambda y: all(row[y] == "0" for row in image))[0]
        lft = bs(-1, y, lambda y: any(row[y] == "1" for row in image))[1]
        
        return (bot - top + 1)*(rgh - lft + 1)