C++ DFS/Floodfill (Easy to understand with explanation)


  • 0
    H

    [DISCLAIMER]: The worst case complexity of this solution is O(n^2) time and O(n+m) system stack (recursion). Binary search based solution has lesser complexity, but this solution is very easy to understand and simple.

    The problem is to find the leftmost, rightmost, topmost & bottommost 1. Once we have their position we can calculate the area of rectangle very easily. So intuitively start from (x, y) given in the problem and fill the matrix of 1's (given that all 1's occur together). While filling, maintain 4 variables left, right, top, bottom and update their values. At the end, we calculate the area of rectangle as (right-left+1) * (bottom-top+1). One thing to note is that, we don't need extra space to store previously visited information. We can change the given matrix to '2' whenever we visit a '1'. This way we can reconstruct the original matrix at the end by replacing all '2's with '1's if necessary. The code is as follows,

    class Solution {
    public:
        int n, m;
        bool isSafe(int x, int y){
            return x >= 0 && x < n && y >= 0 && y < m;
        }
        void fill(vector<vector<char>>& image, int x, int y, int& left, int& right, int& top, int& bottom){
            image[x][y] = '2';
            left = min(left, x);
            right = max(right, x);
            top = min(top, y);
            bottom = max(bottom, y);
            if(isSafe(x-1, y) && image[x-1][y] == '1') fill(image, x-1, y, left, right, top, bottom);
            if(isSafe(x, y-1) && image[x][y-1] == '1') fill(image, x, y-1, left, right, top, bottom);
            if(isSafe(x+1, y) && image[x+1][y] == '1') fill(image, x+1, y, left, right, top, bottom);
            if(isSafe(x, y+1) && image[x][y+1] == '1') fill(image, x, y+1, left, right, top, bottom);
        }
        int minArea(vector<vector<char>>& image, int x, int y) {
            n = image.size();
            if(n == 0) return 0;
            m = image[0].size();
            if(m == 0) return 0;
            int left = x;
            int right = x;
            int top = y;
            int bottom = y;
            fill(image, x, y, left, right, top, bottom);
            return (right-left+1)*(bottom-top+1);
        }
    };
    

Log in to reply
 

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