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.
Number of Distinct Islands Using DFS Shape Encoding - Visualization
Visualization Player
Problem Statement
Examples
Solution
Algorithm Steps
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}
Time Complexity
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(m * n) | Even in the best case, we must visit every cell to check if it's land or water and track unique shapes. |
Average Case | O(m * n) | Each cell is visited once, and DFS explores each connected component, tracking the shape. |
Worst Case | O(m * n) | In the worst case (e.g., entire grid is land), DFS explores all cells, and all must be encoded and compared. |
Comments
Loading comments...