SSSP Algorithm
Problem Used https://leetcode.com/problems/network-delay-time/
Time Complexity Dijkstra - V + ElogE - SSSP Time Complexity of Dijkstra's Algorithm is O(V^2) but due to minheap it drops down Bellman Ford - VE - SSSP : Bellman Ford is to check if there is a negative cycle in the graph, Floyd Warshall - V^3 - MSSP**
Dijkstra
from collections import defaultdict
import heapq
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
graph = defaultdict(list)
for i,j,w in times:
graph[i].append((j,w))
heap = [(0,K)]
array = [0] + [float("inf")] * N
while heap:
time,ele = heapq.heappop(heap)
if time < array[ele]:
array[ele] = time
for j,w in graph[ele]:
heapq.heappush(heap,(time+w,j))
if max(array) < float("inf"):
return max(array)
else:
return -1
Bellman Ford
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
array = [0] + [float("inf")] * N
array[K] = 0
for node in range(1,N):
for u,v,w in times:
if array[u] + w < array[v]:
array[v] = array[u] + w
if max(array) < float("inf"):
return max(array)
else:
return -1
Floyd Warshall
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
dist = [[float("inf") for i in range(N)] for j in range(N)]
for i in range(N):
dist[i][i] = 0
for u,v,w in times:
dist[u-1][v-1] = w
for k in range(N):
for i in range(N):
for j in range(N):
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
if max(dist[K-1]) < float("inf"):
return max(dist[K-1])
else:
return -1
MST Algorithms Time complexity Prim: O((V+E)logV) because each vertex is inserted in heap Kruskal : O(ElogV) most time consuming operation is sorting
Problem Used - https://leetcode.com/problems/connecting-cities-with-minimum-cost/
Prims
import heapq
import collections
class Solution:
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
graph = collections.defaultdict(list)
for a,b,w in connections:
graph[a].append((b,w))
graph[b].append((a,w))
visited,cost = set(),0
minHeap = [(0,1)]
while minHeap:
minCost,city = heapq.heappop(minHeap)
if city not in visited:
cost += minCost
visited.add(city)
for nxt,c in graph[city]:
if nxt not in visited:
heapq.heappush(minHeap,(c,nxt))
return -1 if len(visited) < N else cost
Kruskal
class Solution:
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
def find(node,par):
if par[node] == node:
return node
par[node] = find(par[node],par)
return par[node]
def union(a,b,par,rank1,a_rep,b_rep):
if rank1[a] == rank1[b]:
par[a_rep] = b_rep
rank1[a] += 1
elif rank1[a] > rank1[b]:
par[a_rep] = b_rep
else:
par[b_rep] = a_rep
parent = [x for x in range(N+1)]
rank = [1 for i in range(N+1)]
res,i,e,result = 0,0,0,[]
graph = sorted(connections,key = lambda x:x[2])
while i < len(graph) and e < N - 1:
u,v,w = graph[i]
uroot,vroot = find(u,parent),find(v,parent)
if uroot != vroot:
result.append([u,v])
res += w
e += 1
union(u,v,parent,rank,uroot,vroot)
i += 1
if len(result) == N-1:
return res
else:
return -1
Topological sort Problem Used - https://leetcode.com/problems/course-schedule/ Time Complexity: O(V+E)
from collections import defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph,queue,cnt = defaultdict(list),[],0
inDeg = [0] * numCourses
for j,i in prerequisites:
graph[i].append(j)
inDeg[j] += 1
for i in range(numCourses):
if inDeg[i] == 0:
queue.append(i)
while queue:
ele = queue.pop(0)
for j in graph[ele]:
inDeg[j] -= 1
if inDeg[j] == 0:
queue.append(j)
cnt += 1
if cnt == numCourses:
return True
else:
return False
Generic Union Find Problem Used - https://leetcode.com/problems/friend-circles/ Time Complexity for Union Find : O(logV)
class UnionFind:
def __init__(self, V):
self.id = [i for i in range(V)]
self.size = [1 for _ in range(V)]
def find(self, node):
root = node
while self.id[root]!=root:
root = self.id[root]
while node != root:
next = self.id[node]
self.id[node] = root
node = next
return root
def unify(self, p1, p2):
parent1 = self.find(p1)
parent2 = self.find(p2)
size_parent1 = self.size[parent1]
size_parent2 = self.size[parent2]
if size_parent1 < size_parent2:
self.id[parent1] = parent2
size_parent2 += size_parent1
else:
self.id[parent2] = parent1
size_parent1 += size_parent2
Graph coloring/Bipartition
Problem Used - https://leetcode.com/problems/is-graph-bipartite/
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
adj_table = collections.defaultdict(list)
for idx,val in enumerate(graph):
adj_table[idx] = val
vis = [False for i in range(n)]
for i in range(n):
if not vis[i] and adj_table[i]:
queue = [i]
vis[i] = 0
while queue:
x = queue.pop(0)
for i in adj_table[x]:
if not vis[i]:
vis[i] = 1 - vis[x]
queue.append(i)
else:
if vis[i] == vis[x]:
return False
return True
Cycle detection: Problem used: https://leetcode.com/problems/find-eventual-safe-states/
Directed graph:
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
def is_safe(u, rec_stack):
if u in visited:
return u not in rec_stack and u not in unsafe
visited.add(u)
rec_stack.add(u)
for v in graph[u]:
if not is_safe(v, rec_stack):
unsafe.add(u)
return False
rec_stack.remove(u)
return True
unsafe, visited = set(), set()
for u in range(len(graph)):
if u not in visited: is_safe(u, set())
return sorted([u for u in range(len(graph)) if u not in unsafe])
Undirected graph:
def DFS(graph, v, discovered, parent):
discovered[v] = True
for w in graph.adjList[v]:
if not discovered[w]:
if DFS(graph, w, discovered, v):
return True
elif w != parent:
return True
return False
discovered = [False] * N
DFS(graph, 1, discovered, -1)
DP patterns: https://leetcode.com/discuss/general-discussion/972402/Python-template-for-DP-patterns-One-Place-for-quick-revision Tree: https://leetcode.com/discuss/general-discussion/1019622/Python-template-Tree-questions-in-One-Place-for-quick-revision EDGE case: https://leetcode.com/discuss/general-discussion/988504/Edge-cases-to-consider-during-problem-solving Please let me know if you found any mistakes and will update remaining patterns on this post
DP Patterns that I use while revision: https://leetcode.com/discuss/general-discussion/662866/DP-for-Beginners-Problems-or-Patterns-or-Sample-Solutions
https://leetcode.com/discuss/study-guide/458695/dynamic-programming-patterns/915726