{"id":2021,"date":"2020-07-01T09:51:08","date_gmt":"2020-07-01T09:51:08","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2021"},"modified":"2022-03-22T08:57:52","modified_gmt":"2022-03-22T08:57:52","slug":"number-of-islands","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/number-of-islands\/","title":{"rendered":"Number of islands"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Depth First Search, Disjoint Set<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a 2D matrix, which contains only two numbers 0 or 1. In the map group of connected 0 represents, the water and group of connected 1 represent the island. Find the number of islands.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

A group of connected 1’s represents an island.
\nIdea is to consider the 1’s and look for their neightbours if they form a component together it will be counted as 1 island.<\/p>\n

This problem can be solved by many ways like Breadth First Search<\/strong>, Depth First Search<\/strong> or Disjoint Set<\/strong>. Below we are going to discuss two of the above mentioned methods to solve this problem.<\/p>\n<\/blockquote>\n

EXAMPLE:<\/h4>\n

\"\"<\/p>\n

Method 1 (Using DFS) :<\/h4>\n
\n

In this method we are going to use Depth First Search<\/strong> or DFS<\/strong> to find total number of connected components. In dfs()<\/strong>, we are going to traverse all the adjacent vertices(cells) which are not yet visited and mark them as visited so we won’t traverse them again. Once we encounter a cell which has value 1<\/code>, then we will look for all its neighbour cells for the 1's<\/code> by calling dfs()<\/strong> and count them as a single component, then increment count by 1<\/code>.
\nWe can keep track if the node is visited or not, using a boolean visited[ ]<\/strong> array of size n<\/code> which is initially set false (why ?<\/code>).<\/p>\n

Now the question arise, why are we counting the different calls made to dfs()<\/strong> ?<\/code> The answer lies in the fact that each time we call our dfs() function with some vertex v<\/code>, it marks all vertices(cells) which are connected to v<\/code> as visited, which means the we are visiting the vertices which are directly or indirectly connected to the v<\/code> and has value 1<\/code>. This is considered as one island. So each call made up to dfs() with some unvisited vertex v<\/code>, gives us the different connected islands. <\/p>\n<\/blockquote>\n

Method 2 (Using Disjoint Set) :<\/h4>\n
\n

Disjoint Set Union<\/strong> or DSU<\/strong> data structure is also sometimes called Union-Find Set<\/strong>. This data structure is used to keep track of the different disjoint sets.
\nIt basically performs two operations :<\/p>\n

    \n
  1. Union :<\/strong> It takes two vertices and join them in a single set (if it is not already there).<\/li>\n
  2. Find :<\/strong> Determines in which subset the element is.<\/li>\n<\/ol>\n

    We will use a parent[]<\/code> array to keep track of the parents of each vertex. ith<\/code> element will store the root\/parent of ith<\/code> vertex. Now, iterate through each cell or vertex of the matrix, if any cell has 1<\/code> then we will look for its neighbours if it has a value 1<\/code>. If we find any such neighbour we will perform union()<\/strong> for the cell and its neighbour (both having 1<\/code>) and update the parent[]<\/code> array.
    \nNow, iterate each value of the matrix again, this time if we will find 1<\/code>, we will look for its root (or its set).
    \nNow, iterate for all elements of matrix again, for each vertex\/cell c<\/code>, we will find root of c<\/code> using find()<\/strong> and keep track of all distinct roots. Every time we encounter a distinct root increment the counter by 1<\/code>.<\/p>\n

    Each disjoint set stores the vertices which are connected (directly or indirectly) to each other and has no relation\/connection with any other vertex (as it is non overlapping set), which means each set itself represents a connected islands and since each set contains exactly one vertex as its root, the sum of distinct roots of all sets gives us the total number of connected islands.<\/p>\n<\/blockquote>\n

    Algorithms :<\/h3>\n
    \n

    dfs()<\/strong> :<\/h3>\n
      \n
    1. For each call, for some vertex v<\/code> ( dfs(v<\/code>) ), we will mark the vertex v<\/code> as visited (visited[v]= true<\/code>).<\/li>\n
    2. Iterate for all the adjacent vertices of v<\/code> and for every adjacent vertex a<\/code>, do following :\n
        \n
      • if a<\/code> is not visited i.e visited[a]= false<\/code>,
        \nand if a<\/code> has value 1<\/code>. <\/li>\n
      • recursively call dfs (a<\/code>)<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

        union()<\/strong> :<\/h3>\n
          \n
        1. For two vertices u<\/code> & v<\/code>, find the root for both vertices using find()<\/strong> (a=find(u)<\/code> & b = find(v)<\/code>).<\/li>\n
        2. If the root of u<\/code> & v<\/code> are not similar, check the level of a<\/code> & b<\/code> as follows:\n
            \n
          • if (level[a]>* else if (<\/code>level[a]>level[b]), update <\/code>parent[b] = a`.<\/li>\n
          • else , update parent[b]=a<\/code> & update level[a] = level[a]+1<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

            find()<\/strong> :<\/h3>\n
              \n
            1. If (parent[v]==v)<\/code>, returns the vertex v<\/code> (which is root).<\/li>\n
            2. Else, update parent[v]<\/code> by recursively looking up the tree for the root. (find(parent[v]))<\/code>.<\/li>\n<\/ol>\n<\/blockquote>\n

              Complexity Analysis:<\/h3>\n
              \n

              The time complexity<\/strong> of the first method is represented in the form of O(R*C)<\/code>, where R<\/code> is the number of rows and c<\/code> is the number of columns.<\/p>\n

              Talking about method 2 using Union-Find<\/strong> data structure, since we have used path compression & union by rank (refer to Disjoint Set<\/strong> article for more detailed explanation), we will reach nearly constant time O(1)<\/code> for each query. But we are traversing the matrix which gives us the time complexity O(R*C)<\/code> for this method as well.<\/p>\n<\/blockquote>\n

              Solutions:<\/h3>\n

              \t\t\t\t\t\t