DFS, BFS, binary search and brute force interation.


  • 2
    B

    I will show four algorithms and corresponding complexity;

    • DFS : roughly 4k * n^2, k means the factor of num of '1' cell versus image size; This algorithm performs well while k << log2(N) / N;
    • BFS : same as DFS
    • Binary Search: search for the bounding row and col which has '1', which performs well while many cells are filled with '1'
    • brute force: just iterate all of the cells and calc the min_x, min_y, max_x, max_y;

    DFS

    class Solution {
        vector<pair<int, int>> dirs;
    public:
        Solution(){
            dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        }
        int minArea(vector<vector<char>>& image, int x, int y) {
            image[x][y] = '2';
            fill_to_boundary(image, x, y);
            
            int xdim, ydim;
            xdim = ydim = 0;
            
            for(int i = 0; i <= image.size() - 1; ++i){
                if (image[i][y] == '2'){
                    ++xdim;
                }
            }
            for(int i = 0; i <= image[0].size() - 1; ++i){
                if (image[x][i] == '2'){
                    ++ydim;
                }
            }
            return  xdim * ydim;
        }
    
        void fill_to_boundary(vector<vector<char>>& image, int x, int y){
            for(int i = 0; i < dirs.size(); ++i){
                int row = x + dirs[i].first;
                int col = y + dirs[i].second;
                if (row >=0 && row <= image.size() - 1 && col >= 0 && col <= image[0].size() - 1 && need_change(image, row, col)){
                    image[row][col] = '2';
                    fill_to_boundary(image, row, col);
                }
            }
        }
        bool need_change(vector<vector<char>>& image, int x, int y){
            if (image[x][y] == '1') return true;
            if (image[x][y] == '2') return false;
            int count = 0;
            for(int i = 0; i < dirs.size(); ++i){
                int row = x + dirs[i].first;
                int col = y + dirs[i].second;
                if (row >=0 && row <= image.size() - 1 && col >= 0 && col <= image[0].size() - 1 && (image[row][col] == '1' || image[row][col] == '2')){
                    ++ count;
                }
            }
            if (count > 1){
                return true;
            } else {
                return false;
            }
        }
    };
    

    Brute Force

    class Solution {
    public:
        int minArea(vector<vector<char>>& image, int x, int y) {
            int x_min = INT_MAX, y_min = INT_MAX, x_max = INT_MIN, y_max = INT_MIN;
            for(int i = 0; i < image.size(); ++i){
                for(int j = 0; j < image[0].size(); ++j){
                    if (image[i][j] == '1'){
                        x_min = min(x_min, i);
                        y_min = min(y_min, j);
                        x_max = max(x_max, i);
                        y_max = max(y_max, j);
                    }
                }
            }
            return (x_max - x_min + 1) * (y_max - y_min + 1);
        }
    };
    

    Binary Search:

    Maybe you can refer to https://leetcode.com/discuss/68246/c-java-python-binary-search-solution-with-explanation


Log in to reply
 

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