Number of Distinct Islands

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 117 ms)

Metric	Value
Runtime	117 ms
Memory	39.3 MB
Date	2022-02-16

Solution

public class Solution {
    public int NumDistinctIslands(int[][] grid) {
        int m = grid.Length;
    int n = grid[0].Length;
    bool[,] used = new bool[m,n];
    HashSet<string> islands = new HashSet<string>();
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(grid[i][j] == 1 && !used[i,j])
            {
                List<char> path = new List<char>();
                Dfs(grid, i, j, m, n, used, path, ' ');
                islands.Add(new string(path.ToArray()).Trim());             
            }
        }
    }
    return islands.Count;
}

private void Dfs(int[][] grid, int i, int j, int m, int n, bool[,] used, List<char> path, char current)
{
    if(i<0 || i>=m || j<0 || j>=n || grid[i][j] == 0 || used[i,j])
    return;
    path.Add(current);
    used[i,j] = true;
    Dfs(grid, i - 1, j, m, n, used, path, 'u');
    Dfs(grid, i + 1, j, m, n, used, path, 'd');
    Dfs(grid, i, j-1, m, n, used, path, 'l');
    Dfs(grid, i, j+1, m, n, used, path, 'r');
    path.Add('b');
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed