Find the number of Islands

This is a very common question asked in the interviews with various modifications such as:

1. Island is considered a single if any vertical OR horizontal is 1.(either of 4 directions vertical and horizontal)

1 1 0 0
0 0 1 0
0 0 0 1
0 1 0 0

Number of Islands are: 4

2. Island is considered a single if any among all the directions is 1.(either of 8 directions)

1 1 0 0
0 0 1 0
0 0 0 1
0 1 0 0

Number of Islands are: 2

Solution Part:

There are 2 techniques for solving this:

1. Using the constant space, we will put 0 in the same Array or ArrayList we are iteration if we already visited that index.
2. Using a Boolean matrix of the same size, where we will put true if we visited that index.

Let’s write code for the same:

Code 1: Constant space and either of 4 directions vertical and horizontal.

Code 2: Constant space and either of 8 directions.

Code 3: Boolean matrix of the same size and either of 4 directions vertical and horizontal.

Code 4: Boolean matrix of the same size and either of 8 directions.

//Code 1
class Islands {
// Function to find the number of island in the given list A
// N, M: size of list row and column respectively
  public static int findIslands(ArrayList<ArrayList<Integer>> A, int N, int M) {
        if(A==null  || A.isEmpty())
        return 0;
        int count=0;
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.get(i).size();j++){
                if(A.get(i).get(j)==1){
                    dfs(A,i,j);
                    count++;
                }
                
            }
        }
        return count;
    }
  public static void dfs(ArrayList<ArrayList<Integer>> A,int i,int j){
        if(i<0||j<0||i>=A.size()||j>=A.get(i).size()||A.get(i).get(j)==0)
            return;
        A.get(i).set(j,0);
        dfs(A,i-1,j);
        dfs(A,i,j-1);
        dfs(A,i+1,j);
        dfs(A,i,j+1);
    }
}

//Code 2
class Islands {
// Function to find the number of island in the given list A
// N, M: size of list row and column respectively
   public static int findIslands(ArrayList<ArrayList<Integer>> A, int N, int M) {
        if(A==null  || A.isEmpty())
        return 0;
        int count=0;
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.get(i).size();j++){
                if(A.get(i).get(j)==1){
                    dfs(A,i,j);
                    count++;
                }
                
            }
        }
        return count;
    }
  public static void dfs(ArrayList<ArrayList<Integer>> A,int i,int j){
        if(i<0||j<0||i>=A.size()||j>=A.get(i).size()||A.get(i).get(j)==0)
            return;
        A.get(i).set(j,0);
        dfs(A,i-1,j);
        dfs(A,i,j-1);
        dfs(A,i+1,j);
        dfs(A,i,j+1);
        dfs(A,i-1,j-1);
        dfs(A,i-1,j+1);
        dfs(A,i+1,j-1);
        dfs(A,i+1,j+1);
    }
}

//Code 3
class Islands {
// Function to find the number of island in the given list A
// N, M: size of list row and column respectively
  public static int findIslands(ArrayList<ArrayList<Integer>> A, int N, int M) {
        if(A==null  || A.isEmpty())
        return 0;
        int count=0;
        boolean[][] visited = new boolean[A.size()][A.get(0).size()];
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.get(i).size();j++){
                if(A.get(i).get(j)==1 && !visited[i][j]){
                    dfs(A,i,j,visited);
                    count++;
                }
                
            }
        }
        return count;
    }
  public static void dfs(ArrayList<ArrayList<Integer>> A,int i,int j,boolean[][] visited){
        if(i<0||j<0||i>=A.size()||j>=A.get(i).size()||A.get(i).get(j)==0||visited[i][j])
            return;
        visited[i][j]=true;
        dfs(A,i-1,j,visited);
        dfs(A,i,j-1,visited);
        dfs(A,i+1,j,visited);
        dfs(A,i,j+1,visited);
        
    }
}

//Code 4
class Islands {
// Function to find the number of island in the given list A
// N, M: size of list row and column respectively
  public static int findIslands(ArrayList<ArrayList<Integer>> A, int N, int M) {
        if(A==null  || A.isEmpty())
        return 0;
        int count=0;
        boolean[][] visited = new boolean[A.size()][A.get(0).size()];
        for(int i=0;i<A.size();i++){
            for(int j=0;j<A.get(i).size();j++){
                if(A.get(i).get(j)==1 && !visited[i][j]){
                    dfs(A,i,j,visited);
                    count++;
                }
                
            }
        }
        return count;
    }
   public static void dfs(ArrayList<ArrayList<Integer>> A,int i,int j,boolean[][] visited){
        if(i<0||j<0||i>=A.size()||j>=A.get(i).size()||A.get(i).get(j)==0||visited[i][j])
            return;
        visited[i][j]=true;
        dfs(A,i-1,j,visited);
        dfs(A,i,j-1,visited);
        dfs(A,i+1,j,visited);
        dfs(A,i,j+1,visited);
        dfs(A,i-1,j-1,visited);
        dfs(A,i-1,j+1,visited);
        dfs(A,i+1,j-1,visited);
        dfs(A,i+1,j+1,visited);
    }
}

Thank you for reading the article.