Hard Graph
6 min readDec 20, 2019
Apologies. This article is for the reader who is in the last one or two months of interview preparation, say you have prepared at least 400 Leetcode questions.
This article will contain some hard graph questions from leetcode.
882. Reachable Nodes In Subdivided Graph
This problem is similar to
Key steps
- build graph
- prune infeasible branches in an early stage by comparing the steps to move to a specified node. Do not add them if move steps of new node are larger than before.
- Then follow standard BFS approach and recording the number of new generated nodes for the new graph from both i to j and j to i. Then the final results of reachable new added nodes will be min(n, i to j + j to i) as they may have overlaps.
BFS (732ms)
from collections import deque
class Solution:
def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:
edg = {}
graph = collections.defaultdict(list)
dp = collections.defaultdict(int)
for a,b,n in edges:
graph[a].append(b)
graph[b].append(a)
edg[(a,b)] = n
edg[(b,a)] = n
def bfs():
Q = deque([(0, 0)])
seen = collections.defaultdict(lambda: float('inf'))
seen[0] = 0
while Q:
i, d = Q.popleft()
for j in graph[i]:
n = edg[(i,j)]
if d+n+1<=M:
dp[(i,j)] = n
if seen[j] >d+n+1:
seen[j] = d+n+1
Q.append((j, d+n+1))
else:
dp[(i,j)] = max(M-d, dp[(i,j)])
return seen
seen = bfs()
res = len(seen.keys())
return res+sum(min(n, dp[(a,b)]+dp[(b,a)]) for a, b, n in edges)864. Shortest Path to Get All Keys
BFS again (568ms)
this time, for the seen, record the location + s where s is a set contains all keys.
class Solution:
def shortestPathAllKeys(self, grid: List[str]) -> int:
R, C = len(grid), len(grid[0])
ii, jj =0 ,0
target = 0
for i in range(R):
for j in range(C):
if grid[i][j]=='@':
ii, jj = i, j
if grid[i][j].islower():
target+=1
def bfs(i, j):
from collections import deque
Q = deque([(i,j, 0 ,set())])
seen = {(i,j,tuple(sorted(set())))}
while Q:
i,j, d, s = Q.popleft()
for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:
r, c = i+di, j+dj
if 0<=r<R and 0<=c<C:
if grid[r][c].islower():
#s1 = s
s1 = s.copy()
s1.add(grid[r][c])
if len(s1)==target:return d+1
tuple_s = tuple(sorted(set(s1)))
if (r,c,tuple_s) not in seen:
seen.add((r,c,tuple_s))
Q.append((r,c, d+1,s1))
elif grid[r][c].isupper():
if grid[r][c].lower() in s:
tuple_s = tuple(sorted(set(s)))
if (r,c,tuple_s) not in seen:
seen.add((r,c,tuple_s))
Q.append((r,c, d+1, s))
elif grid[r][c]!='#':
tuple_s = tuple(sorted(set(s)))
if (r,c,tuple_s) not in seen:
seen.add((r,c,tuple_s))
Q.append((r,c, d+1, s))
return -1
return bfs(ii,jj)Deep copy of a set has to be used here to avoid Wrong Answer.
s1 = s.copy()854. K-Similar Strings
BFS can be used to solve this problem.
class Solution:
def kSimilarity(self, A: str, B: str) -> int:
def graph(x: str) -> str:
i, xarr = 0, list(x)
while x[i] == B[i]:i += 1
# it means that xarr[i]!=B[i], we need find xarr[j]==B[i] and swap, at the same time, xarr[j] should not equal to B[j]
for j in range(i + 1, len(A)):
if xarr[j] == B[i] and xarr[j] != B[j]:
this_xarr = xarr[:]
this_xarr[i], this_xarr[j] = xarr[j], xarr[i]
yield ''.join(this_xarr)
def bfs():
Q, seen = collections.deque([(A, 0)]), {A}
while Q:
x, d = Q.popleft()
for y in graph(x):
if y not in seen:
if y == B:return d + 1
seen.add(y)
Q.append((y, d+1))
if A==B:return 0
return bfs()847. Shortest Path Visiting All Nodes
This problem has similarities to TSP, however, it is not a TSP as we are allowed to visit one node multiple times. Although it is not a TSP problem, we can use the method in solving TSP problem to prune the unneeded states.
without pruning (TLE)
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
if any(len(g)==0 for g in graph):return 0
N = len(graph)
def bfs():
from collections import deque
Q = deque([(i, 0, {i}) for i in range(N)])
while Q:
i, d, seen = Q.popleft()
if len(seen)==N:return d
for j in graph[i]:
this_seen = seen | {j}
Q.append((j, d+1, this_seen))
return bfs()With pruning (AC 348 ms)
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
if any(len(g)==0 for g in graph):return 0
N = len(graph)
def bfs():
from collections import deque
Q = deque([(i, 0, {i}) for i in range(N)])
pruning = collections.defaultdict(lambda : float('inf'))
while Q:
i, d, seen = Q.popleft()
#pruning[tuple(sorted(seen))+(i,)]=d
if len(seen)==N:return d
for j in graph[i]:
this_seen = seen | {j}
this_key = tuple(sorted(this_seen))+(j,)
if pruning[this_key]>d+1:
pruning[this_key] = d+1
Q.append((j, d+1, this_seen))
return bfs()842. Split Array into Fibonacci Sequence
https://leetcode.com/problems/split-array-into-fibonacci-sequence/
Can use DFS to solve this problem. It is relatively hard as lots of edge case to consider such as non-leading zero. At the same time, the correct path is needed to be output.
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
L = len(S)
def dfs(fin_res, pre_val, val, i, cur_len):
fin_res = fin_res[:]
if len(val)>L-i:return False, []
elif len(val)==L-i:
if val == S[i:] and cur_len+1>=3:
fin_res.append(int(val))
if len(val)==1:return True, fin_res
elif S[i]!='0':return True, fin_res
else:return False, []
else:
if val == S[i:i+len(val)]:
new_val = int(val)+int(pre_val)
fin_res.append(int(val))
return dfs(fin_res, val, str(new_val), i+len(val), cur_len+1)
else:
return False, []
for i in range(1, len(S)-1):
if i>1 and S[0]=='0':continue
for j in range(1, len(S)-i):
if j>1 and S[i]=='0':continue
if i+j-1>=L:continue
pre_val, val = S[:i], S[i:i+j]
new_val = int(pre_val)+int(val)
#print(i,j, pre_val, val, new_val)
fin_res = [int(pre_val), int(val)]
good, res = dfs(fin_res, val, str(new_val), i+j, 2)
if good:
if max(res)<=2**31-1:return res
return []834. Sum of Distances in Tree
My code based on idea from
class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
tree = collections.defaultdict(set)
for a,b in edges:
tree[a].add(b)
tree[b].add(a)
root_nodes = [0]*N
def dfs_root_nodes(node, d,seen):
root_nodes[node] = d
seen.add(node)
for nxt_node in tree[node]:
if nxt_node not in seen:
dfs_root_nodes(nxt_node, d+1, seen.copy())
dfs_root_nodes(0, 0, set())
res = [0]*N
def node_counter(nxt_node, seen):
#print(seen)
if len(tree[nxt_node])==1:return 1
seen.add(nxt_node)
return 1+sum(node_counter(node, seen.copy()) for node in tree[nxt_node] if node not in seen)
def dfs_node_rest_nodes(node, d, seen):
#print(node)
res[node] = d
seen.add(node)
for nxt_node in tree[node]:
if nxt_node not in seen:
counter = node_counter(nxt_node, {node})
this_d = d - counter + (N-counter)
dfs_node_rest_nodes(nxt_node, this_d, seen.copy())
dfs_node_rest_nodes(0, sum(root_nodes), set())
return reshttps://leetcode.com/problems/sum-of-distances-in-tree/
class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
tree = collections.defaultdict(set)
res = [0] * N
count = [1] * N
for i, j in edges:
tree[i].add(j)
tree[j].add(i)def dfs(root, pre):
for i in tree[root]:
if i != pre:
dfs(i, root)
count[root] += count[i]
res[root] += res[i] + count[i]def dfs2(root, pre):
for i in tree[root]:
if i != pre:
res[i] = res[root] - count[i] + N - count[i]
dfs2(i, root)
dfs(0, -1)
dfs2(0, -1)
return res
827. Making A Large Island
https://leetcode.com/problems/making-a-large-island/
Union find
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
R, C = len(grid), len(grid[0])
self.uf = {}
def find(x):
self.uf.setdefault(x,x)
if x!=self.uf[x]:
self.uf[x]=find(self.uf[x])
return self.uf[x]
def union(x ,y):
self.uf[find(y)] = find(x)
ones = set()
for i in range(R):
for j in range(C):
if grid[i][j]:
x= C*i+j
ones.add(x)
neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]
for r, c in neighbors:
if 0<=r<R and 0<=c<C and grid[r][c]:
y = C*r+c
ones.add(y)
union(x,y)
cnt = collections.defaultdict(int)
for i in ones:
cnt[find(i)]+=1
if not cnt:return 1
M = max(cnt.values())
if M==0:return 1
for i in range(R):
for j in range(C):
if not grid[i][j]:
neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]
good_nei = [(r,c) for r,c in neighbors if 0<=r<R and 0<=c<C and grid[r][c]]
if good_nei:
roots = set()
for r, c in good_nei:
y = C*r+c
roots.add(find(y))
new_M = 1+sum(cnt[key] for key in roots)
M =max(M, new_M)
return M815. Bus Routes
https://leetcode.com/problems/bus-routes/
class Solution:
def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:
stop_bus = collections.defaultdict(set)
begin_bus = []
for i, route in enumerate(routes):
for stop in route:
if stop==S:
begin_bus.append(i)
stop_bus[stop].add(i)
if S ==T:return 0
def bfs(b):
if T in routes[b]:return 1
from collections import deque
Q = deque([(S,b, 1)])
seen_bus = {0}
while Q:
stop, bus, d = Q.popleft()
for stop in routes[bus]:
for nxt_bus in stop_bus[stop]:
if nxt_bus not in seen_bus:
if T in routes[nxt_bus]:return d+1
seen_bus.add(nxt_bus)
Q.append((stop, nxt_bus, d+1))
return -1
res = [bfs(b) for b in begin_bus]
fin_res = [r for r in res if r!=-1]
return min(fin_res) if fin_res else -1785. Is Graph Bipartite?
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = {}
def dfs(pos):
for i in graph[pos]:
if i in color:
if color[i] == color[pos]:
return False
else:
color[i] = 1 - color[pos]
if not dfs(i):
return False
return True
for i in range(len(graph)):
if i not in color:
color[i] = 0
if not dfs(i):
return False
return True