Python O(mn) time by finding four indices


  • 0
    W

    Not very efficient algorithm since it does not use the provided index of a black pixel.
    We know the m X n matrix is a valid rectangle that encloses all black pixels. We pin the upper left and lower right four indices and keep updating until a row or column does contain a '1'. This defines the smallest rectangle.

    def minArea(self, image, x, y):
        leftx = lefty = 0
        rightx, righty = len(image) - 1, len(image[0]) - 1
        for i in range(len(image)):
            if '1' not in image[i]:
                leftx += 1
            else:
                break
        for j in range(len(image[0])):
            if '1' not in [image[a][j] for a in range(len(image))]:
                lefty += 1
            else:
                break
        for m in range(len(image)-1, -1,-1):
            if '1' not in image[m]:
                rightx -= 1
            else:
                break
        for n in range(len(image[0])-1,-1,-1):
            if '1' not in [image[b][n] for b in range(len(image)-1,-1,-1)]:
                righty -= 1
            else:
                break
        return (rightx-leftx+1) * (righty-lefty+1)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.