 New update is available. Click here to update.
Topics

# COUNT ISLANDS

Moderate 0/80
Average time to solve is 40m

## Problem statement

You are given an empty 2D binary 'GRID' of size ‘N’ x 'M' The 'GRID' represents a map where 0's represent water and 1's represent land. Initially, all the cells of the 'GRID' are water cells (i.e., all the cells are 0's).

We may perform an add land operation which turns the water at position into a land. You are given an array 'POSITIONS' of size ‘K’ where POSITIONS[i] = [Ri, Ci] is the position (Ri, Ci) at which we should operate the ith operation.

Return an array of integers answer where ‘ANSWER[i]’ is the number of islands after turning the cell (‘Ri’, ‘Ci’) into a land.

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’ into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at  ‘GRID’ into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at  'GRID’ into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at  'GRID’ 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’ into a land. We have 1 island,  [( 0, 0)].
- Operation #2: addLand(0, 1) turns the water at  ‘GRID’ into a land. We still have 1     island,  [ ( 0, 0) , ( 0, 1 ) ].
- Operation #3: addLand(0, 2) turns the water at  'GRID' 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’ into a land. We have 1 island, [ ( 0, 0 ) ].
- Operation #2: addLand(0, 2) turns the water at  ‘GRID’ into a land. We still have 2    islands, [ ( 0, 0 ) ] and [ ( 0, 2 ) ].
- Operation #3: addLand(0, 2) turns the water at  'GRID' 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
`````` Console