• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
const int m = image.size();
const int n = image[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
vector<int> topLeft{x, y};
vector<int> bottomRight{x, y};
queue<pair<int, int>> q{{{x, y}}};
image[x][y] = '2';  // visited

while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int r = i + dirs[k];
const int c = j + dirs[k + 1];
if (r < 0 || r == m || c < 0 || c == n)
continue;
if (image[r][c] != '1')
continue;
topLeft[0] = min(topLeft[0], r);
topLeft[1] = min(topLeft[1], c);
bottomRight[0] = max(bottomRight[0], r);
bottomRight[1] = max(bottomRight[1], c);
q.emplace(r, c);
image[r][c] = '2';
}
}

const int width = bottomRight[1] - topLeft[1] + 1;
const int height = bottomRight[0] - topLeft[0] + 1;
return width * height;
}
};
``````

## JAVA

``````class Solution {
public int minArea(char[][] image, int x, int y) {
final int m = image.length;
final int n = image[0].length;
final int[] dirs = {0, 1, 0, -1, 0};
int[] topLeft = {x, y};
int[] bottomRight = {x, y};
Queue<int[]> q = new ArrayDeque<>(Arrays.asList(new int[] {x, y}));
image[x][y] = '2'; // visited

while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int r = i + dirs[k];
final int c = j + dirs[k + 1];
if (r < 0 || r == m || c < 0 || c == n)
continue;
if (image[r][c] != '1')
continue;
topLeft[0] = Math.min(topLeft[0], r);
topLeft[1] = Math.min(topLeft[1], c);
bottomRight[0] = Math.max(bottomRight[0], r);
bottomRight[1] = Math.max(bottomRight[1], c);
q.offer(new int[] {r, c});
image[r][c] = '2';
}
}

final int width = bottomRight[1] - topLeft[1] + 1;
final int height = bottomRight[0] - topLeft[0] + 1;
return width * height;
}
}
``````

## Python

``````class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m = len(image)
n = len(image[0])
dirs = [0, 1, 0, -1, 0]
topLeft = [x, y]
bottomRight = [x, y]
q = deque([(x, y)])
image[x][y] = '2'  # visited

while q:
i, j = q.popleft()
for k in range(4):
r = i + dirs[k]
c = j + dirs[k + 1]
if r < 0 or r == m or c < 0 or c == n:
continue
if image[r][c] != '1':
continue
topLeft[0] = min(topLeft[0], r)
topLeft[1] = min(topLeft[1], c)
bottomRight[0] = max(bottomRight[0], r)
bottomRight[1] = max(bottomRight[1], c)
q.append((r, c))
image[r][c] = '2'

width = bottomRight[1] - topLeft[1] + 1
height = bottomRight[0] - topLeft[0] + 1
return width * height
``````
• Time:O(m\log n + n\log m)
• Space:O(1)

## C++

``````class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
const int x1 = firstAnyOne(image, 0, x, &rowAllZeros);
const int x2 = firstAllZeros(image, x + 1, image.size(), &rowAllZeros);
const int y1 = firstAnyOne(image, 0, y, &colAllZeros);
const int y2 = firstAllZeros(image, y + 1, image[0].size(), &colAllZeros);
return (x2 - x1) * (y2 - y1);
}

private:
int firstAnyOne(const vector<vector<char>>& image, int l, int r,
function<bool(const vector<vector<char>>&, int)> allZeros) {
while (l < r) {
const int m = (l + r) / 2;
if (allZeros(image, m))
l = m + 1;
else
r = m;
}
return l;
}

int firstAllZeros(const vector<vector<char>>& image, int l, int r,
function<bool(const vector<vector<char>>&, int)> allZeros) {
while (l < r) {
const int m = (l + r) / 2;
if (allZeros(image, m))
r = m;
else
l = m + 1;
}
return l;
}

static bool rowAllZeros(const vector<vector<char>>& image, int rowIndex) {
return all_of(cbegin(image[rowIndex]), cend(image[rowIndex]),
[](int pixel) { return pixel == '0'; });
}

static bool colAllZeros(const vector<vector<char>>& image, int colIndex) {
for (int i = 0; i < image.size(); ++i)
if (image[i][colIndex] == '1')
return false;
return true;
}
};
``````

## JAVA

``````class Solution {
public int minArea(char[][] image, int x, int y) {
this.image = image;
final int x1 = firstAnyOne(0, x, rowAllZeros);
final int x2 = firstAllZeros(x + 1, image.length, rowAllZeros);
final int y1 = firstAnyOne(0, y, colAllZeros);
final int y2 = firstAllZeros(y + 1, image[0].length, colAllZeros);
return (x2 - x1) * (y2 - y1);
}

private char[][] image;

private int firstAnyOne(int l, int r, Function<Integer, Boolean> allZeros) {
while (l < r) {
final int m = (l + r) / 2;
if (allZeros.apply(m))
l = m + 1;
else
r = m;
}
return l;
}

private int firstAllZeros(int l, int r, Function<Integer, Boolean> allZeros) {
while (l < r) {
final int m = (l + r) / 2;
if (allZeros.apply(m))
r = m;
else
l = m + 1;
}
return l;
}

Function<Integer, Boolean> rowAllZeros = new Function<>() {
public Boolean apply(Integer rowIndex) {
return new String(image[rowIndex]).chars().allMatch(pixel -> pixel == '0');
}
};

Function<Integer, Boolean> colAllZeros = new Function<>() {
public Boolean apply(Integer colIndex) {
for (int i = 0; i < image.length; ++i)
if (image[i][colIndex] == '1')
return false;
return true;
}
};
}
``````

## Python

``````class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
def firstAnyOne(l: int, r: int, allZeros: Callable[[int], bool]) -> int:
while l < r:
m = (l + r) // 2
if allZeros(m):
l = m + 1
else:
r = m
return l

def firstAllZeros(l: int, r: int, allZeros: Callable[[int], bool]) -> int:
while l < r:
m = (l + r) // 2
if allZeros(m):
r = m
else:
l = m + 1
return l

def colAllZeros(colIndex: int) -> bool:
return all(pixel == '0' for pixel in list(zip(*image))[colIndex])

def rowAllZeros(rowIndex: int) -> bool:
return all(pixel == '0' for pixel in image[rowIndex])

x1 = firstAnyOne(0, x, rowAllZeros)
x2 = firstAllZeros(x + 1, len(image), rowAllZeros)
y1 = firstAnyOne(0, y, colAllZeros)
y2 = firstAllZeros(y + 1, len(image[0]), colAllZeros)
return (x2 - x1) * (y2 - y1)
``````