Max Area of Island – LeetCode Solution [Medium]

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 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
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

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

Constraints:

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

Approach:

This question could be solved easily by BFS (Breadth-first search).

We iteratively visit every cell in grid and on visiting a cell, we mark it as visited. So that, we do not count a cell twice. While iterating the grid, we keep updating a variable (ans) to store the largest area, yet discovered.

class Solution {
public:

    //We apply BFS on given grid
    void solve (vector<vector<int>>& grid,
    vector<vector<int>>& vis, 
    queue<vector<int>>& qu, 
    int& ans, const int n, const int m) {
           int x = 0;
           while (!qu.empty()) {
            vector<int> cell = qu.front();
            qu.pop();

            //Checking left cell
            if (cell[1]-1>=0 && 
                vis[cell[1]-1][cell[2]] == 0 && 
                grid[cell[1]-1][cell[2]] == 1) {
                   vis[cell[1]-1][cell[2]] = 1;
                   x = grid[cell[1]-1][cell[2]] == 
                     1 ? (cell[0]+1) : 0;
                   ans++;
                   qu.push(vector<int> {x, 
                     cell[1]-1, cell[2]});
            }

            //Checking top cell
            if (cell[2]-1>=0 && 
                vis[cell[1]][cell[2]-1] == 0 &&
                grid[cell[1]][cell[2]-1] == 1) {
                   vis[cell[1]][cell[2]-1] = 1;
                   x = grid[cell[1]][cell[2]-1] == 
                     1 ? (cell[0]+1) : 0;
                   ans++;
                   qu.push(vector<int> {x, 
                     cell[1], cell[2]-1});
            }

            //Checking right cell
            if (cell[1]+1<n && 
                vis[cell[1]+1][cell[2]] == 0 &&
                grid[cell[1]+1][cell[2]] == 1) {
                     vis[cell[1]+1][cell[2]] = 1;
                     x = grid[cell[1]+1][cell[2]] == 
                     1 ? (cell[0]+1) : 0;
                     ans++;
                     qu.push(vector<int> {x, 
                       cell[1]+1, cell[2]});
            }

            //Checking bottom cell
            if (cell[2]+1<m && 
                vis[cell[1]][cell[2]+1] == 0 
                && grid[cell[1]][cell[2]+1] == 1) {
                  vis[cell[1]][cell[2]+1] = 1;
                  x = grid[cell[1]][cell[2]+1] == 
                    1 ? (cell[0]+1) : 0;
                  ans++;
                  qu.push(vector<int> {x, 
                    cell[1], cell[2]+1});  
            }
        }
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        queue<vector<int>> qu;
        int ans = 0, sol = 0;
        const int n = grid.size(), m = grid[0].size();
        
        //Base case
        if (n == 0 || m == 0) {
            return 0;
        }

        //Setting visited vector to 0 (no cell visited)
        vector<vector<int>> vis;
        for (int i=0; i<n; i++) {
            vis.push_back(vector<int> {});
            for (int j=0; j<m; j++) {
                vis[i].push_back(0);
            }
        }

        //BFS utility loop
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (vis[i][j] == 0 && grid[i][j] == 1){
                    vector<int> cell;

                    //marking cell as visited
                    cell.push_back(1);
                    
                    //saving cell indices
                    cell.push_back(i);
                    cell.push_back(j);
                    qu.push(cell);
                    vis[i][j] = 1;
                    ans = 1;
                    solve (grid, vis, qu, ans, n, m);
                    sol = max(sol, ans);
                }
            }
        }
        return sol;
    }
};

Leave a Reply

Your email address will not be published.