Select right as pivot element and left as fill position from left to right move elements smaller or equal to fill position and move the fill position to right Now p is the kth smallest element def quickselect(l, r): pivot = nums[r] p = l for i in range(l, r): if nums[i] <= pivot: nums[i], nums[p] = nums[p], nums[i] p += 1 nums[p], nums[r] = nums[r], nums[p] if p > k: return quickselect(l, p-1) elif p < k: return quickselect(p+1, r) else: return nums[p]
Problems 2385. Amount of Time for Binary Tree to Be Infected https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/ self.maxDistance = 0 def dfs(node): depth = 0 if not node: return depth leftDepth = dfs(node.left) rightDepth = dfs(node.right) if node.val == start: self.maxDistance = max(leftDepth, rightDepth) depth = -1 elif leftDepth >= 0 and rightDepth >= 0: depth = max(leftDepth, rightDepth) + 1 else: distance = abs(leftDepth) + abs(rightDepth) self.maxDistance = max(self.maxDistance, distance) depth = min(leftDepth, rightDepth) - 1 return depth dfs(root) return self....
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....