# COUNT ISLANDS

Contributed by
Abhishek Gupta
Last Updated: 23 Feb, 2023
Medium
0/80
Avg time to solve 40 mins
Success Rate 40 %
Share

## Problem Statement

#### An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the 'GRID' are all surrounded by water.

##### Example:
``````Input: ‘M’ = 3, 'N' = 3, 'POSITIONS' = [ [ 0,0 ], [ 0,1 ], [ 1,2 ], [ 2,1 ] ]

Output: [1, 1, 2, 3]

Initially, the 2d  'GRID' is filled with water.
- Operation #1: addLand(0, 0) turns the water at  ‘GRID[0][0]’ into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at  ‘GRID[0][1]’ into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at  'GRID[1][2]’ into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at  'GRID[2][1]’ into a land. We have 3 islands.
``````
Detailed explanation ( Input/output format, Notes, Images )
##### Constraints :
``````1 <= T <= 10
1 <= M, N, K <= 100
0 <= Ri< m
0 <= Ci < n

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
1 3
3
0 0
0 1
0 2
1 3
3
0 0
0 2
0 1
``````

##### Sample Output 1 :

`````` 1 1 1
1 2 1
``````
##### Explanation Of Sample Input 1 :
``````For the first test case:-
- Operation #1: addLand(0, 0) turns the water at  ‘GRID’[0][0] into a land. We have 1 island,  [( 0, 0)].
- Operation #2: addLand(0, 1) turns the water at  ‘GRID’[0][1] into a land. We still have 1     island,  [ ( 0, 0) , ( 0, 1 ) ].
- Operation #3: addLand(0, 2) turns the water at  'GRID'[1][2] into a land. We still have 1 island,  [ ( 0, 0) , ( 0, 1 ), ( 0, 2 ) ].

For the second test case:-
- Operation #1: addLand(0, 0) turns the water at  ‘GRID’[0][0] into a land. We have 1 island, [ ( 0, 0 ) ].
- Operation #2: addLand(0, 2) turns the water at  ‘GRID’[0][1] into a land. We still have 2    islands, [ ( 0, 0 ) ] and [ ( 0, 2 ) ].
- Operation #3: addLand(0, 2) turns the water at  'GRID'[1][2] into a land. We have 1 island,  [ ( 0, 0) , ( 0, 1 ), ( 0, 2 ) ].
``````
##### Sample Input 2 :
``````2
3 3
4
0 0
0 1
1 2
2 1
4 5
4
1 1
0 1
3 3
3 4
``````
##### Sample Output 2 :
`````` 1 1 2 3
1 1 2 2
``````
Autocomplete
Console