C++ 9-15 lines solutions for 19ms binary search and 36ms DFS

• 19ms binary search, run time is O(max(mlogn, nlogm)):

``````class Solution {
private:
// binary search for boundaries: [u, d) and [l, r)
int search(vector<vector<char>>& image, int lower, int upper, bool scanY, bool target) {
int scanBound = scanY ? image[0].size() : image.size();     // decide scan boundary based on scanning x/y
while (lower < upper) {                                     // binary search
int mid = lower + (upper - lower) / 2;
bool found = false;                                     // found '1' or not

for (int i = 0; i < scanBound && !found; i++)           // scanning for '1'
if (scanY ? image[mid][i] == '1' : image[i][mid] == '1') { found = true; }

if (found == target) { lower = mid + 1; }
else                 { upper = mid; }
}
return lower;
}

public:
int minArea(vector<vector<char>>& image, int x, int y) {
// Boundaries: [up, down)
int u = search(image, 0, x, true, false), d = search(image, x, image.size(), true, true);
// Boundaries: [left, right)
int l = search(image, 0, y, false, false), r = search(image, y, image[0].size(), false, true);
// calculate area
return (d - u) * (r - l);
}
};
``````

36ms DFS, run time is O(m*n):

``````class Solution {
private:
// up, right, down, left for boundaries and directions
int u = INT_MAX, r = INT_MIN, d = INT_MIN, l = INT_MAX, dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

// DFS for boundaries
void search(vector<vector<char>>& image, int x, int y, const int& m, const int& n) {
if (x < 0 || x == m || y < 0 || y == n || image[x][y] != '1') { return; }
image[x][y] = '2';                                          // mark as visited
u = min(u, x), d = max(d, x), l = min(l, y), r = max(r, y); // update boundaries
for (auto d : dirs) { search(image, x + d[0], y + d[1], m, n); }
}

public:
int minArea(vector<vector<char>>& image, int x, int y) {
search(image, x, y, image.size(), image[0].size());
return (d - u + 1) * (r - l + 1);
}
};
``````

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