Jobs

Interviews

Discussions

Number of Distinct Islands II

Hard

Amazon

4 views

Topics:

ArraysGraphsRecursion

You are given a binary matrix grid of size m x n where 0 represents water and 1 represents land. An island is a group of 1s connected 4-directionally (horizontal or vertical). Two islands are considered the same if and only if one island can be transformed into another by translation, rotation (90, 180, 270 degrees only), and reflection (about the x-axis, y-axis, or both).

Write a function that determines the number of distinct islands. Since rotation and reflection can transform an island into multiple shapes, you should normalize the island into its canonical form. The goal is to count only unique island shapes after accounting for all possible transformations.

For example:

Input: grid = [
  [1,1,0,0,0],
  [1,0,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]
Output: 1
Explanation: The first two islands are considered the same because we can rotate the first island by 90 degrees to make the second island.

Input: grid = [
  [1,1,0,0,0],
  [1,1,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]
Output: 1

Input: grid = [
  [1,1,0],
  [0,1,1],
  [0,0,0],
  [1,1,1],
  [0,1,0]
]
Output: 3

Can you implement an efficient algorithm to solve this problem?

Number of Distinct Islands II

Hard

Amazon

4 views

Topics:

ArraysGraphsRecursion

For example:

Input: grid = [
  [1,1,0,0,0],
  [1,0,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]
Output: 1
Explanation: The first two islands are considered the same because we can rotate the first island by 90 degrees to make the second island.

Input: grid = [
  [1,1,0,0,0],
  [1,1,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]
Output: 1

Input: grid = [
  [1,1,0],
  [0,1,1],
  [0,0,0],
  [1,1,1],
  [0,1,0]
]
Output: 3

Can you implement an efficient algorithm to solve this problem?

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 is the maximum size of the grid (rows and columns)?
Is the grid guaranteed to be rectangular (i.e., all rows have the same number of columns)?
By 'distinct islands', do we consider islands distinct if they have a different shape after rotation or reflection, or are islands with the same shape in different locations also considered distinct?
Can the grid be empty or null?
What should I return if the input grid is null or empty? Should I return 0, null, or throw an exception?

Brute Force Solution

Approach

The core idea is to find all unique island shapes, treating rotated and reflected versions as the same. The brute force method explores every possible island by examining the entire grid for connected land masses.

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

Look at every single piece of land in the entire map.
Whenever you find a piece of land, try to trace out the whole island it belongs to.
Think of the island's shape as a set of directions you take to walk around it, starting from a specific spot.
Now, make copies of that island and rotate or flip them in every possible way (like turning a puzzle piece).
Compare each new island shape to all the island shapes you've found so far. If the new island, or any of its rotated or flipped copies, looks exactly like an island you've already saved, ignore it.
If none of the copies match any of the islands you've found before, then this is a brand new island shape. Save it.
Keep doing this for every piece of land in the map. At the end, you'll have a list of all the unique island shapes.

Code Implementation

def number_of_distinct_islands_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])
    islands = set()

    def explore_island(row, col, path, start_row, start_col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 0:
            return

        grid[row][col] = 0  # Mark as visited
        path.append((row - start_row, col - start_col))

        explore_island(row + 1, col, path, start_row, start_col)
        explore_island(row - 1, col, path, start_row, start_col)
        explore_island(row, col + 1, path, start_row, start_col)
        explore_island(row, col - 1, path, start_row, start_col)

    def normalize_island_shape(island_shape):
        normalized_shape = tuple(sorted(island_shape))
        return normalized_shape

    def generate_rotations_and_reflections(island_shape):
        rotated_and_reflected_shapes = set()
        for _ in range(4):
            # Rotate the island 90 degrees
            rotated_shape = [(y, -x) for x, y in island_shape]
            rotated_and_reflected_shapes.add(normalize_island_shape(rotated_shape))

            # Reflect the island along the x-axis
            reflected_shape = [(-x, y) for x, y in rotated_shape]
            rotated_and_reflected_shapes.add(normalize_island_shape(reflected_shape))

            island_shape = rotated_shape  # Update for next rotation

        return rotated_and_reflected_shapes

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                island_path = []

                # Find island and mark all visited lands
                explore_island(row, col, island_path, row, col)

                # Generate all rotations and reflections
                all_shapes = generate_rotations_and_reflections(island_path)

                is_unique = True
                for shape in all_shapes:
                    if shape in islands:

                        #If the shape is found skip to next landmass
                        is_unique = False
                        break

                if is_unique:

                    #if unique store shape to avoid duplicates
                    islands.add(normalize_island_shape(island_path))

    return len(islands)

Big(O) Analysis

Time Complexity

O(M * N * (M * N) * log(M * N)) – The algorithm iterates through each cell of the M x N grid, resulting in O(M * N) operations. For each land cell, it extracts the island's shape, which can have at most M * N cells. Transforming (rotating/flipping) the island also takes O(M * N) time. Comparing the transformed island to existing unique islands involves storing the island's shape (represented as a sequence of coordinates) and then comparing it to other stored shapes, which can be done efficiently using a set. The insertion into the set can take O(log(number of islands)) which at worse case can be O(log(M * N)). Combining these, for each cell we potentially extract and transform an island of at most M * N cells, and then possibly inserting the island into the set of stored islands, leading to a time complexity of O(M * N * (M * N) * log(M * N)).

Space Complexity

O(N) – The algorithm uses auxiliary space to store the discovered island, which in the worst case can be the entire grid. The algorithm also uses space to store all rotated and flipped versions of the island. Since there are a constant number of transformations (rotations and reflections), each of size at most N (where N is the total number of cells in the grid), the space used for these transformed islands is also O(N). A set is used to store unique island shapes, which, in the worst case, might contain all the islands discovered, thus consuming O(N) space overall. Therefore the total auxiliary space is O(N).

Optimal Solution

Approach

The goal is to identify distinct island shapes, even if they are rotated or flipped. The key is to transform each island into a unique, comparable representation by exploring its structure and normalizing it.

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

First, find each island in the grid. An island is a group of connected land cells.
For each island, extract all its land cells' coordinates relative to a fixed point (e.g., the top-left cell of the island).
Generate all eight possible transformations of these coordinates: rotations (0, 90, 180, 270 degrees) and reflections (flipping over x and y axes) for each rotation.
For each transformation, shift the coordinates so that the minimum x and y values are both zero. This ensures consistency and removes dependency on the initial location of the island.
Convert each set of transformed coordinates into a string representation, like a list of cell pairs. This enables easy comparison.
Compare all eight string representations of each island and select the lexicographically smallest one. This becomes the unique identifier for that island's shape, regardless of its initial orientation.
Store the unique identifiers in a set. The size of this set represents the number of distinct island shapes.

Code Implementation

def number_of_distinct_islands_two(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0]) if number_of_rows > 0 else 0
    visited = set()
    distinct_islands = set()

    def explore_island(row, column, current_island_cells):
        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))
        current_island_cells.append((row, column))

        explore_island(row + 1, column, current_island_cells)
        explore_island(row - 1, column, current_island_cells)
        explore_island(row, column + 1, current_island_cells)
        explore_island(row, column - 1, current_island_cells)

    def normalize_island(island_cells):
        min_row = min(row for row, column in island_cells)
        min_column = min(column for row, column in island_cells)
        return [(row - min_row, column - min_column) for row, column in island_cells]

    def rotate_island(island_cells):
        return [(-column, row) for row, column in island_cells]

    def flip_island(island_cells):
        return [(row, -column) for row, column in island_cells]

    def get_island_string(island_cells):
        return str(sorted(island_cells))

    def get_unique_island_string(island_cells):
        unique_strings = set()
        for _ in range(4):
            unique_strings.add(get_island_string(normalize_island(island_cells)))
            unique_strings.add(get_island_string(normalize_island(flip_island(island_cells))))
            island_cells = rotate_island(island_cells)
        return min(unique_strings)

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1 and (row, column) not in visited:
                current_island_cells = []
                explore_island(row, column, current_island_cells)

                # Generating unique string representation
                unique_island_string = get_unique_island_string(current_island_cells)
                distinct_islands.add(unique_island_string)

    # Return the number of distinct island shapes.
    return len(distinct_islands)

Big(O) Analysis

Time Complexity

O(M * N * log(M * N)) – Let M and N be the dimensions of the grid. Finding all islands involves iterating through each cell, which takes O(M * N) time. For each island of size k (where k <= M * N), generating all 8 transformations takes O(k) time. Normalizing and stringifying each transformation also takes O(k) time. Comparing the 8 string representations to find the lexicographically smallest one is O(k) as well. Finally, inserting the string representation into a set of strings takes O(log(number of islands)) time on average, which is bounded by O(log(M * N)). Since we need to do this for each island, and in the worst case, all the land cells could form one giant island, the overall time complexity is O(M * N) to find islands * O(M * N) to transform, normalize and stringify the island * O(log(M * N)) for the set insertion, which is O(M * N * log(M * N)).

Space Complexity

O(N) – The space complexity is determined by the auxiliary data structures used to store intermediate results. The algorithm uses a set to store unique island identifiers which in the worst-case scenario could potentially store all islands if they are distinct. Extracting each island involves storing coordinates, and generating transformations also uses space proportional to island size. Since the total number of cells in the grid is N, where N is rows * cols, in the worst-case each cell could belong to a distinct island, or one large island. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty grid	Return an empty list or appropriate error code indicating no islands if the input grid is null or empty.
Grid with all zeros (no land)	The algorithm should return an empty list because no islands exist.
Grid with only one cell as land (a single island)	The algorithm should correctly identify this single-cell island and its eight transformations.
Grid with a very large island, potentially causing stack overflow if recursion is used for DFS/BFS	Consider using an iterative approach for DFS/BFS to avoid stack overflow issues on very large islands.
Two islands are identical after rotation/reflection, but are initially at different locations	The solution must ensure that the normalized representations are identical to correctly identify them as the same island.
Integer overflow during coordinate transformations or centroid calculations	Use appropriate data types (e.g., long) to store coordinate values and calculations to prevent overflow.
Maximum grid size causing memory issues when storing island shapes or normalized forms	Optimize memory usage by efficiently representing island shapes (e.g., using relative coordinates) and avoid storing unnecessary data.
Island shapes that are symmetrical, potentially leading to duplicate normalized forms	The normalization process should generate a unique representation, even for symmetrical islands.

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 is the maximum size of the grid (rows and columns)?
Is the grid guaranteed to be rectangular (i.e., all rows have the same number of columns)?
By 'distinct islands', do we consider islands distinct if they have a different shape after rotation or reflection, or are islands with the same shape in different locations also considered distinct?
Can the grid be empty or null?
What should I return if the input grid is null or empty? Should I return 0, null, or throw an exception?

Brute Force Solution

Approach

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

Look at every single piece of land in the entire map.
Whenever you find a piece of land, try to trace out the whole island it belongs to.
Think of the island's shape as a set of directions you take to walk around it, starting from a specific spot.
Now, make copies of that island and rotate or flip them in every possible way (like turning a puzzle piece).
Compare each new island shape to all the island shapes you've found so far. If the new island, or any of its rotated or flipped copies, looks exactly like an island you've already saved, ignore it.
If none of the copies match any of the islands you've found before, then this is a brand new island shape. Save it.
Keep doing this for every piece of land in the map. At the end, you'll have a list of all the unique island shapes.

Code Implementation

def number_of_distinct_islands_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])
    islands = set()

    def explore_island(row, col, path, start_row, start_col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 0:
            return

        grid[row][col] = 0  # Mark as visited
        path.append((row - start_row, col - start_col))

        explore_island(row + 1, col, path, start_row, start_col)
        explore_island(row - 1, col, path, start_row, start_col)
        explore_island(row, col + 1, path, start_row, start_col)
        explore_island(row, col - 1, path, start_row, start_col)

    def normalize_island_shape(island_shape):
        normalized_shape = tuple(sorted(island_shape))
        return normalized_shape

    def generate_rotations_and_reflections(island_shape):
        rotated_and_reflected_shapes = set()
        for _ in range(4):
            # Rotate the island 90 degrees
            rotated_shape = [(y, -x) for x, y in island_shape]
            rotated_and_reflected_shapes.add(normalize_island_shape(rotated_shape))

            # Reflect the island along the x-axis
            reflected_shape = [(-x, y) for x, y in rotated_shape]
            rotated_and_reflected_shapes.add(normalize_island_shape(reflected_shape))

            island_shape = rotated_shape  # Update for next rotation

        return rotated_and_reflected_shapes

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                island_path = []

                # Find island and mark all visited lands
                explore_island(row, col, island_path, row, col)

                # Generate all rotations and reflections
                all_shapes = generate_rotations_and_reflections(island_path)

                is_unique = True
                for shape in all_shapes:
                    if shape in islands:

                        #If the shape is found skip to next landmass
                        is_unique = False
                        break

                if is_unique:

                    #if unique store shape to avoid duplicates
                    islands.add(normalize_island_shape(island_path))

    return len(islands)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find each island in the grid. An island is a group of connected land cells.
For each island, extract all its land cells' coordinates relative to a fixed point (e.g., the top-left cell of the island).
Generate all eight possible transformations of these coordinates: rotations (0, 90, 180, 270 degrees) and reflections (flipping over x and y axes) for each rotation.
For each transformation, shift the coordinates so that the minimum x and y values are both zero. This ensures consistency and removes dependency on the initial location of the island.
Convert each set of transformed coordinates into a string representation, like a list of cell pairs. This enables easy comparison.
Compare all eight string representations of each island and select the lexicographically smallest one. This becomes the unique identifier for that island's shape, regardless of its initial orientation.
Store the unique identifiers in a set. The size of this set represents the number of distinct island shapes.

Code Implementation

def number_of_distinct_islands_two(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0]) if number_of_rows > 0 else 0
    visited = set()
    distinct_islands = set()

    def explore_island(row, column, current_island_cells):
        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))
        current_island_cells.append((row, column))

        explore_island(row + 1, column, current_island_cells)
        explore_island(row - 1, column, current_island_cells)
        explore_island(row, column + 1, current_island_cells)
        explore_island(row, column - 1, current_island_cells)

    def normalize_island(island_cells):
        min_row = min(row for row, column in island_cells)
        min_column = min(column for row, column in island_cells)
        return [(row - min_row, column - min_column) for row, column in island_cells]

    def rotate_island(island_cells):
        return [(-column, row) for row, column in island_cells]

    def flip_island(island_cells):
        return [(row, -column) for row, column in island_cells]

    def get_island_string(island_cells):
        return str(sorted(island_cells))

    def get_unique_island_string(island_cells):
        unique_strings = set()
        for _ in range(4):
            unique_strings.add(get_island_string(normalize_island(island_cells)))
            unique_strings.add(get_island_string(normalize_island(flip_island(island_cells))))
            island_cells = rotate_island(island_cells)
        return min(unique_strings)

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1 and (row, column) not in visited:
                current_island_cells = []
                explore_island(row, column, current_island_cells)

                # Generating unique string representation
                unique_island_string = get_unique_island_string(current_island_cells)
                distinct_islands.add(unique_island_string)

    # Return the number of distinct island shapes.
    return len(distinct_islands)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return an empty list or appropriate error code indicating no islands if the input grid is null or empty.
Grid with all zeros (no land)	The algorithm should return an empty list because no islands exist.
Grid with only one cell as land (a single island)	The algorithm should correctly identify this single-cell island and its eight transformations.
Grid with a very large island, potentially causing stack overflow if recursion is used for DFS/BFS	Consider using an iterative approach for DFS/BFS to avoid stack overflow issues on very large islands.
Two islands are identical after rotation/reflection, but are initially at different locations	The solution must ensure that the normalized representations are identical to correctly identify them as the same island.
Integer overflow during coordinate transformations or centroid calculations	Use appropriate data types (e.g., long) to store coordinate values and calculations to prevent overflow.
Maximum grid size causing memory issues when storing island shapes or normalized forms	Optimize memory usage by efficiently representing island shapes (e.g., using relative coordinates) and avoid storing unnecessary data.
Island shapes that are symmetrical, potentially leading to duplicate normalized forms	The normalization process should generate a unique representation, even for symmetrical islands.