Given a two-dimensional boolean matrix, find the number of islands.

An island is a group of connected 1s or a standalone 1. A cell in the matrix can be connected to up to 8 neighbors:** **2 vertical, 2 horizontal and 4 diagonal.

**Example**

Input:

[

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

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

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

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

[1, 0, 1, 0, 1]

]

Output: 5

(0 0), (0 1), (1 1) and (2 0) make an island.

(1 4), (2 4) and (2 3) make an island.

(4 0) makes an island.

(4 2) makes an island.

(4 4) makes an island.

**Notes**

Input Format: Function has one argument, a two-dimensional integer matrix. All the values in the matrix are either 0 or 1.

Output Format: Return an integer, the number of islands of 1s.

Constraints:

- 1 <= rows <= 450
- 1 <= columns <= 450
- Values in the matrix are either 0 or 1.

Solve the problem without allocating a “visited” matrix.

Below are the 2 solutions

The problem is easy but there is one very important thing to learn. We recommend reading through the whole editorial even if your solution passed all tests.

Treat the matrix like a graph and do a simple DFS (see other_solution.cpp) or BFS (see optimal_solution.cpp).

We are not allowed to use a “visited” matrix, but we can modify the input matrix itself! When a node is visited, change its value from 1 to 0.

**Time Complexity:**

Time complexity of BFS or DFS is O(V + E), in our case it will be O(n * m + 8 * n * m) that is O(n * m).

**Auxiliary Space Used:**

O(n * m) for the DFS solution, other_solution.cpp. The space is used by the call stack because the solution is recursive. If we had used an iterative DFS implementation, we would use a stack and same O(n * m) auxiliary space for that.

Consider the worst case for DFS:

9

10

1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 0 1

1 0 0 0 0 0 0 1 0 1

1 0 1 1 1 1 0 1 0 1

1 0 1 0 0 0 0 1 0 1

1 0 1 1 1 1 1 1 0 1

1 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1

DFS would make up to almost (n * m) / 2 nested recursive calls; that takes O(n * m) space.

BFS solution (optimal_solution.cpp), on the other hand, uses just O(max(n, m)) of auxiliary space.

Consider the worst case for BFS:

10

10

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

At some point of time all the nodes of the last row and last column will be in the queue. The queue will then take O(n+m) = O(max(n, m)) space.

This difference in used space between the two algorithms can affect performance in some real life cases.

**Space Complexity:**

O(n * m) due to input size and auxiliary space used.