Number of Distinct Islands using DFS

Given a 2D grid of size N x M consisting of '1's (land) and '0's (water), your task is to find the number of distinct islands. An island is a group of connected '1's (land) in 4 directions (horizontal and vertical). Two islands are considered distinct if and only if their shape (relative position of land cells) is different.

Understanding the Problem

We are given a 2D grid consisting of 0s and 1s. Here, '1' represents land, and '0' represents water. An island is a group of connected 1s in the grid, where connections are allowed only in four directions—up, down, left, and right.

Our goal is to count how many distinct island shapes exist. Two islands are considered the same if they have the same shape when shifted to the same origin. That means rotation and flipping do not count; only translation (shifting) is allowed when comparing shapes.

Step-by-Step Solution with Example

step 1: Traverse the grid to find unvisited land cells

We start scanning the grid from the top-left corner. When we encounter a cell with value 1 that hasn't been visited yet, it means we've found the start of a new island.

step 2: Perform DFS to explore the full island

From the current cell, we perform a Depth-First Search (DFS) in all four directions. For each direction we move, we add a corresponding character to a path string to encode the shape. For example, 'U' for up, 'D' for down, 'L' for left, 'R' for right.

step 3: Add backtracking information to avoid false matches

Every time we finish a recursive DFS call and go back to the previous cell, we add a special symbol, such as 'B' for backtrack. This helps us capture the exact structure of the island. For instance, a line and a zig-zag of the same length would produce different signatures.

step 4: Store the encoded shape in a set

Once the DFS is complete for an island, we add the shape signature to a set. This ensures we only keep unique shapes.

step 5: Count the number of unique shapes

At the end of the traversal, the number of distinct islands is simply the size of the set that stores the shape signatures.

Example

Input:
[
  [1,1,0,0,0],
  [1,0,0,0,0],
  [0,0,0,1,1],
  [0,0,0,1,1]
]

We find two islands:
- The first one on the top-left forms a shape with path: "DRB"
- The second one on the bottom-right has the same shape: "DRB"

Even though they are in different locations, their shapes are the same, so the output is: 1

Edge Cases

• Empty Grid: If the grid is empty, we return 0 since there are no islands.
• All Water: If every cell is 0, there’s no land to explore. Output is 0.
• All Land: If every cell is 1, there’s one big island. So, output is 1.
• Same Size but Different Shapes: If two islands have the same number of cells but different layouts, they are still considered distinct.
• Multiple Identical Shapes: If multiple islands have the same shape, they’re only counted once because we use a set to store unique patterns.

Finally

This problem helps build a strong foundation in graph traversal and pattern recognition. The key idea is not just visiting islands, but encoding their traversal paths uniquely to compare their shapes. Using DFS with shape encoding and backtracking gives us a reliable way to distinguish islands by structure.

Always consider boundary conditions and edge cases before finalizing your solution. Sets are a powerful way to track distinct patterns without worrying about duplicates.

1. Initialize an empty set shapes to store unique island signatures.
2. Iterate through each cell in the grid.
3. When a land cell ('1') is found that is not visited:
1. Start a DFS from that cell, marking visited cells.
2. Track the shape of the island by recording moves relative to the start cell.
3. Store the shape string in the shapes set.
4. Return the number of elements in shapes.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 50

int rows, cols;
int visited[MAX][MAX];
char path[MAX * MAX];
int pathIndex;

int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
char moves[] = {'R','D','L','U'};

void dfs(int grid[MAX][MAX], int r, int c, char start) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || grid[r][c] == 0) return;
    visited[r][c] = 1;
    path[pathIndex++] = start;
    for (int i = 0; i < 4; i++) {
        dfs(grid, r + directions[i][0], c + directions[i][1], moves[i]);
    }
    path[pathIndex++] = 'B';
}

int main() {
    int grid[MAX][MAX] = {
        {1,1,0,0},
        {1,0,0,0},
        {0,0,1,1},
        {0,0,0,1}
    };
    rows = 4;
    cols = 4;
    char shapes[100][MAX * MAX];
    int shapeCount = 0;

    memset(visited, 0, sizeof(visited));

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1 && !visited[r][c]) {
                pathIndex = 0;
                dfs(grid, r, c, 'S');
                path[pathIndex] = '\0';

                int isNew = 1;
                for (int i = 0; i < shapeCount; i++) {
                    if (strcmp(shapes[i], path) == 0) {
                        isNew = 0;
                        break;
                    }
                }
                if (isNew) strcpy(shapes[shapeCount++], path);
            }
        }
    }
    printf("Distinct Islands: %d\n", shapeCount);
    return 0;
}

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

void dfs(int r, int c, vector<vector<int>>& grid, vector<vector<bool>>& visited, string& path, char dir) {
    if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || visited[r][c] || grid[r][c] == 0) return;
    visited[r][c] = true;
    path += dir;
    dfs(r, c + 1, grid, visited, path, 'R');
    dfs(r + 1, c, grid, visited, path, 'D');
    dfs(r, c - 1, grid, visited, path, 'L');
    dfs(r - 1, c, grid, visited, path, 'U');
    path += 'B';
}

int numDistinctIslands(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    set<string> shapes;
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1 && !visited[r][c]) {
                string path = "S";
                dfs(r, c, grid, visited, path, 'S');
                shapes.insert(path);
            }
        }
    }
    return shapes.size();
}

int main() {
    vector<vector<int>> grid = {
        {1,1,0,0},
        {1,0,0,0},
        {0,0,1,1},
        {0,0,0,1}
    };
    cout << "Distinct Islands: " << numDistinctIslands(grid) << endl;
    return 0;
}

def num_distinct_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = [[False]*cols for _ in range(rows)]
    shapes = set()

    def dfs(r, c, path, direction):
        if r < 0 or c < 0 or r >= rows or c >= cols or visited[r][c] or grid[r][c] == 0:
            return
        visited[r][c] = True
        path.append(direction)
        dfs(r, c+1, path, 'R')
        dfs(r+1, c, path, 'D')
        dfs(r, c-1, path, 'L')
        dfs(r-1, c, path, 'U')
        path.append('B')

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visited[r][c]:
                path = []
                dfs(r, c, path, 'S')
                shapes.add(''.join(path))

    return len(shapes)

# Example Usage
grid = [
    [1,1,0,0],
    [1,0,0,0],
    [0,0,1,1],
    [0,0,0,1]
]
print("Distinct Islands:", num_distinct_islands(grid))

import java.util.*;

public class DistinctIslands {
    public static void main(String[] args) {
        int[][] grid = {
            {1,1,0,0},
            {1,0,0,0},
            {0,0,1,1},
            {0,0,0,1}
        };
        System.out.println("Distinct Islands: " + numDistinctIslands(grid));
    }

    public static int numDistinctIslands(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Set<String> shapes = new HashSet<>();

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    StringBuilder path = new StringBuilder();
                    dfs(grid, visited, r, c, 'S', path);
                    shapes.add(path.toString());
                }
            }
        }
        return shapes.size();
    }

    private static void dfs(int[][] grid, boolean[][] visited, int r, int c, char dir, StringBuilder path) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || visited[r][c] || grid[r][c] == 0) return;
        visited[r][c] = true;
        path.append(dir);
        dfs(grid, visited, r, c + 1, 'R', path);
        dfs(grid, visited, r + 1, c, 'D', path);
        dfs(grid, visited, r, c - 1, 'L', path);
        dfs(grid, visited, r - 1, c, 'U', path);
        path.append('B');
    }
}

function numDistinctIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  const shapes = new Set();

  const directions = [
    [0, 1, 'R'],
    [0, -1, 'L'],
    [1, 0, 'D'],
    [-1, 0, 'U']
  ];

  function dfs(r, c, path, dir) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || grid[r][c] === 0) return;
    visited[r][c] = true;
    path.push(dir);
    for (const [dr, dc, d] of directions) {
      dfs(r + dr, c + dc, path, d);
    }
    path.push('B');
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1 && !visited[r][c]) {
        const path = [];
        dfs(r, c, path, 'S');
        shapes.add(path.join(''));
      }
    }
  }

  return shapes.size;
}

console.log("Distinct Islands:", numDistinctIslands([
  [1,1,0,0],
  [1,0,0,0],
  [0,0,1,1],
  [0,0,0,1]
]));

// Go
package main

import (
  "fmt"
)

func numDistinctIslands(grid [][]int) int {
  rows, cols := len(grid), len(grid[0])
  visited := make([][]bool, rows)
  for i := range visited {
    visited[i] = make([]bool, cols)
  }

  shapes := make(map[string]bool)

  var dfs func(r, c int, path *[]byte, dir byte)
  dfs = func(r, c int, path *[]byte, dir byte) {
    if r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || grid[r][c] == 0 {
      return
    }
    visited[r][c] = true
    *path = append(*path, dir)
    dfs(r, c+1, path, 'R')
    dfs(r+1, c, path, 'D')
    dfs(r, c-1, path, 'L')
    dfs(r-1, c, path, 'U')
    *path = append(*path, 'B')
  }

  for r := 0; r < rows; r++ {
    for c := 0; c < cols; c++ {
      if grid[r][c] == 1 && !visited[r][c] {
        path := []byte{'S'}
        dfs(r, c, &path, 'S')
        shapes[string(path)] = true
      }
    }
  }

  return len(shapes)
}

func main() {
  grid := [][]int{
    {1, 1, 0, 0},
    {1, 0, 0, 0},
    {0, 0, 1, 1},
    {0, 0, 0, 1},
  }
  fmt.Println("Distinct Islands:", numDistinctIslands(grid))
}

// Rust
use std::collections::HashSet;

fn num_distinct_islands(grid: &mut Vec<Vec<i32>>) -> usize {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut shapes = HashSet::new();

    fn dfs(r: usize, c: usize, grid: &Vec<Vec<i32>>, visited: &mut Vec<Vec<bool>>, path: &mut String, dir: char) {
        if r >= grid.len() || c >= grid[0].len() || visited[r][c] || grid[r][c] == 0 {
            return;
        }
        visited[r][c] = true;
        path.push(dir);

        if r > 0 { dfs(r - 1, c, grid, visited, path, 'U'); }
        if r + 1 < grid.len() { dfs(r + 1, c, grid, visited, path, 'D'); }
        if c > 0 { dfs(r, c - 1, grid, visited, path, 'L'); }
        if c + 1 < grid[0].len() { dfs(r, c + 1, grid, visited, path, 'R'); }
        path.push('B');
    }

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == 1 && !visited[r][c] {
                let mut path = String::from("S");
                dfs(r, c, &grid, &mut visited, &mut path, 'S');
                shapes.insert(path);
            }
        }
    }
    shapes.len()
}

fn main() {
    let mut grid = vec![
        vec![1,1,0,0],
        vec![1,0,0,0],
        vec![0,0,1,1],
        vec![0,0,0,1],
    ];
    println!("Distinct Islands: {}", num_distinct_islands(&mut grid));
}

// Kotlin
fun numDistinctIslands(grid: Array<IntArray>): Int {
    val rows = grid.size
    val cols = grid[0].size
    val visited = Array(rows) { BooleanArray(cols) }
    val shapes = mutableSetOf<String>()

    fun dfs(r: Int, c: Int, path: StringBuilder, dir: Char) {
        if (r !in 0 until rows || c !in 0 until cols || visited[r][c] || grid[r][c] == 0) return
        visited[r][c] = true
        path.append(dir)
        dfs(r, c+1, path, 'R')
        dfs(r+1, c, path, 'D')
        dfs(r, c-1, path, 'L')
        dfs(r-1, c, path, 'U')
        path.append('B')
    }

    for (r in 0 until rows) {
        for (c in 0 until cols) {
            if (grid[r][c] == 1 && !visited[r][c]) {
                val path = StringBuilder("S")
                dfs(r, c, path, 'S')
                shapes.add(path.toString())
            }
        }
    }
    return shapes.size
}

fun main() {
    val grid = arrayOf(
        intArrayOf(1,1,0,0),
        intArrayOf(1,0,0,0),
        intArrayOf(0,0,1,1),
        intArrayOf(0,0,0,1)
    )
    println("Distinct Islands: ${numDistinctIslands(grid)}")
}

// Swift
func numDistinctIslands(_ grid: inout [[Int]]) -> Int {
    let rows = grid.count
    let cols = grid[0].count
    var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
    var shapes = Set<String>()

    func dfs(_ r: Int, _ c: Int, _ path: inout String, _ dir: Character) {
        if r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || grid[r][c] == 0 {
            return
        }
        visited[r][c] = true
        path.append(dir)
        dfs(r, c + 1, &path, "R")
        dfs(r + 1, c, &path, "D")
        dfs(r, c - 1, &path, "L")
        dfs(r - 1, c, &path, "U")
        path.append("B")
    }

    for r in 0..<rows {
        for c in 0..<cols {
            if grid[r][c] == 1 && !visited[r][c] {
                var path = "S"
                dfs(r, c, &path, "S")
                shapes.insert(path)
            }
        }
    }
    return shapes.count
}

var grid = [
    [1,1,0,0],
    [1,0,0,0],
    [0,0,1,1],
    [0,0,0,1]
]
print("Distinct Islands:", numDistinctIslands(&grid))

function numDistinctIslands(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));
  const shapes = new Set<string>();

  const directions: [number, number, string][] = [
    [0, 1, 'R'],
    [0, -1, 'L'],
    [1, 0, 'D'],
    [-1, 0, 'U']
  ];

  function dfs(r: number, c: number, path: string[], dir: string): void {
    if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || grid[r][c] === 0) return;
    visited[r][c] = true;
    path.push(dir);
    for (const [dr, dc, d] of directions) {
      dfs(r + dr, c + dc, path, d);
    }
    path.push('B');
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1 && !visited[r][c]) {
        const path: string[] = [];
        dfs(r, c, path, 'S');
        shapes.add(path.join(''));
      }
    }
  }

  return shapes.size;
}

console.log("Distinct Islands:", numDistinctIslands([
  [1,1,0,0],
  [1,0,0,0],
  [0,0,1,1],
  [0,0,0,1]
]));

Time complexity

Space complexity

O(m * n)

In the worst case, all cells are part of different islands, requiring separate shape strings and a visited matrix of the same size.