Count the Distinct Island Shapes
Solve this ProblemYou are given a grid of land (1) and water (0). Two islands have the same shape when one can be slid (without rotating or flipping) onto the other. Count how many different shapes of islands the grid contains.
Counting islands is a plain flood fill; the extra work is to turn each island into something comparable, such as a list of offsets from its first cell or a string that records how a depth-first search walks around it.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; grid[r][c] is 1 (land) or 0 (water) - ◆
An island is a group of land cells connected through shared sides - ◆
Two islands have the same shape when one can be moved (translated) onto the other; rotating or mirroring an island makes a different shape - ◆
Return the number of distinct island shapes
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Compare Each Island Cell-by-Cell With the Known Shapes
BruteFind each island with a flood fill and collect its cells. Sort them top-to-bottom, left-to-right and rewrite every cell as an offset from the first one, so that two islands that are copies of each other produce the same list. Then compare this list with every distinct shape found so far; add it only when it matches none. With K islands this compares up to K² lists of up to R·C numbers.
O(K · R·C) shape comparisonsO(R·C)1class Solution {
2 private List<Integer> flood(int[][] grid, boolean[][] seen, int sr, int sc) {
3 int rows = grid.length, cols = grid[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 List<Integer> keys = new ArrayList<>();
7 Deque<int[]> queue = new ArrayDeque<>();
8 seen[sr][sc] = true;
9 queue.add(new int[]{sr, sc});
10 while (!queue.isEmpty()) {
11 int[] cell = queue.poll();
12 keys.add(cell[0] * cols + cell[1]);
13 for (int d = 0; d < 4; d++) {
14 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
15 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !seen[nr][nc]) {
16 seen[nr][nc] = true;
17 queue.add(new int[]{nr, nc});
18 }
19 }
20 }
21 return keys;
22 }
23
24 public int countDistinctShapes(int[][] grid) {
25 int rows = grid.length, cols = grid[0].length;
26 boolean[][] seen = new boolean[rows][cols];
27 List<int[]> shapes = new ArrayList<>();
28 for (int r = 0; r < rows; r++) {
29 for (int c = 0; c < cols; c++) {
30 if (grid[r][c] == 1 && !seen[r][c]) {
31 List<Integer> keys = flood(grid, seen, r, c);
32 Collections.sort(keys);
33 int[] shape = new int[keys.size()];
34 for (int i = 0; i < shape.length; i++) {
35 shape[i] = (keys.get(i) / cols - r) * 40 + (keys.get(i) % cols - c) + 20;
36 }
37 boolean known = false;
38 for (int[] other : shapes) {
39 if (Arrays.equals(other, shape)) known = true;
40 }
41 if (!known) shapes.add(shape);
42 }
43 }
44 }
45 return shapes.size();
46 }
47}Optimal — Depth-First Signature Stored in a Set
OptimalExplore each island with a depth-first search that always tries the directions in the same fixed order, and record the path as a string: the letter of the direction you moved (d, u, r, l), then the signature of everything below it, then "b" when you return. The start is 'o'. Two islands with the same shape are explored in the same way, giving the same string, and different shapes give different strings (the "b" marks make the layout unambiguous). Store the strings in a set and return its size. Total length is proportional to the number of land cells: O(R·C).
O(R·C)O(R·C)1class Solution {
2 private void trace(int[][] grid, boolean[][] seen, int r, int c, char came, StringBuilder signature) {
3 int[] dr = {1, -1, 0, 0};
4 int[] dc = {0, 0, 1, -1};
5 char[] name = {'d', 'u', 'r', 'l'};
6 seen[r][c] = true;
7 signature.append(came);
8 for (int d = 0; d < 4; d++) {
9 int nr = r + dr[d], nc = c + dc[d];
10 if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1 && !seen[nr][nc]) {
11 trace(grid, seen, nr, nc, name[d], signature);
12 }
13 }
14 signature.append('b');
15 }
16
17 public int countDistinctShapes(int[][] grid) {
18 int rows = grid.length, cols = grid[0].length;
19 boolean[][] seen = new boolean[rows][cols];
20 Set<String> shapes = new HashSet<>();
21 for (int r = 0; r < rows; r++) {
22 for (int c = 0; c < cols; c++) {
23 if (grid[r][c] == 1 && !seen[r][c]) {
24 StringBuilder signature = new StringBuilder();
25 trace(grid, seen, r, c, 'o', signature);
26 shapes.add(signature.toString());
27 }
28 }
29 }
30 return shapes.size();
31 }
32}