Find the number of Islands

  1. Island is considered a single if any vertical OR horizontal is 1.(either of 4 directions vertical and horizontal)
  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.
//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);
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store