Two clean C++ solutions BFS and Binary Search


  • 0

    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;
        }
    };
    

Log in to reply
 

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