Leetcode

visited = set() def dfs(u): if u == destination: return True if u in visited: return False visited.add(u) for v in adj[u]: if (dfs(v)): return True return False return dfs(source) stack = [source] visited = set() while stack: u = stack.pop() if u == destination: return True if u in visited: continue visited.add(u) for v in adj[u]: stack.append(v) return False Problems 332. Reconstruct Itinerary https://leetcode.com/problems/reconstruct-itinerary/description/ Eulerian path adj = defaultdict(list) for u, v in tickets: adj[u]....

To find number of events occuring at a given point affected by multiple ranges. Problems 370. Range Addition https://leetcode.com/problems/range-addition When event starts increase the value at the start position When it ends decrease the value at the end position starts = defaultdict(int) ends = defaultdict(int) for s, e, inc in updates: starts[s] += inc ends[e] += inc inc = 0 res = [] for i in range(length): inc += starts[i] res....

if gcd(a,b) > 1 there share a prime factor Sieve of eratosthenes n = 100 sieve = [0]*(n+1) for i in range(2, n+1): if sieve[i] == 0: for j in range(i, n+1, i): sieve[j] = i primes = [] for i in range(2, n+1): if sieve[i] == i: primes.append(i) print(primes) Prime factors n = 12 sieve = [0]*(n+1) for i in range(2, n+1): if sieve[i] == 0: for j in range(i, n+1, i): sieve[j] = i pfactors = [] val = n while val > 1: prime = sieve[val] pfactors....

class UnionFind(): def __init__(self, n): self.root = [i for i in range(n)] self.sz = [1] * n self.n_components = n def find(self, a): root = a while root != self.root[root]: root = self.root[root] while a != root: nxt = self.root[a] self.root[a] = root a = nxt return root def union(self, a, b): root1 = self.find(a) root2 = self.find(b) if root1 == root2: return root1 if self.sz[root1] > self.sz[root2]: self.root[root2] = root1 self....

q = deque() q.append(start) visited = set() visited.add(start) while q: u = q.popleft() for v in adj[u]: if v not in visited: visited.add(v) q.append(v) Problems 2092. Find All People With Secret https://leetcode.com/problems/find-all-people-with-secret Revisit the node based if the secret is know to that node earliest. Revisit the node if better option is found in the later point. Multi source bfs revisiting the nodes if better option is found. 1q = deque() 2q....

dist = [inf] * (n+1) dist[src] = 0 q = deque() q.append(src) visited = set() visited.add(src) while q: u = q.popleft() visited.remove(u) for v, d in adj[u]: if dist[u] + d < dist[v]: if v not in visited: q.append(v) visited.add(v) dist[v] = dist[u] + d

# O(V*E) dist = [inf] * n dist[src] = 0 for i in range(n-1): changed = False for u, v, d in edges: if dist[u] + d < dist[v]: dist[v] = dist[u] + d changed = True if not changed: break Problems 787. Cheapest Flights Within K Stops https://leetcode.com/problems/cheapest-flights-within-k-stops Apply bellman ford for k+1 iterations

Initialize dist = [inf] * n Place start in a min heap For all its neighbors update the dist[v] = dist[u] + d if dist[v] > dist[u] + d and add to min heap # O(V + E*log(V)) dist = [inf] * (n) dist[src] = 0 mi_heap = [[0, src]] visited = set() while mi_heap: dist, u = heappop(mi_heap) visited.add(u) for v, t in adj[u]: if v in visited: continue if dist[u] + t < dist[v]: dist[v] = dist[u] + t heappush(mi_heap, [dist[v], v]) Problems 743....

Dijkstra’s single shource shortest path Bellman Ford SPFA (Shortest Path Faster Algorithm)