Given an R×C binary grid where 1 represents land and 0 represents water, return the number of distinct island shapes.
An island is formed by horizontal and vertical connections between land cells. Two islands are equal only when one island can be shifted up, down, left, or right to match the other island exactly. Rotation and reflection do not create equality.
number of distnct islands
Example 1
Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 1
Explanation: Both islands form the same 2×2 square shape after shifting to a common origin.
Example 2
Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3
Explanation: The grid contains multiple islands, and only repeated translated shapes collapse into one distinct shape.
Approach 1
Depth First Search explores an entire island from the first unvisited land cell encountered during row-major traversal. The starting cell acts as the base position, and every island cell is recorded using an offset from the base.
Relative coordinates remove positional differences between translated islands. A fixed traversal order creates consistent signatures for identical shapes, while a hash set retains only unique signatures.
Algorithm
Initialize an empty hash set to store unique island signatures.
Traverse the grid using an outer loop for rows and an inner loop for columns, ensuring every cell is examined.
Upon finding a land cell, store the current position as the base and start DFS to explore the complete island.
During DFS, mark each visited land cell as water to prevent repeated processing.
Record each visited cell as
(row-baseRow, col-baseCol), removing positional differences while preserving the island shape.Explore neighboring land cells in a fixed directional order and convert all collected coordinates into an unambiguous signature.
Insert the signature into the hash set and return the set size after the complete grid traversal.
Dry Run
DFS
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to collect one island signature using DFS. void dfs(int row, int col, int baseRow, int baseCol, vector<vector<int>>& grid, vector<string>& shape) { int rows = grid.size(); int cols = grid[0].size(); // Stop for invalid cells and water cells. if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0) { return; } // Mark current land cell as visited. grid[row][col] = 0; // Store relative position from island start. shape.push_back(to_string(row - baseRow) + ":" + to_string(col - baseCol)); // Visit all four neighboring cells. dfs(row - 1, col, baseRow, baseCol, grid, shape); dfs(row + 1, col, baseRow, baseCol, grid, shape); dfs(row, col - 1, baseRow, baseCol, grid, shape); dfs(row, col + 1, baseRow, baseCol, grid, shape); }public: // Function to count distinct islands using DFS. int countDistinctIslands(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); set<string> uniqueShapes; // Scan every cell using nested loops. for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (grid[row][col] == 1) { vector<string> shape; dfs(row, col, row, col, grid, shape); // Build a comparable string signature. string signature = ""; for (string& point : shape) { signature += point + "|"; } // Store only unique signatures. uniqueShapes.insert(signature); } } } // Return count of unique shapes. return uniqueShapes.size(); }};// Driver code.int main() { vector<vector<int>> grid = { {1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1} }; Solution sol; cout << sol.countDistinctIslands(grid); return 0;}Complexity Analysis
Time Complexity: O(R×C) on average, where R and C are the grid dimensions; every cell is visited once and every land cell contributes once to a hashed signature.
Space Complexity: O(R×C), where the recursion stack, temporary coordinates, and stored unique signatures can collectively contain up to R×C cells.
Approach 2
Breadth First Search explores an entire island iteratively using a queue. The first land cell encountered during row-major traversal becomes the base position for normalizing all coordinates in the island.
Every dequeued cell contributes a relative coordinate to the island signature. A fixed neighbor order produces consistent signatures, while queue-based traversal avoids recursive call-stack usage.
Algorithm
Initialize an empty hash set for unique island signatures and define the four movement directions in a fixed order.
Traverse the grid using nested row and column loops to locate every unvisited land cell.
Upon finding a land cell, store the position as the base, mark the cell as water, and add the coordinates to a queue.
Process the queue and record each removed cell as
(row-baseRow, col-baseCol), preserving shape while removing absolute position.Examine all four neighbors and add every valid land neighbor after marking the cell as water, preventing duplicate queue entries.
Convert the collected relative coordinates into an unambiguous signature and insert the signature into the hash set.
Return the hash-set size after all cells have been processed, as every stored signature represents one distinct island shape.
Dry Run
count-distinct-islands-bfs-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to count distinct islands using BFS. int countDistinctIslands(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); set<string> uniqueShapes; vector<int> deltaRow = {-1, 1, 0, 0}; vector<int> deltaCol = {0, 0, -1, 1}; // Scan every cell using nested loops. for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (grid[row][col] == 0) { continue; } vector<string> shape; queue<pair<int, int>> q; grid[row][col] = 0; q.push({row, col}); // Process one complete island. while (!q.empty()) { auto cell = q.front(); q.pop(); int currentRow = cell.first; int currentCol = cell.second; // Store relative position from island start. shape.push_back(to_string(currentRow - row) + ":" + to_string(currentCol - col)); // Visit all four neighboring cells. for (int dir = 0; dir < 4; dir++) { int nextRow = currentRow + deltaRow[dir]; int nextCol = currentCol + deltaCol[dir]; if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols && grid[nextRow][nextCol] == 1) { grid[nextRow][nextCol] = 0; q.push({nextRow, nextCol}); } } } // Build a comparable string signature. string signature = ""; for (string& point : shape) { signature += point + "|"; } // Store only unique signatures. uniqueShapes.insert(signature); } } // Return count of unique shapes. return uniqueShapes.size(); }};// Driver code.int main() { vector<vector<int>> grid = { {1, 1, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {1, 1, 0, 1, 1} }; Solution sol; cout << sol.countDistinctIslands(grid); return 0;}Complexity Analysis
Time Complexity: O(R×C) on average, where R and C are the grid dimensions; every cell is processed once and every land cell contributes once to a hashed signature.
Space Complexity: O(R×C), where the queue, temporary coordinates, and stored unique signatures can collectively contain up to R×C cells.
Interview follow-up Questions
No. Only translation is allowed, so rotations are counted separately.
Be the first to add a comment.