Problem:
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Process:
Objective: Return the number of islands
Constraints:
1. m == grid.length
2. n == grid[i].length
3. 1 <= m, n <= 300
4. grid[i][j] is '0' or '1'.
Edge Cases:
1. When the grid is completely filled with land or water
2. When the (0,0) coordinate of the grid is land or water
Additional Details:
1. An island is when a land is surrounded by 0 horizontally and vertically.
2. The grid is NOT a square.
Solution:
(Incorrect)Attempt #1: Traversing through the graph WITHOUT Iteration
- Time Complexity: O(n), where n is the total number of nodes
- Space Complexity: O(n)
Logic behind this decision:
1. I would like to traverse through each node once to find the number of islands.
How it works
-However, it does not work.-
1. I would visit a node, add its "land" neighbors to nodes_to_visit2. These nodes will be added to nodes_visited. When nodes_to_visit2 is empty, all the land of one island should be visited.
2. If you visit a node that is empty right after visiting the whole island, then island_count increases. (This creates huge problem later) The logic was that you would visit the whole island and you should be visiting the "water" node. However, two land nodes of different island can be added at once.
3. I would continue to traverse each node and not go over the nodes that are already visited.
def find_neighbors(self, node, max_len):
x,y = node
neighbors = []
if x+1 < max_len and x+1 > -1:
neighbors.append((x+1, y))
if y+1 < max_len and y+1 > -1:
neighbors.append((x,y+1))
return neighbors
def numIslands(self, grid: List[List[str]]) -> int:
nodes_visited = []
nodes_to_visit1 = []
nodes_to_visit2 = []
island_count = 0
print
if grid[0][0] == "1":
nodes_to_visit1.append((0,0))
counted = False
else:
nodes_to_visit2.append((0,0))
counted = True
while nodes_to_visit1 or nodes_to_visit2:
if nodes_to_visit1:
counted = False
node = nodes_to_visit1.pop(0)
else:
if not counted:
island_count += 1
counted = True
node = nodes_to_visit2.pop(0)
neighbors = self.find_neighbors(node, len(grid))
nodes_visited.append(node)
for neighbor_node in neighbors:
x,y = neighbor_node
neighbor_val = grid[y][x]
if neighbor_val == "1":
if neighbor_node not in nodes_to_visit1 and neighbor_node not in nodes_visited:
nodes_to_visit1.append(neighbor_node)
else:
if neighbor_node not in nodes_to_visit2 and neighbor_node not in nodes_visited:
nodes_to_visit2.append(neighbor_node)
if counted == False:
island_count += 1
return island_countLimitations:
1. This code does not work.
2. There is a limitation if two nodes that are a part of completely different island are added to nodes_to_visit1 at once.
Attempt #2: Iterating through each graph with BFS
- Time Complexity: O(n^3) - due to the while loop within the nested for loops.
- Space Complexity: O(n)
How it works:
1. I would visit every single node that are NOT YET VISITED with nested for loops.
2. If I encounter a "land" node, I would traverse through its neighbors to check off all the other land nodes of this island as nodes_visited.
3. After traversing through all of the node on that particular island, I have incremented the island_count and continued iterating through the nodes.
def find_neighbors(self, node, max_len_x, max_len_y, nodes_visited, nodes_to_visit):
x,y = node
neighbors = []
if x-1 < max_len_x and x-1 > -1 and (x-1,y) not in nodes_visited and (x-1,y) not in nodes_to_visit:
neighbors.append((x-1, y))
if x+1 < max_len_x and x+1 > -1 and (x+1,y) not in nodes_visited and (x+1,y) not in nodes_to_visit:
neighbors.append((x+1, y))
if y+1 < max_len_y and y+1 > -1 and (x,y+1) not in nodes_visited and (x,y+1) not in nodes_to_visit:
neighbors.append((x,y+1))
if y-1 < max_len_y and y-1 > -1 and (x,y-1) not in nodes_visited and (x,y-1) not in nodes_to_visit:
neighbors.append((x,y-1))
return neighbors
def numIslands(self, grid: List[List[str]]) -> int:
nodes_visited = []
nodes_to_visit = []
island_count = 0
for x in range(len(grid[0])):
for y in range(len(grid)):
if grid[y][x] == "1" and (x,y) not in nodes_visited:
nodes_to_visit = [(x,y)]
while nodes_to_visit:
node = nodes_to_visit.pop()
nodes_visited.append(node)
neighbors = self.find_neighbors(node, len(grid[0]), len(grid), nodes_visited, nodes_to_visit)
for neighbor in neighbors:
neighbor_x, neighbor_y = neighbor
if grid[neighbor_y][neighbor_x] == "1":
nodes_to_visit.append(neighbor)
island_count += 1
return island_countLimitations:
- This solution is very expansive in terms of time. I would have to remove the while loop within the nested for loops in order to reduce the time.
Attempt #3: Iterating through each graph with DFS(Recursion)
- Time Complexity: O(n^3) - due to recursive function calls
- Space Complexity: O(n) - due to space consumed by call stacks
How it works:
1. This code has the same logic as attempt #2 except that it uses recursion and in-place replacement of the grid elements to accomplish the objective.
def dfs(self, grid, x, y):
if 0 <= x < len(grid[0]) and 0 <= y < len(grid) and grid[y][x] == "1":
grid[y][x] = "0"
self.dfs(grid, x+1, y)
self.dfs(grid, x-1, y)
self.dfs(grid, x, y+1)
self.dfs(grid, x, y-1)
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
for x in range(len(grid[0])):
for y in range(len(grid)):
if grid[y][x] == "1":
self.dfs(grid, x, y)
count += 1
return countLimitations:
1. This takes up more space than the second method due to creating extra call stacks that are unnecessary (such as when x or y is less than 0 or greater than their max value.)
LeetCode Question #200
