694. Number of distinct Islands
Tags:
Medium
Skills:
Matrix
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach
1 (Island), bắt đầu BFS từ ô đó0Time and space complexity
Solution - BFS
1function numDistinctIslands(grid: number[][]): number {
2 // current_position = [0][0]
3 // mapping_position = [n - 1][m - 1] or [n - 1][0] or [0][m - 1] with 0 is i
4 let n = grid.length;
5 let m = grid[0].length;
6 let directions = [
7 [1, 0], [-1, 0], [0, 1], [0, -1]
8 ]
9 let unique_island: Set<string> = new Set();
10
11 // with () -> string is shape of island
12 function bfs(row: number, col: number): string {
13 let queue: [number, number][] = [[row, col]]
14 const path: string[] = [];
15
16 grid[row][col] = 0;
17
18 while (queue.length > 0) {
19 const [r, c] = queue.shift()!
20
21 for (const [dr, dc] of directions) {
22 const new_row = r + dr;
23 const new_col = c + dc
24
25 if (new_row >= 0 && new_row < n && new_col >= 0 && new_col <= m && grid[new_row][new_col] === 1) {
26 grid[new_row][new_col] = 0
27 queue.push([new_row, new_col])
28 path.push(`${new_row - row}, ${new_col - col}`)
29 }
30 }
31 }
32 // console.log("PATH: ", path.join(';'))
33 return path.join(';')
34 }
35
36 for (let i = 0; i < n; i++) {
37 for (let j = 0; j < m; j++) {
38 if (grid[i][j] === 1) {
39 let path_string = bfs(i, j)
40 unique_island.add(path_string)
41 }
42 }
43 }
44
45 return unique_island.size;
46};