Last Updated: 21 Mar, 2021

Number of Islands II

Hard
Asked in companies
UberFlipkartMakeMyTrip

Problem statement

You have a 2D grid of ‘N’ rows and ‘M’ columns which are initially filled with water. You are given ‘Q’ queries each consisting of two integers ‘X’ and ‘Y’ and in each query operation, you have to turn the water at position (‘X’, ‘Y’) into a land. You are supposed to find the number of islands in the grid after each query.

An island is a group of lands surrounded by water horizontally, vertically, or diagonally.

Input Format:
The first line contains an integer ‘T’ denoting the number of test cases. 

The first input line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

The second line of each test case contains an integer ‘Q’ representing the number of queries.

Next ‘Q’ lines contain two single space-separated integers ‘X’ and ‘Y’, representing the coordinates of the grid i.e the coordinates of the point to be turned into land.
Output Format:
For each test case, print a single integer denoting the number of islands after each query operation.

Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 1000
1 <= M <= 1000
1 <= Q <= 100000
0 <= X < N
0 <= Y < M

Time limit: 1 sec

Approaches

01 Approach

The idea here is to represent the grid as a graph and all the adjacent land cells are connected via an edge. Finally, do DFS on the grid and find the number of connected components after each query operation.

 

The algorithm is as follows:

  1. Declare an ‘ANS’ array to store the number of islands after each query.
  2. Declare a 2D array 'GRID' with ‘N’ rows and ‘M’ columns, where ‘GRID[i][j]’ = 0 or 1, 0 representing water and 1 representing land.
  3. Declare a ‘DX’ array representing and set it to {1, 0, -1, 0}, representing the directions of all four neighboring cells.
  4. Declare a ‘DY’ array representing and set it to {0, 1, 0, -1}, representing the directions of all four neighboring cells.
  5. Iterate from ‘P’ = 0 to ‘Q.size() - 1’,
    • Declare a variable ‘X’ and set it to ‘Q[i][0]’.
    • Declare a variable ‘Y’ and set it to 'Q[i][1]'.
    • Set ‘GRID[X][Y]’ to 1, i.e i.e cell is converted into the land.
    • Declare a variable 'NUMBEROFISLANDS' and set it to 0.
    • Declare a 2D array ‘VISITED’ with ‘N’ rows and ‘M’ columns, where ‘VISITED[i][j]’ = 0 or 1, 0 representing the current cell being visited and 1 representing not visited.
    • Iterate from ‘i’ = 0 to ‘N’ - 1,
      • Iterate from ‘j’ = 0 toM’ - 1,
        • If ‘GRID[i][j]’ == 1 && ‘VISITED[i][j]’ == 0,
          • This means the current cell is an island that is not seen before.
          • Run a ‘DFS’ function and mark all the connected lands as ‘VISITED’ that are connected to the cell (i,j).
          • Increment 'NUMBEROFISLANDS' by 1.
    • Append 'NUMBEROFISLANDS' to ‘ANS’.
  6. Return the ‘ANS’ array.

02 Approach

The idea here is to use the union-find data structure to efficiently count the number of connected components in the grid. For each query, we will union the given land position with all the neighboring lands. Creating land increases the 'NUMBEROFISLANDS' by 1. But if we connect two different islands together it decreases the 'NUMBEROFISLANDS' by 1.

 

The algorithm is as follows:

  1. Declare a 'PARENT' array of size ('N * M') to keep track of the parent node of each connected component, initially, none of the cells are connected. Hence each cell is its own parent.
  2. Declare an ‘ANS’ array to store the number of islands after each query.
  3. Declare a 2D array 'GRID' with ‘N’ rows and ‘M’ columns, where ‘GRID[i][j]’ = 0 or 1, 0 representing water and 1 representing land.
  4. Declare a ‘DX array representing and set it to {1, 0, -1, 0}, representing the directions of all four neighboring cells.
  5. Declare a ‘DY array representing and set it to {0, 1, 0, -1}, representing the directions of all four neighboring cells.
  6. Declare a variable 'NUMBEROFISLANDS' and set it to 0.
  7. Iterate from ‘i’ = 0 to ‘Q.size() - 1’,
    • Declare a variable ‘X’ and set it to ‘Q[i][0]’.
    • Declare a variable ‘Y’ and set it to ‘Q[i][1]’.
    • If ‘GRID[X][Y]’ == 1, this position is already taken care of.
      • Append 'NUMBEROFISLANDS' to ‘ANS’.
      • And continue from here.
    • Increment 'NUMBEROFISLANDS' by 1.
    • Iterate from ‘DIR’ = 0 to 3,
      • Declare a variable 'NEWX' and set it to ‘X + DX[DIR]’.
      • Declare a variable 'NEWY' and set it to ‘Y + DY[DIR]’.
      • If 'NEWX' and 'NEWY' are invalid coordinates, continue.
      • If GRID[NEWX][NEWY] == 0, continue.
      • If the parent of {'NEWX', 'NEWY'} and parent of {X, Y} are not the same, this means that two different islands are being connected, so decrement 'NUMBEROFISLANDS' by 1.
      • Union the two coordinates {X, Y} and {'NEWX', 'NEWY'}.
    • Set ‘GRID[X][Y]’ to 1, i.e cell is converted into land.
    • Append 'NUMBEROFISLANDS' to ‘ANS’.
  8. Return the ‘ANS’ array.