Count Sub Islands LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Twitter
Array Depth First Search MatrixViews 2791

Problem Statement

Count Sub Islands LeetCode Solution says that grid1 and grid2 contain only 0‘s (representing water) and 1‘s (representing land). The island means the group of 1’s connected 4 directionally.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Example 1:

Count Sub Islands LeetCode SolutionInput:

 grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]

Output:

 3

Explanation: 

In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2:

Count Sub Islands LeetCode SolutionInput:

 grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]

Output:

 2

Explanation: 

In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

 

Constraints:

  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1 <= m, n <= 500
  • grid1[i][j] and grid2[i][j] are either 0 or 1.

Approach

Idea

1. Count Subislands, this problem can be solved through DFS on the grid.

2. We will run DFS on the second grid(grid2).

3. However, this time we also count land in matching cells in the first grid.

4. In the end, if a number of land cells match then the island in the second grid is a sub-island. We will increase our cnt variable.

Code

Count Sub Islands C++ Solution

class Solution {
public:
    #define ll int
    ll n,m;
    vector<vector<ll>>dirs={{1,0},{-1,0},{0,1},{0,-1}};
    void dfs(ll x,ll y,vector<vector<ll>>&vis,vector<vector<ll>>&g1,vector<vector<ll>>&g2,ll &ans)
    {
        vis[x][y]=1;
        ans&=g1[x][y];
        for(ll i=0;i<4;i++)
        {
            ll ind1=x+dirs[i][0];
            ll ind2=y+dirs[i][1];
            if(ind1<0 or ind2<0 or ind1>=n or ind2>=m)
                continue;
            if(g2[ind1][ind2]==0)
                continue;
            if(!vis[ind1][ind2])
                dfs(ind1,ind2,vis,g1,g2,ans);
                
        }
        
        
    }
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        n=grid1.size();
        m=grid1[0].size();
        vector<vector<ll>>vis(n,vector<ll>(m,0));
        ll i,j,cnt=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(grid2[i][j]==1 and !vis[i][j])
                {
                    ll ans=1;
                    dfs(i,j,vis,grid1,grid2,ans);
                    if(ans==1)
                    {cnt++;
                    }
                }
            }
        }
        return cnt;
    }
};

Count Sub Islands Java Solution

class Solution {
    int n,m;
    int[] dx={1,-1,0,0};
    int[] dy={0,0,1,-1};
    int ans=1;
    void dfs(int x,int y,int[][] vis,int[][] g1,int[][] g2)
    {
        vis[x][y]=1;
        ans*=g1[x][y];
        for(int i=0;i<4;i++)
        {
            int ind1=x+dx[i];
            int ind2=y+dy[i];
            if(ind1<0 || ind2<0 || ind1>=n || ind2>=m)
                continue;
            if(g2[ind1][ind2]==0)
                continue;
            if(vis[ind1][ind2]==0)
                dfs(ind1,ind2,vis,g1,g2);
                
       }
        
        
    }

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        n=grid1.length;
        m=grid1[0].length;
        int i,j,cnt=0;
        int[][] vis = new int[n][m];
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
                vis[i][j]=0;
        
         for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(grid2[i][j]==1 && vis[i][j]==0)
                {
                     ans=1;
                    dfs(i,j,vis,grid1,grid2);
                    if(ans==1)
                    {cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

Complexity Analysis of Count Sub Islands Leetcode Solution:

Time Complexity

The time complexity of the Count Sub Islands problem is O(N*M). Here, N*M is the dimension of the grid.

Space Complexity

Space complexity is O(N*M). We are keeping the extra visited array while running the DFS. Here, N*M is the dimension of the grid.

Translate »