## Introduction

The challenge for today is to calculate the number of Islands in the given 2-D grid.

## The problem statement

*Given an m x n 2D binary grid, a grid representing a map of '1's (land) and '0's (water) returns the number of islands.*

A collection of connected 1s forms an island.

**Example 1**:

Input: grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

**Output: 1**

**Explanation**:

**Example 2**:

Input: grid = [

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]

**Output: 3**

**Explanation:**

__It is recommended to attempt the problem on your own first before moving to the solution. __

The problem is quite similar to the common problem: “__Counting the number of connected components in an undirected graph__.”

Before we go into the problem, let's define a connected component that will be helpful to solve the current problem:-

A component of an undirected graph is an induced subgraph in which any two vertices are connected by paths but are not connected to any other vertices in the graph. The graph in the picture, for example, contains three components.

Source:- __Wikipedia__

Furthermore, a vertex with no incident edges is a component in and of itself.

Let's revisit the **Equivalence Relation**’s discrete mathematics topic and examine how the components form a connection in a graph or other data structure.

So, a relation is an equivalence relation if it is **Reflexive**, **Symmetric**, and **Transitive**. If a component follows any of the properties, it is referred to as a connected component. Let's look at how:

**Reflexive Property**:- From any vertex to itself, there is a simple route of length zero.

**Symmetric Property**:- If a path exists from u to v, the same edges also exist from v to u.

**Transitive Property**:- If there are pathways from u to v and v to w, the two paths can be joined to produce a path from u to w.

All of the stated examples can also be referred to as the connected components as said above.

Now how is this related to our problem?

If we concentrate on our task, we need to count the total number of 1's connected to others 1's in any way.

The idea is to apply __DFS Algorithm__ to each component. Each DFS call visits a component or a sub-graph. We'll call DFS to the next un-visited component. The number of DFS calls represents the number of connected components.

A cell in a 2D matrix can have up to 8 neighbours. In contrast to standard DFS, which recursively calls for all neighbouring vertices, we can only recursively call for 8 neighbours here. We keep track of the visited 1s so that they do not need to be revisited.

Let’s discuss the algorithm now: