# Two clean C++ solutions BFS and Binary Search

• BFS O(mn), not modifying image, 235ms

``````class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
if(!image.size() || !image[0].size()) return 0;
queue<pair<int,int>> Q;
set<pair<int, int>> visited;
int l = x, u = y, d = y, r = x, m = image.size(), n = image[0].size();
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

Q.push(make_pair(x, y));
visited.insert(Q.front());

while(!Q.empty()){
auto cur = Q.front();
Q.pop();
l = min(cur.first, l);
r = max(cur.first, r);
u = min(cur.second, u);
d = max(cur.second, d);

for(auto dir: dirs){
int xx = cur.first + dir.first;
int yy = cur.second + dir.second;
if(xx >= 0 && xx < m && yy >= 0 && yy < n && image[xx][yy] == '1'){
pair<int, int> pixel = make_pair(xx, yy);
if(visited.find(pixel) == visited.end()){
Q.push(pixel);
visited.insert(pixel);
}
}
}
}

return (d - u + 1) * (r - l + 1);
}
};
``````

Modified BFS by modifying image, 40ms, so 'visited' is not needed

``````class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
if(!image.size() || !image[0].size()) return 0;
queue<pair<int,int>> Q;
int l = x, u = y, d = y, r = x, m = image.size(), n = image[0].size();
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

Q.push(make_pair(x, y));
image[x][y] = '0';

while(!Q.empty()){
auto cur = Q.front();
Q.pop();

l = min(cur.first, l);
r = max(cur.first, r);
u = min(cur.second, u);
d = max(cur.second, d);

for(auto dir: dirs){
int xx = cur.first + dir.first;
int yy = cur.second + dir.second;

if(xx >= 0 && xx < m && yy >= 0 && yy < n && image[xx][yy] == '1'){
pair<int, int> pixel = make_pair(xx, yy);
Q.push(pixel);
image[xx][yy] = '0';
}
}
}

return (d - u + 1) * (r - l + 1);
}
};
``````

Binary Search, O(mlgn + nlgm), 20ms, inspired by dietpepsi's post, and yavinci's post

``````class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
if(!image.size() || !image[0].size()) return 0;
int m = (int)image.size(), n = (int)image[0].size();
int l = search(0, y, 0, m, image, true, '1');
int r = search(y + 1, n, 0, m, image, true, '0');
int u = search(0, x, l, r, image, false, '1');
int d = search(x + 1, m, l, r, image, false, '0');

return (r - l) * (d - u);
}

int search(int start, int end, int top, int bottom, vector<vector<char>>& image, bool hori, char target){
while(start < end){
int mid = start + (end - start) / 2, _top = top;
char found = '0'; // if find any ‘1’ in search range [top, bottom), found = ‘1’
while(_top < bottom){
if((hori ? image[_top++][mid] : image[mid][_top++]) == '1') {
found = '1';
break;
}
}
target == found ? end = mid : start = mid + 1;
}

return start;
}
};
``````

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