Java version, time complexity worst case O(n^2 log(n^2))


  • 0

    Record all the points along the path during DFS. Then add all the eight combinations of reflection, rotation into a array of points. From their, sort each list where time complexity would be O(n^2 * log(n^2)). Substract the first point's x and y value from all the points in the list, which identifies a shape uniquely.

    In Java, HashSet only compares hashCode() and equals() function so we have to convert the shape into a String and we only need to take the smallest string out of the eight combinations for uniqueness comparison.

    class Solution {
        private final int[] dir = {-1, 0, 1, 0, -1};
        private final int[][] refl = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        public int numDistinctIslands2(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            Set<String> set = new HashSet<>();
    
            List<Point> list = new ArrayList<>();
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    dfs(grid, i, j, list);
                    if (list.size() > 0) {
                        set.add(norm(list));
                        list.clear();
                    }
                }
            }
            return set.size();
        }
        
        private void dfs(int[][] grid, int row, int col, List<Point> list) {
            if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != 1) return;
            grid[row][col] = 2;
            list.add(new Point(row, col));
            for (int i = 0; i < 4; i++) {
                dfs(grid, row + dir[i], col + dir[i+1], list);
            }
        }
        
        @SuppressWarnings("unchecked")
    	private String norm(List<Point> list) {
            List<Point>[] comb = new List[8];
            
            for (int i = 0; i < 4; i++) {
                comb[i] = new ArrayList<Point>();
                comb[i+4] = new ArrayList<Point>();
                for (Point p : list) {
                    comb[i].add(new Point(p.x * refl[i][0], p.y * refl[i][1]));
                    comb[i+4].add(new Point(p.y * refl[i][1], p.x * refl[i][0]));
                }
            }
            
            for (int i = 0; i < 8; i++) {
            	Collections.sort(comb[i]);
            }
            String[] s = new String[8];
            for (int i = 0; i < 8; i++) {
               	StringBuilder sb = new StringBuilder();
                int x0 = comb[i].get(0).x, y0 = comb[i].get(0).y;
            	for (Point p : comb[i]) {
            		sb.append(p.x - x0);
                    sb.append(',');
                    sb.append(p.y - y0);
                    sb.append('!');
            	}
            	s[i] = sb.toString();
            }
            Arrays.sort(s);
            return s[0];
        }
        
        public static class Point implements Comparable<Point> {
            int x;
            int y;
            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
            @Override
            public int compareTo(Point p) {
                return this.x - p.x == 0 ? this.y - p.y : this.x - p.x;
            }
            @Override
            public String toString() {
                return String.format("(%d,%d)", this.x, this.y);
            }
        }
    }
    

    BFS version attached, DFS was tricky dealing with the worst test case.

        private final int[] dir = {-1, 0, 1, 0, -1};
        private final int[][] refl = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        public int numDistinctIslands2(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            Set<String> set = new HashSet<>();
    
            List<Point> list = new ArrayList<>();
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) bfs(grid, i, j, list);
                    if (list.size() > 0) {
                        set.add(norm(list));
                        list.clear();
                    }
                }
            }
            return set.size();
        }
        
        private void bfs(int[][] grid, int row, int col, List<Point> list) {
            Queue<Point> queue = new ArrayDeque<>();
            Point start = new Point(row, col);
            queue.add(start);
            list.add(start);
            grid[row][col] = 2;
            while (!queue.isEmpty()) {
                Point p = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int r = p.x + dir[i], c = p.y + dir[i+1];
                    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != 1) continue;
                    grid[r][c] = 2;
                    Point next = new Point(r, c);
                    list.add(next);
                    queue.add(next);
                }
            }
        }
        
        @SuppressWarnings("unchecked")
    	private String norm(List<Point> list) {
            List<Point>[] comb = new List[8];
            
            for (int i = 0; i < 4; i++) {
                comb[i] = new ArrayList<Point>();
                comb[i+4] = new ArrayList<Point>();
                for (Point p : list) {
                    comb[i].add(new Point(p.x * refl[i][0], p.y * refl[i][1]));
                    comb[i+4].add(new Point(p.y * refl[i][1], p.x * refl[i][0]));
                }
            }
            
            for (int i = 0; i < 8; i++) {
            	Collections.sort(comb[i]);
            }
            String[] s = new String[8];
            for (int i = 0; i < 8; i++) {
               	StringBuilder sb = new StringBuilder();
                int x0 = comb[i].get(0).x, y0 = comb[i].get(0).y;
            	for (Point p : comb[i]) {
            		sb.append(p.x - x0);
                    sb.append(',');
                    sb.append(p.y - y0);
                    sb.append('!');
            	}
            	s[i] = sb.toString();
            }
            Arrays.sort(s);
            return s[0];
        }
        
        public static class Point implements Comparable<Point> {
            int x;
            int y;
            public Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
            @Override
            public int compareTo(Point p) {
                return this.x - p.x == 0 ? this.y - p.y : this.x - p.x;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.