G-16. Number of Distinct Islands | Constructive Thinking + DFS

This chapter covers how to solve the classic Number of Distinct Islands problem using Depth-First Search (DFS) combined with a relative coordinate transformation technique (Constructive Thinking) to identify and count unique island shapes in a boolean 2D matrix.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given a boolean 2D matrix of size $N \times M$ (where 1 represents land and 0 represents water), we need to find the number of distinct islands.

Connectivity: Two cells form an island if they are connected horizontally or vertically (diagonal connections do not count).
Distinctness Criterion: Two islands are considered identical if and only if one can be translated (shifted) exactly onto the other without any rotation or reflection.

Status Quo / Naive Failure

In standard problems like Number of Islands, we only count how many connected components exist by marking visited cells. However, two separate islands might have the exact same shape and size, but appear at different locations in the matrix, or even look identical while being rotated.

If we simply count components, separate islands with the same shape would be double-counted.
If we try to compare raw global coordinates (e.g., (0,0), (0,1), (1,0) vs (2,3), (2,4), (3,3)), they will appear completely different to a set data structure.

2. Core Mental Model & The Relative Coordinate Trick

To determine if two island shapes are identical, we must make their coordinates translation-invariant.

Real-Life Analogy: The Blueprint Grid

Imagine drawing an island shape on a transparent grid sheet. If you pick up that transparent sheet and place it anywhere else on the table, the shape is identical as long as you haven't rotated or flipped it.

To store this shape in a data structure (like a Set) so that identical shapes collide and are counted only once, we establish a Base Coordinate (Starting Point) for every island traversal:

The cell where our DFS/BFS first enters the island is designated as the base coordinate (base_row, base_col).
Every subsequent cell visited within that same island is recorded relative to the base:

\text{Stored Coordinate} = (\text{current\_row} - \text{base\_row},\ \text{current\_col} - \text{base\_col})

3. Step-by-Step Coordinate Normalization Example

Let us trace two identical diagonal-ish islands located at different spots in a matrix:

Island A (Starts at `(0, 0)`)

Absolute coordinates visited during traversal:

(0, 0) -> Base coordinate
(0, 1)
(1, 0)

Applying Relative Subtraction (- base (0,0)):

(0 - 0, 0 - 0) -> (0, 0)
(0 - 0, 1 - 0) -> (0, 1)
(1 - 0, 0 - 0) -> (1, 0)

Stored List for Island A: [(0,0), (0,1), (1,0)]

Island B (Starts at `(2, 3)`)

Absolute coordinates visited during traversal:

(2, 3) -> Base coordinate
(2, 4)
(3, 3)

Applying Relative Subtraction (- base (2,3)):

(2 - 2, 3 - 3) -> (0, 0)
(2 - 2, 4 - 3) -> (0, 1)
(3 - 2, 3 - 3) -> (1, 0)

Stored List for Island B: [(0,0), (0,1), (1,0)]

Because both islands yield the exact same relative coordinate sequence [(0,0), (0,1), (1,0)], inserting them into a Set data structure will automatically treat them as duplicate entries, retaining only one unique island count!

4. Importance of Strict Traversal Order

If two islands have the same shape, their relative coordinate lists will only match if we traverse their cells in the exact same directional order.

If DFS checks neighbors in a mismatched order (e.g., checking Left then Right in one island, but Right then Left in another), the generated lists will differ, leading to false distinct counts.

Standard Directional Priority Array

To guarantee deterministic traversal across all islands, fix a strict traversal priority—for example: Up, Right, Down, Left (or Right, Down, Left, Up).

CODE

Traversal Direction Order:
   1. Up    (row - 1, col)
   2. Right (row,     col + 1)
   3. Down  (row + 1, col)
   4. Left  (row,     col - 1)

5. Complete Flow Walkthrough

Structure & Concept Flow

Matrix Scan (Row 0 -> N-1, Col 0 -> M-1)

+--> Is cell grid[i][j] == 1 AND Unvisited?

|-- YES --> Initialize empty list (vec)

| Record base coordinates: base_row = i, base_col = j

| Trigger DFS(i, j, base_row, base_col, grid, visited, vec)

DFS Execution:

- Mark current cell as visited(1)

- Push (i - base_row, j - base_col) into vec

- Loop through 4 directions (Up, Right, Down, Left)

- Recursively visit valid unvisited land neighbors

DFS Completes for Island:

- Insert list (vec) into a Set data structure (automatic duplicate filtering)

Return Set.size() -> Total Count of Distinct Islands

6. Java & C++ Implementation Code

Java Implementation

JAVA

import java.util.*;

class Solution {
    private void dfs(int row, int col, int baseRow, int baseCol, 
                     int[][] grid, int[][] visited, ArrayList<String> vec) {
        
        visited[row][col] = 1;
        
        // Store relative coordinates as a formatted string or pair
        vec.add(toString(row - baseRow, col - baseCol));
        
        int n = grid.length;
        int m = grid[0].length;
        
        // Delta arrays for Up, Right, Down, Left
        int[] delRow = {-1, 0, 1, 0};
        int[] delCol = {0, 1, 0, -1};
        
        for (int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            if (nRow >= 0 && nRow < n && nCol >= 0 && nCol < m 
                && visited[nRow][nCol] == 0 && grid[nRow][nCol] == 1) {
                dfs(nRow, nCol, baseRow, baseCol, grid, visited, vec);
            }
        }
    }
    
    private String toString(int r, int c) {
        return Integer.toString(r) + " " + Integer.toString(c);
    }

    public int countDistinctIslands(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] visited = new int[n][m];
        
        Set<ArrayList<String>> st = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j] == 0 && grid[i][j] == 1) {
                    ArrayList<String> vec = new ArrayList<>();
                    dfs(i, j, i, j, grid, visited, vec);
                    st.add(vec);
                }
            }
        }
        return st.size();
    }
}

C++ Implementation

C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    void dfs(int row, int col, int baseRow, int baseCol, 
             vector<vector<int>>& grid, vector<vector<int>>& visited, 
             vector<pair<int, int>>& vec) {
        
        visited[row][col] = 1;
        
        // Store relative coordinates
        vec.push_back({row - baseRow, col - baseCol});
        
        int n = grid.size();
        int m = grid[0].size();
        
        int delRow[] = {-1, 0, 1, 0};
        int delCol[] = {0, 1, 0, -1};
        
        for (int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            if (nRow >= 0 && nRow < n && nCol >= 0 && nCol < m 
                && !visited[nRow][nCol] && grid[nRow][nCol] == 1) {
                dfs(nRow, nCol, baseRow, baseCol, grid, visited, vec);
            }
        }
    }

public:
    int countDistinctIslands(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> visited(n, vector<int>(m, 0));
        
        set<vector<pair<int, int>>> st;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    vector<pair<int, int>> vec;
                    dfs(i, j, i, j, grid, visited, vec);
                    st.insert(vec);
                }
            }
        }
        return st.size();
    }
};

7. Complexity Analysis

Complexity Type	Analysis	Explanation
Time Complexity	$O(N \times M \times 4 + N \times M \log(N \times M))$	Matrix traversal visits every cell once ( $N \times M$ ). The DFS explores up to 4 neighbors per cell. Inserting each island's coordinate vector into the set takes logarithmic time relative to the number of stored unique shapes (at most $N \times M$ elements).
Space Complexity	$O(N \times M)$	The `visited` matrix requires $N \times M$ space, and the set data structure stores coordinate vectors proportional to total grid cells in the worst-case scenario.

Summary and Key Takeaways

Problem Core: Finding unique island shapes requires identifying connected components while filtering out identical shapes situated at different matrix offsets.
Base Coordinate Subtraction: Subtracting the starting entry cell coordinate (base_row, base_col) from all cells visited during traversal normalizes island shapes, making them translation-invariant.
Consistent Traversal Order: Always enforce a strict directional order (e.g., Up, Right, Down, Left) during DFS/BFS to ensure that identical island shapes always generate identical coordinate sequences.
Set Data Structure Utility: Storing normalized coordinate lists in a Set automatically handles deduplication, leaving only distinct island configurations.
Graph Traversal Foundation: Builds directly upon standard graph traversal concepts like Connected Components and Matrix DFS.