Jobs

Interviews

Discussions

Number of Islands II

Hard

Number of Islands II

Hard

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what is the range of values for row and column indices in the positions array?
Are the row and column indices in the positions array zero-based or one-based?
If adding a new land cell merges previously separate islands, should I update the count of islands immediately after each add operation?
If a position in 'positions' is out of bounds, should I ignore it, throw an error, or handle it some other way?
What should I return if the positions array is empty or null?

Brute Force Solution

Approach

The brute force approach to the 'Number of Islands II' problem involves checking the number of islands after each addition of land. We treat each land addition as a separate and independent scenario. This means we re-evaluate the entire grid to count the islands every time we add a new piece of land.

Here's how the algorithm would work step-by-step:

Start with an empty grid, representing an ocean.
For each new piece of land you add to the grid, place it on the grid.
After adding each piece of land, go through the entire grid cell by cell.
Count how many separate land areas (islands) there are in the grid, considering that neighboring land cells are part of the same island.
Record the number of islands after each new piece of land is added.
Repeat this process for every piece of land given as input.

Code Implementation

def number_of_islands_ii_brute_force(number_of_rows, number_of_columns, positions):
    island_counts = []
    grid = [[0] * number_of_columns for _ in range(number_of_rows)]

    for position in positions:
        row, column = position

        # Mark the current position as land
        grid[row][column] = 1

        number_of_islands = 0
        visited = set()

        # Iterate through the entire grid to count islands
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                if grid[row_index][column_index] == 1 and (row_index, column_index) not in visited:
                    number_of_islands += 1
                    depth_first_search(grid, row_index, column_index, visited, number_of_rows, number_of_columns)

        island_counts.append(number_of_islands)

    return island_counts

def depth_first_search(grid, row, column, visited, number_of_rows, number_of_columns):
    if row < 0 or row >= number_of_rows or column < 0 or column >= number_of_columns or \
       grid[row][column] == 0 or (row, column) in visited:
        return

    visited.add((row, column))
    # Explore adjacent land cells to find the entire island.
    depth_first_search(grid, row + 1, column, visited, number_of_rows, number_of_columns)

    depth_first_search(grid, row - 1, column, visited, number_of_rows, number_of_columns)

    depth_first_search(grid, row, column + 1, visited, number_of_rows, number_of_columns)

    depth_first_search(grid, row, column - 1, visited, number_of_rows, number_of_columns)

Big(O) Analysis

Time Complexity

O(m * n * n) – Let m be the number of land additions and n be the number of rows/columns in the grid. For each of the m land additions, we iterate through the entire n x n grid to count the number of islands. Counting the islands involves visiting each cell of the grid. Thus, for each land addition, the island counting takes O(n * n) time. Since we do this for each of the m land additions, the overall time complexity is O(m * n * n).

Space Complexity

O(m * n) – The brute force approach, as described, maintains a grid representing the ocean and land. This grid has dimensions m x n, where m is the number of rows and n is the number of columns, as defined in the problem constraints (not explicitly given as N in the plain English explanation, but implied by the problem). The space required to store this grid is proportional to the number of cells, which is m * n. Therefore, the auxiliary space complexity is O(m * n).

Optimal Solution

Approach

This problem involves tracking islands as we add land cells to a sea. The key idea is to use a structure that efficiently determines if newly added land connects existing islands and to merge those islands into one.

Here's how the algorithm would work step-by-step:

Imagine each land cell belongs to its own individual tiny island at first.
When we add a new land cell, check its neighbors (up, down, left, right) to see if they are also land.
If a neighbor is land, it means the new land cell connects to the neighbor's island.
If multiple neighbors are land, the new land cell connects multiple islands, and these islands must be merged into a single, bigger island.
Keep track of how many truly separate islands there are by decreasing the count when merging islands.
Using a special 'parent' tracking structure allows you to quickly find which island a land cell belongs to and to efficiently merge islands.
This allows you to quickly determine the number of islands after adding each new land cell without re-checking the entire grid.

Code Implementation

class Solution:
    def numIslands2(self, grid_rows, grid_cols, positions):
        parent = [i for i in range(grid_rows * grid_cols)]
        rank = [0] * (grid_rows * grid_cols)
        island_count = 0
        result = []

        def find(node_id):
            if parent[node_id] != node_id:
                parent[node_id] = find(parent[node_id])
            return parent[node_id]

        def union(node_id_one, node_id_two):
            root_one = find(node_id_one)
            root_two = find(node_id_two)

            if root_one != root_two:
                # Attach smaller rank tree under root of high rank tree
                if rank[root_one] > rank[root_two]:
                    parent[root_two] = root_one
                elif rank[root_one] < rank[root_two]:
                    parent[root_one] = root_two
                # If ranks are same, then make one root and increment
                else:
                    parent[root_two] = root_one
                    rank[root_one] += 1
                return True
            return False

        grid = [[0] * grid_cols for _ in range(grid_rows)]
        for row, col in positions:
            if grid[row][col] == 1:
                result.append(island_count)
                continue

            grid[row][col] = 1
            island_count += 1
            current_node_id = row * grid_cols + col
            neighbors = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]

            for neighbor_row, neighbor_col in neighbors:
                if 0 <= neighbor_row < grid_rows and 0 <= neighbor_col < grid_cols and grid[neighbor_row][neighbor_col] == 1:
                    neighbor_node_id = neighbor_row * grid_cols + neighbor_col

                    # Merging islands and decrementing count
                    if union(current_node_id, neighbor_node_id):
                        island_count -= 1

            result.append(island_count)

        return result

Big(O) Analysis

Time Complexity

O(k log(m*n)) – The input consists of k operations where we add a land cell. For each land cell addition, we perform a constant number of neighbor checks (maximum 4). The core operation is finding the root of the connected component and merging components using a disjoint-set data structure (Union-Find). Finding the root and union operations take O(α(m*n)) time, where α is the inverse Ackermann function which grows extremely slowly and can be considered almost constant in practice. However, a simplified logarithmic cost of log(m*n) can be used, where m and n are the dimensions of the grid. Therefore, processing k operations takes O(k log(m*n)) time.

Space Complexity

O(M * N) – The primary auxiliary space usage comes from the 'parent' tracking structure, which is used to represent the connected components. In the worst-case scenario where all cells in the grid of dimensions M x N become land, the 'parent' array will need to store a value for each cell. This leads to an auxiliary array of size M * N to track the parent of each cell, allowing for efficient island merging. Therefore, the space complexity is O(M * N).

Edge Cases

Case	How to Handle
Empty grid dimensions (m=0 or n=0)	Return an empty list because no islands can be formed in an empty grid.
Null or empty positions array	Return an empty list if the positions array is null or empty, as no islands are being added.
Positions outside the grid boundaries	Ignore positions that are out of bounds to prevent array index out of bounds errors.
Duplicate positions in the positions array	The union-find data structure will correctly merge islands even if the same position is added multiple times.
Large grid dimensions (m and n are very large)	The union-find data structure should be optimized for path compression and union by rank to handle large grids efficiently.
Integer overflow when calculating the position index	Use long data type to store the index to prevent overflow when calculating the flattened index (row * n + col).
Maximum number of operations	Ensure union-find data structure operations do not exceed time limits, and optimize for path compression and union by rank.
Grid already full of land before any add operations	The algorithm should correctly count islands that were initially connected and update the count as new islands connect with existing ones.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what is the range of values for row and column indices in the positions array?
Are the row and column indices in the positions array zero-based or one-based?
If adding a new land cell merges previously separate islands, should I update the count of islands immediately after each add operation?
If a position in 'positions' is out of bounds, should I ignore it, throw an error, or handle it some other way?
What should I return if the positions array is empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty grid, representing an ocean.
For each new piece of land you add to the grid, place it on the grid.
After adding each piece of land, go through the entire grid cell by cell.
Count how many separate land areas (islands) there are in the grid, considering that neighboring land cells are part of the same island.
Record the number of islands after each new piece of land is added.
Repeat this process for every piece of land given as input.

Code Implementation

def number_of_islands_ii_brute_force(number_of_rows, number_of_columns, positions):
    island_counts = []
    grid = [[0] * number_of_columns for _ in range(number_of_rows)]

    for position in positions:
        row, column = position

        # Mark the current position as land
        grid[row][column] = 1

        number_of_islands = 0
        visited = set()

        # Iterate through the entire grid to count islands
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                if grid[row_index][column_index] == 1 and (row_index, column_index) not in visited:
                    number_of_islands += 1
                    depth_first_search(grid, row_index, column_index, visited, number_of_rows, number_of_columns)

        island_counts.append(number_of_islands)

    return island_counts

def depth_first_search(grid, row, column, visited, number_of_rows, number_of_columns):
    if row < 0 or row >= number_of_rows or column < 0 or column >= number_of_columns or \
       grid[row][column] == 0 or (row, column) in visited:
        return

    visited.add((row, column))
    # Explore adjacent land cells to find the entire island.
    depth_first_search(grid, row + 1, column, visited, number_of_rows, number_of_columns)

    depth_first_search(grid, row - 1, column, visited, number_of_rows, number_of_columns)

    depth_first_search(grid, row, column + 1, visited, number_of_rows, number_of_columns)

    depth_first_search(grid, row, column - 1, visited, number_of_rows, number_of_columns)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each land cell belongs to its own individual tiny island at first.
When we add a new land cell, check its neighbors (up, down, left, right) to see if they are also land.
If a neighbor is land, it means the new land cell connects to the neighbor's island.
If multiple neighbors are land, the new land cell connects multiple islands, and these islands must be merged into a single, bigger island.
Keep track of how many truly separate islands there are by decreasing the count when merging islands.
Using a special 'parent' tracking structure allows you to quickly find which island a land cell belongs to and to efficiently merge islands.
This allows you to quickly determine the number of islands after adding each new land cell without re-checking the entire grid.

Code Implementation

class Solution:
    def numIslands2(self, grid_rows, grid_cols, positions):
        parent = [i for i in range(grid_rows * grid_cols)]
        rank = [0] * (grid_rows * grid_cols)
        island_count = 0
        result = []

        def find(node_id):
            if parent[node_id] != node_id:
                parent[node_id] = find(parent[node_id])
            return parent[node_id]

        def union(node_id_one, node_id_two):
            root_one = find(node_id_one)
            root_two = find(node_id_two)

            if root_one != root_two:
                # Attach smaller rank tree under root of high rank tree
                if rank[root_one] > rank[root_two]:
                    parent[root_two] = root_one
                elif rank[root_one] < rank[root_two]:
                    parent[root_one] = root_two
                # If ranks are same, then make one root and increment
                else:
                    parent[root_two] = root_one
                    rank[root_one] += 1
                return True
            return False

        grid = [[0] * grid_cols for _ in range(grid_rows)]
        for row, col in positions:
            if grid[row][col] == 1:
                result.append(island_count)
                continue

            grid[row][col] = 1
            island_count += 1
            current_node_id = row * grid_cols + col
            neighbors = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]

            for neighbor_row, neighbor_col in neighbors:
                if 0 <= neighbor_row < grid_rows and 0 <= neighbor_col < grid_cols and grid[neighbor_row][neighbor_col] == 1:
                    neighbor_node_id = neighbor_row * grid_cols + neighbor_col

                    # Merging islands and decrementing count
                    if union(current_node_id, neighbor_node_id):
                        island_count -= 1

            result.append(island_count)

        return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty grid dimensions (m=0 or n=0)	Return an empty list because no islands can be formed in an empty grid.
Null or empty positions array	Return an empty list if the positions array is null or empty, as no islands are being added.
Positions outside the grid boundaries	Ignore positions that are out of bounds to prevent array index out of bounds errors.
Duplicate positions in the positions array	The union-find data structure will correctly merge islands even if the same position is added multiple times.
Large grid dimensions (m and n are very large)	The union-find data structure should be optimized for path compression and union by rank to handle large grids efficiently.
Integer overflow when calculating the position index	Use long data type to store the index to prevent overflow when calculating the flattened index (row * n + col).
Maximum number of operations	Ensure union-find data structure operations do not exceed time limits, and optimize for path compression and union by rank.
Grid already full of land before any add operations	The algorithm should correctly count islands that were initially connected and update the count as new islands connect with existing ones.