LeetCode 711: Number of Distinct Islands II Solution
Master LeetCode problem 711 (Number of Distinct Islands II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
711. Number of Distinct Islands II
Problem Explanation
Explanation
To solve this problem, we can use the concept of transformations to represent each distinct island. We can apply transformations such as reflection, rotation, and translation to normalize each island. By doing this, we can compare the normalized representation of islands to identify distinct islands.
- Perform DFS to get the coordinates of each island.
- For each island, generate its different transformations.
- Normalize each transformation using a reference point (top-left corner) and store the normalized representation.
- Count the distinct normalized representations to find the number of distinct islands.
Time complexity: O(m * n * log(m*n)) - where m is the number of rows and n is the number of columns in the grid. Space complexity: O(m * n)
Solution Code
class Solution {
public int numDistinctIslands2(int[][] grid) {
Set<String> set = new HashSet<>();
List<List<int[]>> islands = new ArrayList<>();
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
List<int[]> island = new ArrayList<>();
dfs(grid, i, j, i, j, island);
islands.add(island);
}
}
}
for (List<int[]> island : islands) {
Set<String> normalized = new HashSet<>();
for (int[] start : island) {
List<int[]> shape = new ArrayList<>();
for (int[] p : island) {
int x = p[0] - start[0];
int y = p[1] - start[1];
shape.add(new int[]{x, y});
}
List<List<int[]>> transformations = getTransformations(shape);
for (List<int[]> t : transformations) {
normalized.add(normalize(t));
}
}
set.addAll(normalized);
}
return set.size();
}
private void dfs(int[][] grid, int i, int j, int i0, int j0, List<int[]> island) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1)
return;
island.add(new int[]{i - i0, j - j0});
grid[i][j] = 0;
dfs(grid, i + 1, j, i0, j0, island);
dfs(grid, i - 1, j, i0, j0, island);
dfs(grid, i, j + 1, i0, j0, island);
dfs(grid, i, j - 1, i0, j0, island);
}
private List<List<int[]>> getTransformations(List<int[]> shape) {
List<List<int[]>> transformations = new ArrayList<>();
for (int i = 0; i < 4; i++) {
transformations.add(new ArrayList<>());
}
for (int[] p : shape) {
int x = p[0], y = p[1];
transformations.get(0).add(new int[]{x, y});
transformations.get(1).add(new int[]{x, -y});
transformations.get(2).add(new int[]{-x, y});
transformations.get(3).add(new int[]{-x, -y});
}
return transformations;
}
private String normalize(List<int[]> shape) {
List<int[]> normalizedShape = new ArrayList<>(shape);
Collections.sort(normalizedShape, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int deltaX = -normalizedShape.get(0)[0];
int deltaY = -normalizedShape.get(0)[1];
for (int[] p : normalizedShape) {
p[0] += deltaX;
p[1] += deltaY;
}
StringBuilder sb = new StringBuilder();
for (int[] p : normalizedShape) {
sb.append(p[0]).append(",").append(p[1]).append(";");
}
return sb.toString();
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 711 (Number of Distinct Islands II)?
This page provides optimized solutions for LeetCode problem 711 (Number of Distinct Islands II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 711 (Number of Distinct Islands II)?
The time complexity for LeetCode 711 (Number of Distinct Islands II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 711 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 711 in Java, C++, or Python.