711. Number of Distinct Islands II

HardDepth-First SearchBreadth-First SearchUnion FindHash TableHash Function

Problem Description

In this problem, you are given a binary matrix grid, representing a map where 1s indicate land, and 0s represent water. An island is defined as a contiguous group of 1s that are directly connected horizontally or vertically. The task is to determine the number of distinct islands in the grid.

However, there's a twist. Two islands are considered the same if one can be transformed into the other through rotation (90, 180, or 270 degrees) or reflection (flipping over a horizontal or vertical line). We are not simply counting the islands, but we are identifying distinct shapes of islands considering these transformations.

The goal is to return the total number of unique island shapes that exist in the given grid, taking into account the possible rotations and reflections that might make two seemingly different islands actually the same.

Intuition

To approach this problem, we focus on identifying all islands first, and then transform each island into a canonical form that represents its shape. By comparing these canonical shapes, we can determine which islands are unique.

We use a Depth-First Search (DFS) algorithm to explore the grid and identify each island. Starting at a cell with a 1, we perform DFS to visit all land cells that are part of the same island. While visiting, we mark the cells as 0 to avoid revisiting and to help in identifying separate islands.

Once we have an island, the key challenge is determining its unique shape. We generate all possible rotations and reflections of the shape, normalize them by sorting and shifting to have the top-left coordinate at (0,0), and then choose the smallest one in sorted order as the canonical representative of that shape.

We store these canonical representatives in a set to automatically handle the uniqueness aspect—since sets only store unique items, any duplicate shapes will be ignored.

The final count of distinct islands is the size of this set, as it only contains unique shapes.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

A graph is a special treeA tree is a special graphNo relationshipThey are the same thing

I don’t know

Solution Approach

The solution utilizes Depth-First Search (DFS) for graph traversal, set data structure to keep track of unique islands, and normalizes the islands for comparison.

Depth-First Search (DFS): The dfs function takes in the starting cell (i, j) along with a shape list that accumulates the cells that form part of the current island. Each call to dfs visits a new land cell, marks it as 0 by overwriting grid[i][j] to prevent revisiting, and recursively explores the four adjacent cells (up, down, left, right) for further land cells.
Normalization: The normalization process takes the shape of an island obtained from the dfs and generates all possible rotations and reflections. This is done by permuting the cell coordinates (i, j) as described in the code (e.g., shapes[0].append([i, j]) for the original shape, shapes[1].append([i, -j]) for a reflection, etc.). The 8 different transformations correspond to 4 rotations (0, 90, 180, 270 degrees) and their mirrored reflections.
Canonical Representation: After generating all transformations of an island's shape, each transformation is sorted to place the cells in a consistent order. Then, the coordinates are adjusted by subtracting the coordinates of the first cell (e[0][0], e[0][1]) from all cells to ensure that the 'top-left' cell of the shape is brought to (0,0). Among all permutations, the lexicographically smallest is selected as the canonical shape.
Unique Shapes: To determine the distinct islands, we store the canonical representations in a set s. Since a set naturally eliminates duplicates, adding the normalized shape of each island to the set helps us in only keeping unique islands.
Counting Distinct Islands: After iterating over every cell in the grid and performing the above steps for each 1 encountered, the number of distinct islands is simply the number of entries in the set s, which can be returned as len(s).

To sum up, the algorithm performs DFS to identify islands, uses permutations and sorting to normalize shapes, and leverages a set to count distinct islands, taking care of rotations and reflections without explicitly comparing each pair of islands. The resulting algorithm efficiently finds and groups islands with identical shapes, satisfying the conditions posed by the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Example Walkthrough

Let's use a small 3x4 grid example to illustrate the solution approach:

1grid = [
2    [1, 1, 0, 0],
3    [0, 1, 0, 1],
4    [1, 0, 0, 1]
5]

This grid contains three pieces of land. However, not all these land parcels are distinct islands based on the given problem's criteria of rotations and reflections. Let's walk through the solution step by step, as outlined in the problem's solution approach.

We start with the Depth-First Search (DFS) at the top left of the grid. The DFS will identify the first island (top-left corner) and mark it visited by setting those 1s to 0s:

1grid after DFS = [
2    [0, 0, 0, 0],
3    [0, 0, 0, 1],
4    [1, 0, 0, 1]
5]

The shape list for this island will be [(0,0), (0,1), (1,1)].

The algorithm then generates all rotations and reflections of the shape list to obtain a set of potentially unique shapes:

Original shape: [(0,0), (0,1), (1,1)]
Rotate 90 degrees: [(0,0), (1,0), (1,-1)]
Rotate 180 degrees: [(0,0), (0,-1), (-1,-1)]
Rotate 270 degrees: [(0,0), (-1,0), (-1,1)]
Reflect horizontally: [(0,0), (0,-1), (1,-1)]
And more reflections from the above rotations.

The canonical representation would normalize these shapes and select the lexicographically smallest one. This often means the coordinates are shifted so that the first cell in all permutations is at (0,0), and then sorted. Let's assume the canonical shape for the first island is [(0,0), (0,-1), (1,-1)].
Now, we move to the next unvisited cell with a 1, at (1,3), and repeat the process of DFS to mark it visited, finding the second distinct island:

1grid after the second DFS = [
2    [0, 0, 0, 0],
3    [0, 0, 0, 0],
4    [1, 0, 0, 0]
5]

The shape list for the second island will be [(1,3)].

Since it's a single cell, all rotations and reflections will give the same shape list, which is already in its smallest canonical form.
The third island at (2,0) will yield the same shape list as the second island after going through DFS, rotations, reflections, and normalization. So, its canonical shape is [(0,0)].
Throughout, we add these canonical forms to a set to track unique shapes. Once we've visited all cells, the set will contain:

1{
2    [(0,0), (0,-1), (1,-1)],  // Canonical form of the first island
3    [(0,0)]  // Canonical form of the second (and third) island
4}

The final count of distinct islands for our example is the size of this set s, which is 2. Thus, the algorithm would return 2 for this example grid.

In conclusion, through DFS, normalizing with rotations and reflections, and using a set to keep track of unique island shapes, the algorithm effectively identifies the number of distinct islands in the grid.

Solution Implementation

1class Solution:
2    def numDistinctIslands2(self, grid: List[List[int]]) -> int:
3      
4        # Depth-First Search function to explore an island and record its shape
5        def dfs(row, col, shape):
6            shape.append((row, col))
7            grid[row][col] = 0  # Mark the land as visited
8            # Explore all 4 directions: up, down, left, right
9            for delta_row, delta_col in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
10                new_row, new_col = row + delta_row, col + delta_col
11                if 0 <= new_row < num_rows and 0 <= new_col < num_cols and grid[new_row][new_col] == 1:
12                    dfs(new_row, new_col, shape)
13
14        # Function to normalize the shapes by considering all 8 transformations
15        def normalize(shape):
16            # Create 8 transformations for each shape
17            all_transformations = [[] for _ in range(8)]
18            for x, y in shape:
19                all_transformations[0].append((x, y))
20                all_transformations[1].append((x, -y))
21                all_transformations[2].append((-x, y))
22                all_transformations[3].append((-x, -y))
23                all_transformations[4].append((y, x))
24                all_transformations[5].append((y, -x))
25                all_transformations[6].append((-y, x))
26                all_transformations[7].append((-y, -x))
27          
28            # Normalize by sorting and then subtracting the first pair to bring to origin
29            for transformation in all_transformations:
30                transformation.sort()
31                origin_x, origin_y = transformation[0]
32                for i in range(len(transformation)):
33                    transformation[i] = (transformation[i][0] - origin_x, transformation[i][1] - origin_y)
34          
35            # Sort the transformations and keep the first one to represent this shape
36            all_transformations.sort()
37            return tuple(all_transformations[0])
38
39        # Initialize variables and a set to store unique island shapes
40        num_rows, num_cols = len(grid), len(grid[0])
41        unique_islands = set()
42      
43        # Iterate over each cell in the grid
44        for row in range(num_rows):
45            for col in range(num_cols):
46                if grid[row][col]:  # If the cell is a land
47                    shape = []
48                    dfs(row, col, shape)  # Perform DFS to get the shape of the island
49                    unique_islands.add(normalize(shape))  # Normalize and add to set of unique islands
50      
51        # Return the number of unique island shapes
52        return len(unique_islands)
53

1class Solution {
2    // Dimensions of the grid
3    private int rows;
4    private int cols;
5    // The 2D grid itself
6    private int[][] grid;
7
8    // Method to count the number of distinct islands
9    public int numDistinctIslands2(int[][] grid) {
10        rows = grid.length;
11        cols = grid[0].length;
12        this.grid = grid;
13        Set<List<List<Integer>>> uniqueIslands = new HashSet<>();
14      
15        // Iterate over each cell in the grid
16        for (int i = 0; i < rows; ++i) {
17            for (int j = 0; j < cols; ++j) {
18                // If the cell is a part of an island (land)
19                if (grid[i][j] == 1) {
20                    List<Integer> islandShape = new ArrayList<>();
21                    // Use DFS to mark the visited cells and capture the island's shape
22                    dfs(i, j, islandShape);
23                    // Normalize the shape to its canonical form and add it to the set
24                    uniqueIslands.add(normalize(islandShape));
25                }
26            }
27        }
28        // Returns the number of unique islands
29        return uniqueIslands.size();
30    }
31
32    // Normalizes the shape of an island to identify it uniquely
33    private List<List<Integer>> normalize(List<Integer> shape) {
34        List<int[]>[] allTransformations = new List[8];
35      
36        // Initialize lists for all the transformations
37        for (int i = 0; i < 8; ++i) {
38            allTransformations[i] = new ArrayList<>();
39        }
40
41        // Generate all possible transformations for the island shape
42        for (int code : shape) {
43            int row = code / cols;
44            int col = code % cols;
45            allTransformations[0].add(new int[] {row, col});
46            allTransformations[1].add(new int[] {row, -col});
47            allTransformations[2].add(new int[] {-row, col});
48            allTransformations[3].add(new int[] {-row, -col});
49            allTransformations[4].add(new int[] {col, row});
50            allTransformations[5].add(new int[] {col, -row});
51            allTransformations[6].add(new int[] {-col, row});
52            allTransformations[7].add(new int[] {-col, -row});
53        }
54
55        // Normalize each transformation by sorting and repositioning
56        for (List<int[]> transformation : allTransformations) {
57            // Sort by coordinates
58            transformation.sort((a, b) -> 
59                a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]
60            );
61          
62            // Reposition the transformation so it starts at the origin (0,0)
63            int baseRow = transformation.get(0)[0];
64            int baseCol = transformation.get(0)[1];
65            for (int k = transformation.size() - 1; k >= 0; --k) {
66                int[] coords = transformation.get(k);
67                coords[0] -= baseRow;
68                coords[1] -= baseCol;
69                transformation.set(k, coords);
70            }
71        }
72
73        // Sort the transformations to find the canonical form (the smallest)
74        Arrays.sort(allTransformations, (a, b) -> {
75            for (int k = 0; k < a.size(); ++k) {
76                int[] coordsA = a.get(k);
77                int[] coordsB = b.get(k);
78                if (coordsA[0] != coordsB[0]) {
79                    return coordsA[0] - coordsB[0];
80                }
81                if (coordsA[1] != coordsB[1]) {
82                    return coordsA[1] - coordsB[1];
83                }
84            }
85            return 0;
86        });
87
88        // Convert the smallest transformation to a List of Lists and return
89        List<List<Integer>> canonicalShape = new ArrayList<>();
90        for (int[] coords : allTransformations[0]) {
91            canonicalShape.add(Arrays.asList(coords[0], coords[1]));
92        }
93        return canonicalShape;
94    }
95
96    // Helper DFS method to explore the island
97    private void dfs(int row, int col, List<Integer> islandShape) {
98        // Encode the current cell as a single integer and add to island shape
99        islandShape.add(row * cols + col);
100        // Mark the cell as visited by setting it to 0
101        grid[row][col] = 0;
102        // Directions for exploring adjacent cells
103        int[] dirs = {-1, 0, 1, 0, -1};
104      
105        // Explore all four directions
106        for (int k = 0; k < 4; ++k) {
107            int nextRow = row + dirs[k];
108            int nextCol = col + dirs[k + 1];
109            // Continue DFS if the next cell is valid and part of the island
110            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1) {
111                dfs(nextRow, nextCol, islandShape);
112            }
113        }
114    }
115}
116

1#include <vector>
2#include <set>
3#include <algorithm>
4using namespace std;
5
6typedef pair<int, int> Point;
7
8class Solution {
9public:
10    // Counts the distinct islands in the grid
11    int numDistinctIslands2(vector<vector<int>>& grid) {
12        set<vector<Point>> uniqueShapes;
13        for (int row = 0; row < grid.size(); ++row) {
14            for (int col = 0; col < grid[0].size(); ++col) {
15                if (grid[row][col]) {
16                    vector<Point> shape;
17                    depthFirstSearch(row, col, grid, shape);
18                    uniqueShapes.insert(normalizeShape(shape));
19                }
20            }
21        }
22        return uniqueShapes.size();
23    }
24
25    // Normalizes the shape of an island to remove duplicates that are rotations or reflections of each other
26    vector<Point> normalizeShape(vector<Point>& shape) {
27        vector<vector<Point>> shapes(8);
28        for (auto& point : shape) {
29            int x = point.first, y = point.second;
30            shapes[0].push_back({x, y});
31            shapes[1].push_back({x, -y});
32            shapes[2].push_back({-x, y});
33            shapes[3].push_back({-x, -y});
34            shapes[4].push_back({y, x});
35            shapes[5].push_back({y, -x});
36            shapes[6].push_back({-y, -x});
37            shapes[7].push_back({-y, x});
38        }
39      
40        for (auto& e : shapes) {
41            sort(e.begin(), e.end());
42            int baseX = e[0].first, baseY = e[0].second;
43            for (auto& point : e) {
44                point.first -= baseX;
45                point.second -= baseY;
46            }
47        }
48      
49        sort(shapes.begin(), shapes.end());
50        return shapes[0];
51    }
52
53    // Performs a depth-first search to find the entire shape of an island
54    void depthFirstSearch(int x, int y, vector<vector<int>>& grid, vector<Point>& shape) {
55        static const vector<int> directions = {-1, 0, 1, 0, -1}; // Used to explore adjacent cells
56        shape.push_back({x, y});
57        grid[x][y] = 0; // Mark as visited
58      
59        for (int k = 0; k < 4; ++k) {
60            int nextX = x + directions[k], nextY = y + directions[k + 1];
61            if (nextX >= 0 && nextX < grid.size() && nextY >= 0 && nextY < grid[0].size() && grid[nextX][nextY] == 1) {
62                depthFirstSearch(nextX, nextY, grid, shape); // Recursive DFS call
63            }
64        }
65    }
66};
67

1type Point = [number, number]; // Represent a point as a tuple of [x, y] coordinates
2
3// Counts the distinct islands in the grid
4function numDistinctIslands2(grid: number[][]): number {
5    const uniqueShapes: Set<string> = new Set();
6    for (let row = 0; row < grid.length; ++row) {
7        for (let col = 0; col < grid[0].length; ++col) {
8            if (grid[row][col]) {
9                const shape: Point[] = [];
10                depthFirstSearch(row, col, grid, shape);
11                uniqueShapes.add(JSON.stringify(normalizeShape(shape)));
12            }
13        }
14    }
15    return uniqueShapes.size;
16}
17
18// Normalizes the shape of an island to remove duplicates that are rotations or reflections of each other
19function normalizeShape(shape: Point[]): Point[] {
20    const shapes: Point[][] = Array.from({ length: 8 }, () => []);
21    for (const point of shape) {
22        const [x, y] = point;
23        shapes[0].push([x, y]);
24        shapes[1].push([x, -y]);
25        shapes[2].push([-x, y]);
26        shapes[3].push([-x, -y]);
27        shapes[4].push([y, x]);
28        shapes[5].push([y, -x]);
29        shapes[6].push([-y, -x]);
30        shapes[7].push([-y, x]);
31    }
32  
33    for (const e of shapes) {
34        e.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]); // Sort the points
35        const [baseX, baseY] = e[0];
36        e.forEach(point => {
37            point[0] -= baseX;
38            point[1] -= baseY;
39        });
40    }
41  
42    shapes.sort(); // Sort the shapes to get the canonical representation
43    return shapes[0]; // Return the first shape, which is the normalized shape
44}
45
46// Performs a depth-first search to find the entire shape of an island
47function depthFirstSearch(x: number, y: number, grid: number[][], shape: Point[]): void {
48    const directions: number[] = [-1, 0, 1, 0, -1]; // Used to explore adjacent cells
49    shape.push([x, y]);
50    grid[x][y] = 0; // Mark as visited
51  
52    for (let k = 0; k < 4; ++k) {
53        const nextX = x + directions[k];
54        const nextY = y + directions[k + 1];
55        if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && grid[nextX][nextY] === 1) {
56            depthFirstSearch(nextX, nextY, grid, shape); // Recursive DFS call
57        }
58    }
59}
60
61// Note: TypeScript doesn't have direct support for set of objects based on value equality.
62// Therefore, to store shapes in a set, shapes are first converted to string with JSON.stringify.
63

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down as followed:

DFS (dfs function) traversal for every island: The DFS function may visit each cell in the grid up to 8 times due to considering all permutations of rotations and reflections (since normalize will iterate over all possible transformations). The outer loop (nested loop over grid) will go through all cells m * n, but an individual cell belongs to at most one island and once it's part of an island, it is marked as visited (grid[i][j] = 0). Thus, every cell is part of the DFS process at most once, so the complexity of this portion is O(m * n).
Normalization (normalize function) and addition to the set: For each island found, we create up to 8 normalized shapes. Each shape is then sorted, which takes O(k log k) time where k is the number of cells in a given island. This is multiplied by 8 (for the 8 shapes), and the complexity for each island is O(8 * k log k). However, since k can be at most m * n, and each cell is processed exactly once, if we sum it up for all islands, the upper bound across the entire grid remains O(m * n log (m * n)).
Sorting the normalized shapes: This is part of the normalization but sorting the list of shapes for an island contributes O(8 log 8) time, which is constant and can be simplified to O(1).
Operations for the set: Each normalized shape is added to a set. Assuming a good hash function with few collisions, this operation can be considered O(1) on average for each shape. Since there's a bounded number of unique shapes we can have, this does not significantly contribute to the overall time complexity.

Combining these points, the overall time complexity of the algorithm is dominated by the DFS and normalization steps, giving O(m * n log (m * n)).

Space Complexity

The space complexity can be analyzed as follows:

Grid alteration: The input grid is modified in place, so there is no additional space needed proportional to the size of the grid.
Recursive stack: In the worst case, the recursive stack for DFS can go as deep as the size of the grid if the grid is one large island, which is O(m * n).
Shape storage: Shapes are stored, and their size can be up to the full size of the grid in a pathological case where the entire grid is one island, which also takes O(m * n) space.
Set of islands: The number of unique shapes is stored, and while there could be a large number of permutations, they are ultimately constrained by the grid size. So the space taken up by all unique shapes in the set is O(m * n).

As a result, the overall space complexity is O(m * n) due to the storage of the shapes, the set of unique shapes, and the recursion stack for DFS.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

711. Number of Distinct Islands II

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings