Problem of The Day: Redundant
Problem Statement
Brute Force - BFS [TLE]
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
res = 0
ROWS = len(grid)
COLS = len(grid[0])
def bfs(row, col):
val = grid[row][col]
grid[row][col] = 1
visited = [[0 for c in range(COLS)] for r in range(ROWS)]
queue = deque([[row, col]])
ans = 0
while queue:
r, c = queue.popleft()
if visited[r][c] == 1:
continue
visited[r][c] = 1
ans += 1
for x, y in [(0,1),(-1,0),(0,-1),(1,0)]:
nr, nc = r + x, c + y
if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == 1 and visited[nr][nc] == 0:
queue.append([nr, nc])
grid[row][col] = val
return ans
for row in grid:
if any(True for x in row if x == 0):
break
else:
return ROWS * COLS
for row in grid:
if any(True for x in row if x == 1):
break
else:
return 1
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 0:
res = max(res, bfs(r, c))
return res
DFS [Accepted]
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(r, c, index):
if not (0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == 1):
return 0
grid[r][c] = index
return 1 + dfs(r+1, c, index) + dfs(r-1, c, index) + dfs(r, c+1, index) + dfs(r, c-1, index)
n = len(grid)
index = 2
area = defaultdict(int)
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
area[index] = dfs(r, c, index)
index += 1
res = max(area.values() or [0])
for r in range(n):
for c in range(n):
if grid[r][c] == 0:
seen = {grid[nr][nc] for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)] if 0 <= nr < n and 0 <= nc < n}
res = max(res, 1 + sum(area[i] for i in seen))
return res
Notes: The BFS approach is slower than the DFS approach in this problem due to the following reasons:
Repeated Initialization: In the BFS approach, the visited matrix is re-initialized for each cell with value 0. This adds significant overhead, especially for larger grids.
Queue Operations: BFS uses a queue to manage the nodes to be visited. Queue operations (enqueue and dequeue) have additional overhead compared to the recursive stack used in DFS.
Multiple BFS Calls: The BFS approach calls the bfs function for each cell with value 0, leading to multiple traversals of the grid. In contrast, the DFS approach marks all connected components in a single pass and then only considers cells with value 0 once.
Grid Restoration: The BFS approach restores the grid value after each BFS call, adding extra operations.
The DFS approach is more efficient because it marks all connected components in a single pass and uses a more straightforward recursive approach without the need for repeated initialization or queue operations.
Editorial
Approach 1: Using DFS
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
island_sizes = {}
island_id = 2
# Step 1: Mark all islands and calculate their sizes
for current_row in range(len(grid)):
for current_column in range(len(grid[0])):
if grid[current_row][current_column] == 1:
island_sizes[island_id] = self.explore_island(
grid, island_id, current_row, current_column
)
island_id += 1
# If there are no islands, return 1
if not island_sizes:
return 1
# If the entire grid is one island, return its size or size + 1
if len(island_sizes) == 1:
island_id -= 1
return (
island_sizes[island_id]
if island_sizes[island_id] == len(grid) * len(grid[0])
else island_sizes[island_id] + 1
)
max_island_size = 1
# Step 2: Try converting every 0 to 1 and calculate the resulting island size
for current_row in range(len(grid)):
for current_column in range(len(grid[0])):
if grid[current_row][current_column] == 0:
current_island_size = 1
neighboring_islands = set()
# Check down
if (
current_row + 1 < len(grid)
and grid[current_row + 1][current_column] > 1
):
neighboring_islands.add(
grid[current_row + 1][current_column]
)
# Check up
if (
current_row - 1 >= 0
and grid[current_row - 1][current_column] > 1
):
neighboring_islands.add(
grid[current_row - 1][current_column]
)
# Check right
if (
current_column + 1 < len(grid[0])
and grid[current_row][current_column + 1] > 1
):
neighboring_islands.add(
grid[current_row][current_column + 1]
)
# Check left
if (
current_column - 1 >= 0
and grid[current_row][current_column - 1] > 1
):
neighboring_islands.add(
grid[current_row][current_column - 1]
)
# Sum the sizes of all unique neighboring islands
for island_id in neighboring_islands:
current_island_size += island_sizes[island_id]
max_island_size = max(max_island_size, current_island_size)
return max_island_size
def explore_island(
self,
grid: List[List[int]],
island_id: int,
current_row: int,
current_column: int,
) -> int:
if (
current_row < 0
or current_row >= len(grid)
or current_column < 0
or current_column >= len(grid[0])
or grid[current_row][current_column] != 1
):
return 0
grid[current_row][current_column] = island_id
return (
1
+ self.explore_island(
grid, island_id, current_row + 1, current_column
)
+ self.explore_island(
grid, island_id, current_row - 1, current_column
)
+ self.explore_island(
grid, island_id, current_row, current_column + 1
)
+ self.explore_island(
grid, island_id, current_row, current_column - 1
)
)
Approach 2: Using Disjoint Set Union (DSU)
class DisjointSet:
def __init__(self, n: int):
self.parent = [i for i in range(n)]
self.island_size = [1] * n
# Function to find the root of a node with path compression
def find_root(self, node: int) -> int:
if self.parent[node] == node:
return node
self.parent[node] = self.find_root(self.parent[node])
return self.parent[node]
# Function to union two sets based on size
def union_nodes(self, node_a: int, node_b: int):
root_a = self.find_root(node_a)
root_b = self.find_root(node_b)
# Already in the same set
if root_a == root_b:
return
# Union by size: Attach the smaller island to the larger one
if self.island_size[root_a] < self.island_size[root_b]:
# Attach root_a to root_b
self.parent[root_a] = root_b
# Update size of root_b's island
self.island_size[root_b] += self.island_size[root_a]
else:
# Attach root_b to root_a
self.parent[root_b] = root_a
# Update size of root_a's island
self.island_size[root_a] += self.island_size[root_b]
class Solution:
def largestIsland(self, grid: list[list[int]]) -> int:
rows = len(grid)
columns = len(grid[0])
# Initialize DSU for the entire grid
ds = DisjointSet(rows * columns)
# Direction vectors for traversing up, down, left, and right
row_directions = [1, -1, 0, 0]
column_directions = [0, 0, 1, -1]
# Step 1: Union adjacent `1`s in the grid
for current_row in range(rows):
for current_column in range(columns):
if grid[current_row][current_column] == 1:
# Flatten 2D index to 1D
current_node = (columns * current_row) + current_column
for direction in range(4):
neighbor_row = current_row + row_directions[direction]
neighbor_column = (
current_column + column_directions[direction]
)
# Check bounds and ensure the neighbor is also `1`
if (
0 <= neighbor_row < rows
and 0 <= neighbor_column < columns
and grid[neighbor_row][neighbor_column] == 1
):
neighbor_node = (
columns * neighbor_row + neighbor_column
)
ds.union_nodes(current_node, neighbor_node)
# Step 2: Calculate the maximum possible island size
max_island_size = 0
# Flag to check if there are any zeros in the grid
has_zero = False
# To store unique roots for a `0`'s neighbors
unique_roots = set()
for current_row in range(rows):
for current_column in range(columns):
if grid[current_row][current_column] == 0:
has_zero = True
# Start with the flipped `0`
current_island_size = 1
for direction in range(4):
neighbor_row = current_row + row_directions[direction]
neighbor_column = (
current_column + column_directions[direction]
)
# Check bounds and ensure the neighbor is `1`
if (
0 <= neighbor_row < rows
and 0 <= neighbor_column < columns
and grid[neighbor_row][neighbor_column] == 1
):
neighbor_node = (
columns * neighbor_row + neighbor_column
)
root = ds.find_root(neighbor_node)
unique_roots.add(root)
# Sum up the sizes of unique neighboring islands
for root in unique_roots:
current_island_size += ds.island_size[root]
# Clear the set for the next `0`
unique_roots.clear()
# Update the result with the largest island size found
max_island_size = max(max_island_size, current_island_size)
# If there are no zeros, the largest island is the entire grid
if not has_zero:
return rows * columns
return max_island_size
