Maximum Island Area Problem
Given a matrix of 1's (land) and 0's (water), calculate the maximum island area. Islands consist of adjacent land cells connected horizontally or vertically.
Input:
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Output: 4
The solution uses DFS or BFS to traverse each island component and count its area.
Python Implementation using DFS
def explore_island(matrix, visited, x, y):
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
area_count = 1
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
if not visited[nx][ny] and matrix[nx][ny] == 1:
visited[nx][ny] = True
area_count += explore_island(matrix, visited, nx, ny)
return area_count
def solve_max_area():
rows, cols = map(int, input().split())
grid = []
visited = [[False] * cols for _ in range(rows)]
for _ in range(rows):
row = list(map(int, input().split()))
grid.append(row)
max_area = 0
for i in range(rows):
for j in range(cols):
if not visited[i][j] and grid[i][j] == 1:
visited[i][j] = True
current_area = explore_island(grid, visited, i, j)
max_area = max(max_area, current_area)
print(max_area)
solve_max_area()
Python Implementation using BFS
from collections import deque
def bfs_explore(matrix, visited, start_x, start_y):
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
queue = deque([(start_x, start_y)])
area = 1
visited[start_x][start_y] = True
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
if not visited[nx][ny] and matrix[nx][ny] == 1:
visited[nx][ny] = True
area += 1
queue.append((nx, ny))
return area
def solve_with_bfs():
rows, cols = map(int, input().split())
grid = []
visited = [[False] * cols for _ in range(rows)]
for _ in range(rows):
row = list(map(int, input().split()))
grid.append(row)
max_area = 0
for i in range(rows):
for j in range(cols):
if not visited[i][j] and grid[i][j] == 1:
current_area = bfs_explore(grid, visited, i, j)
max_area = max(max_area, current_area)
print(max_area)
Isolated Island Total Area
Calculate the total area of islands that don't touch the matrix boundaries.
Python Solution
from collections import deque
def bfs_check_boundary(matrix, visited, start_x, start_y):
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
queue = deque([(start_x, start_y)])
area = 1
touches_edge = False
visited[start_x][start_y] = True
while queue:
x, y = queue.popleft()
# Check if current position touches boundary
if x == 0 or y == 0 or x == len(matrix) - 1 or y == len(matrix[0]) - 1:
touches_edge = True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
if not visited[nx][ny] and matrix[nx][ny] == 1:
visited[nx][ny] = True
area += 1
queue.append((nx, ny))
return area if not touches_edge else 0
def solve_isolated_islands():
rows, cols = map(int, input().split())
grid = []
visited = [[False] * cols for _ in range(rows)]
for _ in range(rows):
row = list(map(int, input().split()))
grid.append(row)
total_area = 0
for i in range(rows):
for j in range(cols):
if not visited[i][j] and grid[i][j] == 1:
current_area = bfs_check_boundary(grid, visited, i, j)
total_area = max(total_area, current_area)
print(total_area)
Sink Isolated Islands
Convert isolated islands to water while keeping boundary-touching islands intact.
from collections import deque
def mark_boundary_lands(matrix, visited, start_x, start_y):
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
queue = deque([(start_x, start_y)])
matrix[start_x][start_y] = 2 # Mark as boundary-connected
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
if not visited[nx][ny] and matrix[nx][ny] == 1:
visited[nx][ny] = True
matrix[nx][ny] = 2
queue.append((nx, ny))
def sink_isolated_islands():
rows, cols = map(int, input().split())
grid = []
visited = [[False] * cols for _ in range(rows)]
for _ in range(rows):
row = list(map(int, input().split()))
grid.append(row)
# Mark all boundary-connected lands
for j in range(cols):
if grid[0][j] == 1:
visited[0][j] = True
mark_boundary_lands(grid, visited, 0, j)
if grid[rows-1][j] == 1:
visited[rows-1][j] = True
mark_boundary_lands(grid, visited, rows-1, j)
for i in range(rows):
if grid[i][0] == 1:
visited[i][0] = True
mark_boundary_lands(grid, visited, i, 0)
if grid[i][cols-1] == 1:
visited[i][cols-1] = True
mark_boundary_lands(grid, visited, i, cols-1)
# Convert isolated islands to water
for i in range(1, rows-1):
for j in range(1, cols-1):
if grid[i][j] == 1:
grid[i][j] = 0
# Restore boundary-connected lands
for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
grid[i][j] = 1
# Print result
for row in grid:
print(*row)
Water Flow Problem
Determine cells from which water can flow to both ocean boundaries.
from collections import deque
def reverse_flow_search(matrix, visited, start_x, start_y):
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
queue = deque([(start_x, start_y)])
reachable_ocean1 = False
reachable_ocean2 = False
while queue:
x, y = queue.popleft()
if x == 0 or y == 0:
reachable_ocean1 = True
if x == len(matrix) - 1 or y == len(matrix[0]) - 1:
reachable_ocean2 = True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
if not visited[nx][ny] and matrix[nx][ny] >= matrix[x][y]:
visited[nx][ny] = True
queue.append((nx, ny))
return reachable_ocean1 and reachable_ocean2
def water_flow_problem():
rows, cols = map(int, input().split())
heights = []
for _ in range(rows):
row = list(map(int, input().split()))
heights.append(row)
results = []
for i in range(rows):
for j in range(cols):
visited = [[False] * cols for _ in range(rows)]
visited[i][j] = True
if reverse_flow_search(heights, visited, i, j):
results.append([i, j])
for pos in results:
print(pos[0], pos[1])
Build Largest Possible Island
Find the maximum island area after converting at most one water cell to land.
The approach involves:
- First traversal to label each island and record its area
- Second traversal to evaluate each water cell's potential impact
String Ladder Problem
Find shortest transformation sequence from beginWord to endWord where each step changes exactly one character.
from collections import deque
def ladder_length(word_list, begin_word, end_word):
if end_word not in word_list:
return 0
word_set = set(word_list)
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
current_word, steps = queue.popleft()
for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = current_word[:i] + c + current_word[i+1:]
if new_word == end_word:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
Union-Find Data Structure
Union-Find efficiently handles connectivity problems with three core operations:
- Initialize: Set each element as its own parent
- Find: Locate root parent with path compression
- Union: Connect two elements' sets
Template Implementation
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
def connected(self, x, y):
return self.find(x) == self.find(y)
Path Existence in Undirected Graph
Use Union-Find to determine if source and destination nodes are connected.
def check_path_existence():
n, m = map(int, input().split())
uf = UnionFind(n + 1)
for _ in range(m):
u, v = map(int, input().split())
uf.union(u, v)
source, dest = map(int, input().split())
print(1 if uf.connected(source, dest) else 0)
Island Perimeter Calculation
Count perimeter edges by examining adjacent water cells.
def calculate_perimeter():
rows, cols = map(int, input().split())
grid = []
for _ in range(rows):
row = list(map(int, input().split()))
grid.append(row)
perimeter = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
for dx, dy in directions:
ni, nj = i + dx, j + dy
if ni < 0 or nj < 0 or ni >= rows or nj >= cols or grid[ni][nj] == 0:
perimeter += 1
print(perimeter)