Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

```
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

```
1 <= T <= 10
1 <= M, N, K <= 100
0 <= Ri< m
0 <= Ci < n
Time Limit: 1 sec
```

```
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
```

```
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 ) ].
```

```
2
3 3
4
0 0
0 1
1 2
2 1
4 5
4
1 1
0 1
3 3
3 4
```

```
1 1 2 3
1 1 2 2
```