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.

Thank you for reading the article.

Software Developer