# Hard Graph

882. Reachable Nodes In Subdivided Graph

This problem is similar to

Key steps

1. build graph
2. 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.
3. 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 dequeclass 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

https://leetcode.com/problems/sum-of-distances-in-tree/discuss/130567/Two-traversals-O(N)-python-solution-with-Explanation

`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 res`

https://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 M`

# 815. 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 -1`

785. 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`

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi