# O(nOfBlackPixels) time, best BFS solution in Python with detailed explanation

• ``````class Solution(object):
def minArea(self, image, x, y):
"""
:type image: List[List[str]]
:type x: int
:type y: int
:rtype: int
"""
top, left = float("inf"), float("inf")
bot, right = -1, -1

image[x][y] = None
q = collections.deque([(x, y)])
while q:
x, y = q.pop()
top, left = min(x, top), min(y, left)
bot, right = max(x, bot), max(y, right)
for x0, y0 in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
if 0 <= x0 < len(image) and 0 <= y0 < len(image[0]) and image[x0][y0] == "1":
image[x0][y0] = None
q.appendleft((x0, y0))
return (right - left + 1) * (bot - top + 1)
``````

Many people will have the question: whey do we need x and y here ?
The reason is, instead of O(mn) time, where the image can be very big, we only need O(nOfPixel) Time if we have x ,y, we do BFS and found the topLeft corner and botRight corner of this rectangle, top is the smallest x value ever observed in BFS, left is the smalles y value, similar for bot and right.
Then, we got our rectangle after one BFS, wow, is this amazing :)

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