Aug 26, 2024 | monday 7:00 pm
This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
HardGraph
Try it yourself here!
Problem Statement: Given a start word, an end word, and a list of words, determine the number of one-letter transformations needed to transform the start word into the end word.
Edge Cases:
Example:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
Output: 5,
Explanation: hit -> hot -> dot -> dog -> log -> cog, it takes 5 transformations from hot to cog
Key Steps:
BFS Algorithm Details:
Complexity:
Time: O(n * m^2), where n is the length of the wordList, and m is the length of the longest word.
Space: O(n * m^2), space required for the pattern mapping, set, and queue.
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
graph = defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1:]
graph[pattern].append(word)
seen = set([beginWord])
q = deque([beginWord])
res = 1
while q:
for i in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1:]
for n in graph[pattern]:
if n not in seen:
seen.add(n)
q.append(n)
res += 1
return 0
MediumGraphs
Try it yourself here!
def numIslands(self, grid: List[List[str]]) -> int:
res = 0
def bfs(i, j):
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
q = deque([(i, j)])
M, N = len(grid), len(grid[0])
while q:
x, y = q.popleft()
grid[x][y] = "0"
for dx, dy in directions:
if 0 <= x + dx < M and 0 <= y + dy < N and grid[x + dx][y + dy] == "1":
q.append((x + dx, y + dy))
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
res += 1
bfs(i, j)
return res
Complexity:
Time: O(m * n), where each cell in the grid is only visited once.
Space: O(m * n), space used to hold cells in the queue.
MediumGraphs
Try it yourself here!
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def dfs(i, j):
if (i < 0 or i >= len(grid)
or j < 0 or j >= len(grid[0]) or grid[i][j] == 0):
return 0
grid[i][j] = 0
return 1 + dfs(i + 1, j) + dfs(i, j + 1) \
+ dfs(i - 1, j) + dfs(i, j - 1)
maxArea = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
area = dfs(i, j)
maxArea = max(maxArea, area)
return maxArea
Complexity:
Time: O(m * n), where each cell in the grid is only visited once.
Space: O(m * n), space used for the recursion stack.
MediumGraph
Try it yourself here!
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
newNodes = {}
def cloneNode(node):
if not node:
return
if node in newNodes:
return newNodes[node]
newNode = Node(node.val)
newNodes[node] = newNode
for n in node.neighbors:
neighborNode = cloneNode(n)
newNode.neighbors.append(neighborNode)
return newNode
return cloneNode(node)
Complexity:
Time: O(n), where n is the number of nodes in the graph
Space: O(n), recursion stack could be size n for a singly-linked list graph.
MediumGraphs
Try it yourself here!
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
queue = deque()
seen = set()
for m in range(len(rooms)):
for n in range(len(rooms[0])):
if rooms[m][n] == 0:
queue.append([m, n])
seen.add((m, n))
while queue:
x, y = queue.popleft()
for dx, dy in dir:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < len(rooms) and 0 <= new_y < len(rooms[0]) and rooms[new_x][new_y] != -1:
rooms[new_x][new_y] = min(rooms[new_x][new_y], rooms[x][y] + 1)
if (new_x, new_y) not in seen:
queue.append([new_x, new_y])
seen.add((new_x, new_y))
Complexity:
Time: O(m * n), each cell in the grid is visited once
Space: O(m * n), space required for the queue and set.
MediumGraphs
Try it yourself here!
def orangesRotting(self, grid: List[List[int]]) -> int:
num_oranges = 0
time = 0
q = deque()
rows, cols = len(grid), len(grid[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:
num_oranges += 1
elif grid[i][j] == 2:
q.append([i, j])
while q:
length = len(q)
for i in range(length):
[i, j] = q.popleft()
for dx, dy in directions:
next_i, next_j = i + dx, j + dy
if 0 <= next_i < rows and 0 <= next_j < cols and grid[next_i][next_j] == 1:
grid[next_i][next_j] = 2
num_oranges -= 1
q.append([next_i, next_j])
if not q:
break
time += 1
return -1 if num_oranges else time
Complexity:
Time: O(m * n), Each cell is visited in linear time, at most twice.
Space: O(m * n), space required to store cells in the queue
MediumGraph
Try it yourself here!
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
atlanticQueue = deque()
pacificQueue = deque()
rows = len(heights)
cols = len(heights[0])
for i in range(rows):
atlanticQueue.append((i, 0))
pacificQueue.append((i, cols - 1))
for j in range(cols):
atlanticQueue.append((0, j))
pacificQueue.append((rows - 1, j))
def bfs(queue):
nonlocal rows, cols
reachable = set()
while queue:
i, j = queue.popleft()
reachable.add((i, j))
for x, y in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
dx, dy = i + x, j + y
if 0 <= dx < rows and 0 <= dy < cols and (dx, dy) not in reachable and heights[dx][dy] >= heights[i][j]:
queue.append((dx, dy))
return reachable
atlantic = bfs(atlanticQueue)
pacific = bfs(pacificQueue)
return list(atlantic.intersection(pacific))
Complexity:
Time: O(2n), Each cell in the grid is visited at most twice through two bfs calls.
Space: O(2n), set to hold cells that are reachable from the atlantic and pacific borders.
Medium
Try it yourself here!
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def dfs(i, j):
if board[i][j] != "O":
return
board[i][j] = "E"
if i > 0:
dfs(i - 1, j)
if i < len(board) - 1:
dfs(i + 1, j)
if j > 0:
dfs(i, j - 1)
if j < len(board[0]) - 1:
dfs(i, j + 1)
borders = []
seen = set()
rows = len(board)
cols = len(board[0])
for i in range(rows):
borders.append((i, cols - 1))
borders.append((i, 0))
for j in range(cols):
borders.append((rows - 1, j))
borders.append((0, j))
for i, j in borders:
dfs(i, j)
for i in range(rows):
for j in range(cols):
if board[i][j] == "O":
board[i][j] = "X"
if board[i][j] == "E":
board[i][j] = "O"
Complexity:
Time: O(2n), where n is the number of cells in the board. Each cell is visited once in the traversal, and once more during the cell reversion
Space: O(n), space required for the recursion stack.
MediumGraph
Try it yourself here!
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
numPrerequisites = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
numPrerequisites[a] += 1
q = deque()
for i in range(numCourses):
if numPrerequisites[i] == 0:
q.append(i)
nodesVisited = 0
while q:
course = q.popleft()
nodesVisited += 1
for n in graph[course]:
numPrerequisites[n] -= 1
if numPrerequisites[n] == 0:
q.append(n)
return nodesVisited == numCourses
Complexity:
Time: O(2n), each course is visited twice to build the graph and run topological sort.
Space: O(n), space required to build the graph.
MediumGraphs
Try it yourself here!
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = defaultdict(list)
degrees = [0] * numCourses
res = []
for pair in prerequisites:
graph[pair[1]].append(pair[0])
degrees[pair[0]] += 1
q = deque()
for i in range(numCourses):
if degrees[i] == 0:
q.append(i)
res.append(i)
nodesVisited = 0
while q:
node = q.popleft()
nodesVisited += 1
for neighbor in graph[node]:
degrees[neighbor] -= 1
if degrees[neighbor] == 0:
q.append(neighbor)
res.append(neighbor)
return res if nodesVisited == numCourses else []
Complexity:
Time: O(2n), each course is visited twice to build the graph and run topological sort.
Space: O(n), space required to build the graph.
MediumGraphs
Try it yourself here!
def validTree(self, n: int, edges: List[List[int]]) -> bool:
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = set()
def dfs(curr, prev):
if curr in seen:
return False
seen.add(curr)
for n in graph[curr]:
if n == prev:
continue
if not dfs(n, curr):
return False
return True
return dfs(0, -1) and len(seen) == n
Complexity:
Time: O(2n), where each node is visited twice, once to build the graph and another to run dfs
Space: O(n), space required for the recursion stack and set.
MediumGraphs
Try it yourself here!
def countComponents(self, n: int, edges: List[List[int]]) -> int:
counter = 0
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = set()
def dfs(node):
if node in seen:
return
seen.add(node)
for v in graph[node]:
dfs(v)
for i in range(n):
if i not in seen:
counter += 1
dfs(i)
return counter
Complexity:
Time: O(2n), where each node is visited twice, once to build the graph and another to run dfs
Space: O(n), space required for the recursion stack and set.
MediumGraphs
Try it yourself here!
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
graph = defaultdict(set)
def dfs(source, target):
if source not in seen:
seen.add(source)
if source == target: return True
for n in graph[source]:
if dfs(n, target):
return True
return False
for a, b in edges:
seen = set()
if a in graph and b in graph and dfs(a, b):
return a, b
graph[a].add(b)
graph[b].add(a)
Complexity:
Time: O(n), where n is the number of vertices in the graph.
Space: O(n), space required for the recursion stack and set.