Number of Islands II

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
37 upvotes
Asked in companies
OYOAmazonIBM

Problem statement

You are given two integers 'n' and 'm', the dimensions of a grid. The coordinates are from (0, 0) to (n - 1, m - 1).


The grid can only have values 0 and 1.


The value is 0 if there is water and 1 if there is land.


An island is a group of ‘1’s such that every ‘1’ has at least another ‘1’ sharing a common edge.


You are given an array 'queries' of size 'q'.


Each element in 'queries' contains two integers 'x' and 'y', referring to the coordinates in the grid.


Initially, the grid is filled with 0, which means only water and no land.


At each query, the value of 'grid' at (x, y) becomes 1, which means it becomes land.


Find out, after each query, the number of islands in the grid.


Example : 
Input: 'n' = 3, 'm' = 4
'queries' = [[1, 1], [1, 2], [2, 3]]

Output: [1, 1, 2]

Explanation:

Initially, the grid was:
0 0 0 0
0 0 0 0
0 0 0 0

After query (1, 1):
0 0 0 0
0 1 0 0
0 0 0 0
There is one island having land (1, 1).

After query (1, 2):
0 0 0 0
0 1 1 0
0 0 0 0
Since (1, 1) and (1, 2) share a common edge, they form one island. So there is one island having lands (1, 1) and (1, 2).

After query (2, 3):
0 0 0 0
0 1 1 0
0 0 0 1
Now there are two islands, one having lands (1, 1) and (1, 2), and another having land (2, 3).

So the number of islands after each query is [1, 1, 2].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two integers, 'n' and 'm' denoting the number of rows and columns in the grid, respectively.

The second line contains an integer 'q' denoting the number of queries.

The next 'q' lines contain two integers each, the coordinates which are becoming land.


Output Format : 
Print an array of size 'q', denoting the answer of each query.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
3 4
3
1 1
1 2
2 3


Sample Output 1:
1 1 2


Explanation of sample input 1 :
Initially, the grid was:
0 0 0 0
0 0 0 0
0 0 0 0

After query (1, 1):
0 0 0 0
0 1 0 0
0 0 0 0
There is one island having land (1, 1).

After query (1, 2):
0 0 0 0
0 1 1 0
0 0 0 0
Since (1, 1) and (1, 2) share a common edge, they form one island. So there is one island having lands (1, 1) and (1, 2).

After query (2, 3):
0 0 0 0
0 1 1 0
0 0 0 1
Now there are two islands, one having lands (1, 1) and (1, 2), and another having land (2, 3).

So the number of islands after each query is [1, 1, 2].


Sample Input 2:
3 5
3
1 1
1 3
1 2


Sample Output 2:
1 2 1


Expected time complexity :
The expected time complexity is O(n * m + q).


Constraints :
1 <= 'n', 'm' <= 1000
1 <= 'q' <= 10 ^ 4
0 <= 'x' < 'n'
0 <= 'y' < 'm'

All the (x, y) pairs are unique.

Time limit: 1 second
Hint

We can use the Disjoint Set Union data structure to track connected lands efficiently.

Approaches (1)
Using Disjoint Set Union

We can use Disjoint Set Union to keep track of connected lands efficiently.

We can make a DSU of size 'n' * 'm', and for every coordinate (i, j), we can map them to 'i' * 'm' + 'j' in the DSU.

At any query (x, y), we will check all four directions. If there is land in the adjacent coordinate, we will merge them and manage the total number of islands.

The steps are as follows:

int[] numberOfIslandsII(int 'n', int 'm', int 'queries[][]', int 'q')

  1. Initialise a DSU of size 'n' * 'm'.
  2. Let 'ans' be an array of size 'q'.
  3. Let 'count' = 0 be the variable to store the number of islands after each query.
  4. Let 'grid' be a 2-D matrix of size 'n' * 'm' and filled with 0. This is used to store the coordinates converted into land.
  5. For each 'query' in 'queries':
    • Let 'x' = query[0], 'y' = query[1]
    • 'grid[x][y]' = 1
    • First, we will consider (x, y) as an island. So increase 'count' by 1.
    • Now, for each of the four directions, do the following:
      • If the coordinate at the respective direction of (x, y) exists and is equal to 1, this means (x, y) can be merged to that coordinate’s island group. So:
        • Merge (x, y) and that coordinate.
        • Decrease count by 1.
    • Append 'count' in 'ans'.
  6. Return ‘ans’.
Time Complexity

O(n * m + q), Where 'n' and 'm' are the dimensions of the grid, and 'q' is the number of queries.

The initialisation of the DSU data structure is linear time, and we have DSU of size 'n' * 'm'.

The queries loop will run at most 4 * 'q' times.

Hence the time complexity is O(n * m + q).

Space Complexity

O(n * m + q), Where 'n' and 'm' are the dimensions of the grid, and 'q' is the number of queries.

The DSU data structure and 'grid' matrix consume space O(n * m).

The 'ans' array is of size O(q).

Hence the space complexity is O(n * m + q).

Code Solution
(100% EXP penalty)
Number of Islands II
Full screen
Console