Leetcode (695) - the largest area of an island

Leetcode（695）—— The largest area of the island

subject

Give you a size of $m\times n$ The binary matrix of grid .

Islands It's made up of some neighboring 1 ( Representing land ) A combination of components , there 「 adjacent 」 Ask for two 1 Must be in In four horizontal or vertical directions adjacent . You can assume grid The four edges of are all 0（ Representative water ） Surrounded by a .

The area of the island is the value of 1 Number of cells .

Calculate and return grid The largest island area in . If there were no Islands , Then the return area is 0 .

Example 1：

Input ：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output ：6
explain ： The answer should not be 11 , Because the island can only contain horizontal or vertical 1 .

Example 2：

Input ：grid = [[0,0,0,0,0,0,0,0]]
Output ：0

Tips ：

• m == grid.length
• n == grid[i].length
• $1$ <= m, n <= $50$
• grid[i][j] by $0$ or $1$

Answer key

Method 1 ：DFS（ Recursive writing ）

Ideas

• We want to know the area of each connected shape in the grid , And then take the maximum .
• If we are on a land , With $4$ Explore every land connected with it in two directions （ And the land connected to these lands ）, Then the total amount of land explored will be the area of the connected shape .
• To ensure that no more than one visit is made to each land , Every time we pass a piece of land , Set the value of this land to $0$. So we won't visit the same land many times .

​​   Here we use a trick , For traversal in four directions , You can create an array [-1, 0, 1, 0, -1], Every two adjacent digits is one of the four directions up, down, left and right .

​​   In the auxiliary function , One important thing to note is that recursive search in auxiliary functions , Determination of boundary conditions . There are generally two ways to write boundary determination , One is to determine whether it crosses the boundary first , Only if it is legal, can we carry out the next search （ That is, the judgment is placed before calling the recursive function ）; The other is to search for the next step regardless of three, seven and twenty-one , Judge whether it is legal when the next search starts （ That is, the judgment is placed on the first line of the auxiliary function ）. Here we show these two ways .

Code implementation

Leetcode Official explanation ：

class Solution {
    
    int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
    
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
    
            return 0;
        }
        grid[cur_i][cur_j] = 0;
        int di[4] = {
    0, 0, 1, -1};
        int dj[4] = {
    1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
    
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        return ans;
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
    
            for (int j = 0; j != grid[0].size(); ++j) {
    
                ans = max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }
};

My own ：

class Solution {
    
    void DFS(vector<vector<int>>& grid, int x, int y, int& area){
    
        if(0 > x || x >= grid[0].size() || y >= grid.size() || 0 > y) return;
        if(grid[y][x] == 1){
    
            //  The up and down or so 
            area += 1;
            grid[y][x] = 0; //  Set as 0 Prevent revisiting this point 
            DFS(grid, x-1, y, area);
            DFS(grid, x+1, y, area);
            DFS(grid, x, y-1, area);
            DFS(grid, x, y+1, area);
        }
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
        int ans = 0, area, yn = grid.size(), xn = grid[0].size();
        for(int y = 0; y < yn; y++){
    
            for(int x = 0; x < xn; x++){
    
                if(grid[y][x] == 1){
    
                    area = 0;
                    DFS(grid, x, y, area);
                    ans = ans < area? area: ans;
                }
            }
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(m\times n)$. among $m$ Is the number of rows in a given grid ,$n$ It's the number of columns . We visited each originally 1 At most once .
Spatial complexity ：$O(m\times n)$, The depth of recursion is most likely the size of the entire grid , Therefore, it is possible to use $O(m\times n)$ Stack space of .

Method 2 ：DFS + Auxiliary stack （ Iterative writing ）

Ideas

​​   The principle is the same as method 1 , Only the implementation adopts iteration rather than recursion , And use the stack to help realize .

• Method 1 indicates which land you want to traverse next by calling a function , Let the next function access these lands . And method 2 puts the land you want to traverse next in the stack , Then visit these lands when taking them out .
• When visiting every piece of land , We will explore four directions around it , Find land that has not been visited , Add to stack $\text{stack}$ in ;
• in addition , Just stack $\text{stack}$ Not empty , It means we still have land to visit , Then take an element from the stack and access .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
    
            for (int j = 0; j != grid[0].size(); ++j) {
    
                int cur = 0;
                stack<int> stacki;
                stack<int> stackj;
                stacki.push(i);
                stackj.push(j);
                while (!stacki.empty()) {
    
                    int cur_i = stacki.top(), cur_j = stackj.top();
                    stacki.pop();
                    stackj.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
    
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {
    0, 0, 1, -1};
                    int dj[4] = {
    1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
    
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        stacki.push(next_i);
                        stackj.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

My own ：

class Solution {
    
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
        int ans = 0, area, yn = grid.size(), xn = grid[0].size();
        stack<pair<int, int>> island;
        pair<int, int> tmp;
        for(int y = 0; y < yn; y++){
    
            for(int x = 0; x < xn; x++){
    
                if(grid[y][x] == 1){
    
                    area = 0;
                    island.push(make_pair(y, x));
                    while(!island.empty()){
    
                        tmp.first = island.top().first;
                        tmp.second = island.top().second;
                        island.pop();
                        if(grid[tmp.first][tmp.second] != 1) continue;
                        grid[tmp.first][tmp.second] = 0;
                        area++;
                        if(tmp.second-1 >= 0) island.push(make_pair(tmp.first, tmp.second-1));
                        if(tmp.second+1 < xn) island.push(make_pair(tmp.first, tmp.second+1));
                        if(tmp.first-1 >= 0) island.push(make_pair(tmp.first-1, tmp.second));
                        if(tmp.first+1 < yn) island.push(make_pair(tmp.first+1, tmp.second));
                    }
                    ans = max(area, ans);
                }
            }
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(m\times n)$. among $m$ Is the number of rows in a given grid ,$n$ It's the number of columns . We visited each originally 1 At most once .
Spatial complexity ：$O(m\times n)$, The stack can store up to all the land , The maximum amount of land is $m\times n$ block , Therefore, the space used is $O(m\times n)$.

Method 3 ：BFS + queue

Ideas

​​   Change the stack in method 2 to queue , Take out the land from the head of the team every time , And put the land you want to traverse next at the end of the team , To achieve the breadth first search algorithm .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
    
            for (int j = 0; j != grid[0].size(); ++j) {
    
                int cur = 0;
                queue<int> queuei;
                queue<int> queuej;
                queuei.push(i);
                queuej.push(j);
                while (!queuei.empty()) {
    
                    int cur_i = queuei.front(), cur_j = queuej.front();
                    queuei.pop();
                    queuej.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1)
                        continue;
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {
    0, 0, 1, -1};
                    int dj[4] = {
    1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
    
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        queuei.push(next_i);
                        queuej.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

My own ：

class Solution {
    
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
    
        int ans = 0, area, yn = grid.size(), xn = grid[0].size();
        queue<pair<int, int>> island;
        pair<int, int> tmp;
        for(int y = 0; y < yn; y++){
    
            for(int x = 0; x < xn; x++){
    
                if(grid[y][x] == 1){
    
                    area = 0;
                    island.push(make_pair(y, x));
                    while(!island.empty()){
    
                        tmp.first = island.front().first;
                        tmp.second = island.front().second;
                        island.pop();
                        if(grid[tmp.first][tmp.second] != 1) continue;
                        grid[tmp.first][tmp.second] = 0;
                        area++;
                        if(tmp.second-1 >= 0) island.push(make_pair(tmp.first, tmp.second-1));
                        if(tmp.second+1 < xn) island.push(make_pair(tmp.first, tmp.second+1));
                        if(tmp.first-1 >= 0) island.push(make_pair(tmp.first-1, tmp.second));
                        if(tmp.first+1 < yn) island.push(make_pair(tmp.first+1, tmp.second));
                    }
                    ans = max(area, ans);
                }
            }
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(m\times n)$. among $m$ Is the number of rows in a given grid ,$n$ It's the number of columns . We visited each originally 1 At most once .
Spatial complexity ：$O(m\times n)$, At most all the land will be stored in the queue , The maximum amount of land is $m\times n$ block , Therefore, the space used is $O(m\times n)$.