Number Of Islands Ii - Leetcode Solution

Number Of Islands II problem on Leetcode is a problem that requires you to find the number of distinct islands present in a 2D matrix given a list of coordinates. In this problem, an island is defined as a group of connected 1s, where a group is defined as cells connected horizontally or vertically, but not diagonally.

Here is a detailed solution to the Number Of Islands II problem:

Approach:

The problem can be solved using the Union-Find algorithm. We can maintain a parent pointer for each cell in the 2D matrix representing the group it belongs to. Initially, all cells are considered as islands, and the parent pointer for each cell is set to itself. As we process coordinates one by one, we check if the cell is already a part of an island or not. If it is not, we try to merge the cell with its neighboring cells until we find an existing group. At the end of each operation, we update the count of distinct groups.

Algorithm:

1. Create a 2D matrix of size [m][n] and an array islands of size [m*n]. Each cell in the matrix represents the group it belongs to, and the elements of the array islands represent the parent pointer of the group.

2. Initialize each cell in the matrix with -1 and each element in the islands array with -1, indicating that all cells are distinct islands.

3. Initialize a variable count to 0, indicating the number of distinct islands found.

4. Initialize four arrays dx and dy of size 4, representing the coordinates of the neighboring cells.

5. For each coordinate, perform the following steps:

   a. Calculate the index of the cell in the matrix using the formula i*n+j, where i and j are the row and column indices of the cell, respectively.

   b. Set the value of the cell in the matrix to the index.

   c. Set the value of the element in the islands array to the index.

   d. Increment the count of distinct islands by 1.

   e. Check the neighboring cells of the current coordinate using the dx and dy arrays, and try to merge them with the current cell using the union function.

   f. If the current cell and its neighboring cells belong to different groups, update the parent pointer of one of them to point to the other. Then, decrement the count of distinct islands by 1.

6. Return an array of size k, representing the number of distinct islands found after processing each coordinate.

Code:

Here is the Python implementation of the above algorithm:

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        islands = [-1] * (m*n)
        matrix = [[-1 for _ in range(n)] for _ in range(m)]
        dx = [1,0,-1,0]
        dy = [0,1,0,-1]
        count = 0
        result = []
        
        def find(x):
            if islands[x] == x:
                return x
            islands[x] = find(islands[x])
            return islands[x]
    
        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                islands[px] = py
                return True
            return False
    
        for position in positions:
            i, j = position[0], position[1]
            idx = i*n+j
            if matrix[i][j] == -1:
                matrix[i][j] = idx
                islands[idx] = idx
                count += 1
    
                for k in range(4):
                    ni, nj = i+dx[k], j+dy[k]
                    if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] != -1:
                        if union(idx, matrix[ni][nj]):
                            count -= 1
            result.append(count)
        return result

Time Complexity:

The time complexity of the algorithm is O(k log(mn)), where k is the number of coordinates, and mn is the size of the matrix. The union-find operations take log(mn) time in the worst case. Since we perform k operations, the total time complexity is O(k log(mn)).

Space Complexity:

The space complexity of the algorithm is O(m*n), which is the size of the matrix and the islands array.

1