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


  • 0

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

Log in to reply
 

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