Smallest Rectangle Enclosing Black Pixels

Problem: Smallest Rectangle Enclosing Black Pixe

Actually my solution is a silly depth-first search solution. We start search from the passed-in position to find its neighbors and update our left, right, up and down boundary.

Code in Python:

class Solution(object):
    def minArea(self, image, x, y):
        """
        :type image: List[List[str]]
        :type x: int
        :type y: int
        :rtype: int
        """
        self.l = self.r = y
        self.u = self.d = x
        def dfs(i, j):
            image[i][j] = "0"
            self.l, self.r = min(self.l, j), max(self.r, j)
            self.u, self.d = min(self.u, i), max(self.d, i)
            if i > 0 and image[i-1][j] == "1": dfs(i-1, j)
            if j > 0 and image[i][j-1] == "1": dfs(i, j-1)
            if i < len(image)-1 and image[i+1][j] == "1": dfs(i+1, j)
            if j < len(image[0])-1 and image[i][j+1] == "1": dfs(i, j+1)
        dfs(x, y)
        return (self.r-self.l+1)*(self.d-self.u+1)

Here's a real binary search solution, which do binary search for four boundaries from the position passed in.