694. Number of Distinct Islands
Problem Description
In this problem, we are tasked to find the number of distinct islands on a given m x n
binary grid. Each cell in the grid can either be "1" (representing land) or "0" (representing water). An island is defined as a group of "1"s connected horizontally or vertically. We are also told that all the edges of the grid are surrounded by water, which simplifies the problem by ensuring we don't need to handle edge scenarios where islands might be connected beyond the grid.
To consider two islands as the same, they have to be identical in shape and size, and they must be able to be translated (moved horizontally or vertically, but not rotated or flipped) to match one another. The objective is to return the number of distinct islands—those that are not the same as any other island in the grid.
Flowchart Walkthrough
Let's analyze Leetcode 694. Number of Distinct Islands using the Flowchart. Here's the step-by-step process to determine the suitable algorithm:
-
Is it a graph?
- Yes: The grid can be envisioned as a graph where each cell represents a node. Adjacent cells (left, right, up, down) that are both '1's form an edge.
-
Is it a tree?
- No: The grid is not necessarily hierarchical and can consist of multiple separate connective components, which do not form a single tree.
-
Is the problem related to directed acyclic graphs (DAGs)?
- No: The primary concern here is identifying and counting distinct groups of connected '1's, which represent islands. This is unrelated to DAG properties.
-
Is the problem related to shortest paths?
- No: The objective is to count distinct formations of connected components, not to find the shortest path between points.
-
Does the problem involve connectivity?
- Yes: The core of the problem is identifying and counting distinct connected components in the grid.
-
Is the graph weighted?
- No: All edges in the graph (defined by adjacent '1's) have the same, non-specific weight—it's merely connectivity that matters.
-
Does the problem have small constraints?
- Yes: Typically, problems involving grid connectivity with distinct shape determination (like counting distinct islands) have manageable constraints that allow for exhaustive exploration of possibilities.
-
DFS or backtracking?
- DFS/backtracking: Depth-First Search is particularly well-suited for exploring all nodes in each distinct island, facilitating checks for unique configurations.
Conclusion: Using the flowchart, it's determined that Depth-First Search (DFS) is the optimal method to explore and identify distinct islands based on their shapes, which involves detailed traversal and backtracking when necessary to discern unique island structures.
Intuition
The solution leverages a Depth-First Search (DFS) approach. The core idea is to explore each island, marking the visited 'land' cells, and record the paths taken to traverse each island uniquely. These paths are captured as strings, which allows for easy comparison of island shapes.
Here's the step-by-step intuition behind the approach:
- Iterate through each cell in the grid.
- When land ("1") is found, commence a DFS from that cell to visit all connected 'land' cells of that island, effectively marking it to avoid revisiting.
- While executing DFS, record the direction taken at each step to uniquely represent the path over the island. This is done using a representative numerical code.
- Append reverse steps at the end of each DFS call to differentiate between paths when the DFS backtracks. This ensures that shapes are uniquely identified even if they take the same paths but in different order.
- After one complete island is traversed and its path is recorded, add the path string to a set to ensure we only count unique islands.
- Clear the path and continue the search for the next unvisited 'land' cell to find all islands.
- After the entire grid is scanned, count the number of unique path strings in the set, which corresponds to the number of distinct islands.
This solution is efficient and elegant because the DFS ensures that each cell is visited only once, and the set data structure automatically handles the uniqueness of the islands.
Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.
Solution Approach
The implementation of the solution can be broken down into several key components, using algorithms, data structures, and patterns which are encapsulated in the DFS strategy outlined previously:
-
Depth-First Search (DFS):
- This recursive algorithm is essential for traversing the grid and visiting every possible 'land' cell in an island once. The DFS is initiated whenever a '1' is encountered, and it continues until there are no more adjacent '1's to visit.
-
Grid Modification to Mark Visited Cells:
- As the DFS traverses the grid, it marks the cells that have been visited by flipping them from '1' to '0'. This prevents revisiting the same cell and ensures each 'land' cell is part of only one island.
-
Directions and Path Encoding:
- Four possible directions for movement are captured in a list of deltas
dirs
. During DFS, the current direction taken is recorded by appending a number to thepath
list, which is converted to a string for easy differentiation.
- Four possible directions for movement are captured in a list of deltas
-
Backtracking with Signature:
- To handle backtracking uniquely, the algorithm appends a negative value of the move when DFS backtracks. This helps in creating a unique path signature for shapes that otherwise may seem similar if traversed differently.
-
Path Conversion and Uniqueness:
- After a complete island is explored, the
path
list is converted to a string that represents the full traversal path of the island. This string allows the shape of the island to be expressed uniquely, similar to a sequence of moves in a game.
- After a complete island is explored, the
-
Set Data Structure:
- A
set()
is used to store unique island paths. This data structure's inherent property to store only unique items simplifies the task of counting distinct islands. Duplicates are automatically handled.
- A
-
Counts Distinct Islands:
- The final number of distinct islands is obtained by measuring the length of the set containing the unique path strings.
Here is the code snippet detailing the DFS logic:
1def dfs(i: int, j: int, k: int):
2 grid[i][j] = 0
3 path.append(str(k))
4 dirs = (-1, 0, 1, 0, -1)
5 for h in range(1, 5):
6 x, y = i + dirs[h - 1], j + dirs[h]
7 if 0 <= x < m and 0 <= y < n and grid[x][y]:
8 dfs(x, y, h)
9 path.append(str(-k))
Finally, the number of distinct islands is returned using len(paths)
where paths
is the set of unique path strings.
By following these stages, the algorithm effectively captures the essence of each island's shape regardless of its location in the grid, allowing us to accurately count the number of distinct islands present.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small 4 x 5
grid example:
Assume our grid looks like this, where '1' is land and '0' is water:
11 1 0 0 0 21 1 0 1 1 30 0 0 1 1 40 0 0 0 0
Now, let's walk through the DFS approach outlined above:
- Start scanning the grid from
(0, 0)
. - At
(0, 0)
, find '1' and start DFS, initializing an emptypath
list. - Visit
(0, 0)
, mark as '0', and add direction code topath
. Since there's no previous cell, we skip encoding here. - From
(0, 0)
, move to(0, 1)
(right), mark as '0', and add '2' topath
(assuming '2' represents moving right). - Continue DFS to
(1, 1)
(down), mark as '0', and add '3' topath
(assuming '3' represents moving down). - DFS can't move further, so backtrack appending '-3' to
path
to return to(0, 1)
, then append '-2' to backtrack to(0, 0)
. - Since all adjacent '1's are visited, the DFS for this island ends, and the
path
is['2', '3', '-3', '-2']
. - Convert
path
to a string"233-3-2"
and insert into thepaths
set. - Continue scanning the grid and start a new DFS at
(1, 3)
, where the next '1' is found. - Repeat the steps to traverse the second island. Assume the resulting
path
for the second island is"233-3-2"
. - Conversion and insertion into
paths
set have no effect as it's a duplicate. - Finish scanning the grid, with no more '1's left.
- Count the distinct islands from the
paths
set, which contains just one unique path string"233-3-2"
.
We conclude that there is only 1 distinct island in this example grid.
This walkthrough demonstrates how the DFS exploration with unique path encoding can be used to solve this problem, ensuring that only distinct islands are counted even when they are scattered throughout the grid.
Solution Implementation
1class Solution:
2 def numDistinctIslands(self, grid: List[List[int]]) -> int:
3 # Depth-first search function to explore the island
4 def depth_first_search(i: int, j: int, move: int):
5 grid[i][j] = 0 # Marking the visited cell as '0' to avoid revisiting
6 path.append(str(move)) # Add the move direction to path
7 # Possible movements in the four directions: up, right, down, left
8 directions = (-1, 0, 1, 0, -1)
9 # Iterating over the four possible directions
10 for h in range(4):
11 # Calculate new cell's coordinates
12 x, y = i + directions[h], j + directions[h+1]
13 # Check if the new cell is within bounds and is part of an island
14 if 0 <= x < m and 0 <= y < n and grid[x][y]:
15 depth_first_search(x, y, h+1)
16 path.append(str(-move)) # Add the reverse move to path to differentiate shapes
17
18 # Set to store unique paths that represent unique island shapes
19 paths = set()
20 # Temporary list to store the current island's path shape
21 path = []
22 # Dimensions of the grid
23 m, n = len(grid), len(grid[0])
24
25 # Iterate over every cell in the grid
26 for i, row in enumerate(grid):
27 for j, value in enumerate(row):
28 if value: # Check if the cell is part of an island
29 depth_first_search(i, j, 0) # Start DFS from this cell
30 paths.add("".join(path)) # Add the path shape to the set of paths
31 path.clear() # Clear the path for next island
32
33 # Number of distinct islands is the number of unique path shapes
34 return len(paths)
35
1class Solution {
2 private int rows; // number of rows in the grid
3 private int cols; // number of columns in the grid
4 private int[][] grid; // grid representation
5 private StringBuilder path; // used to store the path during DFS to identify unique islands
6
7 public int numDistinctIslands(int[][] grid) {
8 rows = grid.length; // set the number of rows
9 cols = grid[0].length; // set the number of columns
10 this.grid = grid; // reference the grid
11 Set<String> uniqueIslands = new HashSet<>(); // store unique island paths as strings
12 for (int i = 0; i < rows; ++i) {
13 for (int j = 0; j < cols; ++j) {
14 if (grid[i][j] == 1) { // if it's part of an island
15 path = new StringBuilder(); // initialize the path
16 exploreIsland(i, j, 'S'); // start DFS with dummy direction 'S' (Start)
17 uniqueIslands.add(path.toString()); // add the path to the set
18 }
19 }
20 }
21 return uniqueIslands.size(); // the number of unique islands
22 }
23
24 private void exploreIsland(int i, int j, char direction) {
25 grid[i][j] = 0; // mark as visited
26 path.append(direction); // append the direction to path
27
28 // directions represented as delta x and delta y
29 int[] dX = {-1, 0, 1, 0};
30 int[] dY = {0, 1, 0, -1};
31 char[] dirCodes = {'U', 'R', 'D', 'L'}; // corresponding directional codes
32
33 for (int dir = 0; dir < 4; ++dir) { // iterate over possible directions
34 int x = i + dX[dir];
35 int y = j + dY[dir];
36 if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) { // check for valid next cell
37 exploreIsland(x, y, dirCodes[dir]); // recursive DFS call
38 }
39 }
40
41 path.append('B'); // append backtrack code to ensure paths are unique after recursion return
42 }
43}
44
1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <functional> // Include necessary headers
5
6class Solution {
7public:
8 int numDistinctIslands(vector<vector<int>>& grid) {
9 unordered_set<string> uniqueIslandPaths; // Store unique representations of islands
10 string currentPath; // Store the current traversal path
11 int rowCount = grid.size(), colCount = grid[0].size(); // Dimensions of the grid
12 int directions[5] = {-1, 0, 1, 0, -1}; // Used for moving in the grid
13
14 // Depth-first search (DFS) to traverse islands and record paths
15 function<void(int, int, int)> dfs = [&](int row, int col, int moveDirection) {
16 grid[row][col] = 0; // Mark the current cell as visited
17 currentPath += to_string(moveDirection); // Record move direction
18
19 // Explore all possible directions: up, right, down, left
20 for (int d = 1; d < 5; ++d) {
21 int newRow = row + directions[d - 1], newCol = col + directions[d];
22 if (newRow >= 0 && newRow < rowCount && newCol >= 0 && newCol < colCount && grid[newRow][newCol]) {
23 // Continue DFS if the next cell is part of the island (i.e., grid value is 1)
24 dfs(newRow, newCol, d);
25 }
26 }
27
28 // Record move direction again to differentiate between paths with same shape but different sizes
29 currentPath += to_string(moveDirection);
30 };
31
32 // Iterate over all grid cells to find all islands
33 for (int i = 0; i < rowCount; ++i) {
34 for (int j = 0; j < colCount; ++j) {
35 // If the cell is part of an island
36 if (grid[i][j]) {
37 dfs(i, j, 0); // Start DFS
38 uniqueIslandPaths.insert(currentPath); // Add the path to the set
39 currentPath.clear(); // Reset path for the next island
40 }
41 }
42 }
43
44 // The number of unique islands is the size of the set containing unique paths
45 return uniqueIslandPaths.size();
46 }
47};
48
1function numDistinctIslands(grid: number[][]): number {
2 const rowCount = grid.length; // The number of rows in the grid.
3 const colCount = grid[0].length; // The number of columns in the grid.
4 const uniquePaths: Set<string> = new Set(); // Set to store unique island shapes.
5 const currentPath: number[] = []; // Array to keep the current DFS path.
6 const directions: number[] = [-1, 0, 1, 0, -1]; // Array for row and column movements.
7
8 // Helper function to perform DFS.
9 const dfs = (row: number, col: number, directionIndex: number) => {
10 grid[row][col] = 0; // Mark the cell as visited by setting it to 0.
11 currentPath.push(directionIndex); // Append the direction index to the current path.
12
13 // Explore all four directions: up, right, down, left.
14 for (let i = 1; i < 5; ++i) {
15 const nextRow = row + directions[i - 1];
16 const nextCol = col + directions[i];
17
18 // Check if the next cell is within bounds and not visited.
19 if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && grid[nextRow][nextCol]) {
20 dfs(nextRow, nextCol, i); // Recursively perform DFS on the next cell.
21 }
22 }
23
24 // Upon return, push the backtracking direction index to the current path.
25 currentPath.push(directionIndex);
26 };
27
28 // Iterate through all cells of the grid.
29 for (let row = 0; row < rowCount; ++row) {
30 for (let col = 0; col < colCount; ++col) {
31 // If the current cell is part of an island (value is 1).
32 if (grid[row][col]) {
33 dfs(row, col, 0); // Start DFS from the current cell.
34 uniquePaths.add(currentPath.join(',')); // Add the current path to the set of unique paths.
35 currentPath.length = 0; // Reset the currentPath for the next island.
36 }
37 }
38 }
39
40 return uniquePaths.size; // Return the number of distinct islands.
41}
42
Time and Space Complexity
The time complexity of the provided code is O(M * N)
, where M
is the number of rows and N
is the number of columns in the grid. This is due to the fact that we must visit each cell at least once to determine the islands. The dfs
function is called for each land cell (1)
and it ensures every connected cell is visited only once by marking visited cells as water (0)
immediately, thus avoiding revisiting.
The space complexity is O(M * N)
in the worst case. This could happen if the grid is filled with land, and a deep recursive call stack is needed to explore the island. Additionally, the path
variable which records the shape of each distinct island can in the worst case take up as much space as all the cells in the grid (if there was one very large island), therefore the space complexity would depend on the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.