Course Scheduler 1
Hi, here’s your problem today. This problem was recently asked by Google:
You are given a hash table where the key is a course code, and the value is a list of all the course codes that are prerequisites for the key. Return a valid ordering in which we can complete the courses. If no such ordering exists, return NULL.
Example:
{
'CSC300': ['CSC100', 'CSC200'],
'CSC200': ['CSC100'],
'CSC100': []
}This input should return the order that we need to take these courses:
[‘CSC100’, ‘CSC200’, ‘CSCS300’]
Here’s your starting point:
def courses_to_take(course_to_prereqs): # Fill this in.
courses = {
'CSC300': ['CSC100', 'CSC200'],
'CSC200': ['CSC100'],
'CSC100': []
}
print courses_to_take(courses)
# ['CSC100', 'CSC200', 'CSC300']- topological sort
- if we find a cycle, back-edge or otherwise, return failed, in this case, None
- items that have children are courses that have prerequisites. Topological sort returns a list where the items ordered in a way which edge A->V, A comes before V
- We can just append items to a list and return the list. We do not guarantee that any order of edges is maintained, we can say A->V and B->V, it can return [A. B..] or [B, A…] depending on the input
- KEY POINT when you have directed graphs like this, the recent stack is a key strategy. it lets you keep track of events for the single loop then forget
Time: O(n), where n is the number of keys. The edges of the keys are already included in n, so we do not need to include them
Space: O(3n), we have 3 lists that can be the size of the graph
class Solution:
- —def answer(self, graph):
- ——-visited=defaultdict(lambda: False)
- ——-recent_stack=defaultdict(lambda: False)
- ——-stack=[]
- ——-for vertex in graph.keys():
- ———–if not visited[vertex]:
- —————if self.answer_helper(vertex, graph, visited, recent_stack, stack):
- ——————-return None
- ——-return stack
- —def answer_helper(self, vertex, graph, visisted, recent_stack, stack):
- ——-visisted[vertex]=True
- ——-recent_stack[vertex]=True
- ——-for vertex2 in graph[vertex]:
- ———–if not visisted[vertex2]:
- —————if self.answer_helper(vertex2, graph, visisted, recent_stack, stack):
- ——————-return True
- ———–elif recent_stack[vertex2]:
- —————return True
- ——-recent_stack[vertex]=False
- ——-stack.append(vertex)
- ——-return False
Works = {
'CSC300': ['CSC100', 'CSC200'],
'CSC200': ['CSC100'],
'CSC100': []
}
Does not work = {
'CSC300': ['CSC100', 'CSC200'],
'CSC200': ['CSC100'],
'CSC100': ['CSC300]
}
Works = {
'g': ['e', 'f'],
'f': ['d', 'c'],
'e': ['d', 'c', 'b'],
'd': ['b', 'a'],
'c': ['b', 'a'],
'b': ['a'],
'a': []
}Cycle in graph
Given an undirected graph, determine if a cycle exists in the graph.
undirected_graph_true = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A"],
"D": ["A", "B", "E"],
"E": ["D"]
}- Know what a directed vs undirected graph is
- Need a map to keep track of visited vertexes
- On a new edge, check if edge has been seen before and if it is not the edges parent, if so we have cycle
- recursive, make sure your recursive function exits properly
- understand the if conditionals are key. If edge not in visited map, recursive call, elif edge!=parent, return true
- recursive calls return a boolean, so make sure they are in the if conditional
time: O n, do not include the edges of the graph bc they are included in the vertexes
space: O n, the visited map can grow to the size of the graph
- —def answer(self, graph):
- ——-visited={}
- ——-for vertex in graph.keys():
- ———–if vertex not in visited:
- —————if self.__helper(graph, vertex, “”, visited):
- ——————-return True
- ——-return False
- —def __helper(self, graph, vertex, parent, visited):
- ——-visited[vertex]=True
- ———–if edge not in visited:
- ————— if self.__helper(graph, edge, vertex, visited):
- ——————- return True
- ———–elif edge!=parent:
- ————— return True
- ——-return False
strategies for graphs and how to recognize a graph problem
Know your directed/cyclic/tological/disjoined graphs
If they talk about things connecting, probably a graph problem
- Number of Provinces
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
- This is a disjointed graph, know the optimized path/unions for a disjointed graph class
- loop through the matrix, at each intersection, check if 1 and that the row/column are not equal. if so, union them
- must realize that if you are on row 5, then you can start at column 5 since previous columns have already checked if they are connected to your current column, so you do not need to backwards check them
- once finished, call find on all the values in the array, not all root nodes have been updated since some values could have been updated to an outdated value that does not point to the same root note anymore
time: O N^2 + N. optimized path/union are amortized constant time, N bc we build the disjointed graph, optimized union find would be
space: N for the disjointed graph
class Solution:
- —def findCircleNum(self, isConnected) -[greater than] int:
- ——-n = len(isConnected[0])
- ——-graph = Dg(n)
- ——-for i in range(len(isConnected)):
- ———–connections = []
- ———–for j in range(i, len(isConnected[i])):
- —————if isConnected[i][j] is 1 and i is not j:
- ——————-n -= graph.union(i, j)
- —————’’’
- —————can only get above if you realize that at each following row, you don’t need to check the rows before
- —————1 1 0
- —————1 1 0
- —————0 0 1
- —————we see that index 0 was unioned with index 1, then when we get to row 2 we only need to see if index 1 joins with any
- —————following city
- —————’’’
- —————# if isConnected[i][j] is 1:
- —————#—- connections.append(j)
- —————# if len(connections) is 2:
- —————#—- y = connections.pop()
- —————#—- n -= graph.union(connections[0], y)
- ——-return n
-------- class Dg: ----def \_\_init\_\_(self, size): --------self.root = [i for i in range(size)] --------self.rank = [1 for i in range(size)] -------- ----def find(self, x): --------if x is not self.root[x]: ------------self.root[x] = self.find(self.root[x]) ------------return self.root[x] --------return x ---- ----def union(self, x, y): --------rootX = self.find(x) --------rootY = self.find(y) --------if rootX is not rootY: ------------if self.rank[rootX] [greater than] self.rank[rootY]: ----------------self.root[rootY] = rootX ------------elif self.rank[rootX] [less than] self.rank[rootY]: ----------------self.root[rootX] = rootY ------------else: ----------------self.root[rootY] = rootX ----------------self.rank[rootX] +=1 ------------return 1 --------return 0
Graph Valid Tree
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
- disjointed graphs can not only create a graph/tree, but can tell you if there is a cycle if you union any items and they have the same root node after the find function
- if the edges are less than the nodes, it means we do not see all of the nodes, therefore, it is not valid
time: O (N + a(N)) where a(n) is the inverse ackerman function since we used optimized union and find. the ackerman function only gets as large as 4 for reasonable inputs, so in practice it is a constant time operation
space: O (N) to keep the array for root/graph
class Solution: ----def validTree(self, n: int, edges): --------if len(edges) != n -1: ------------return False --------dg = DisjointedGraph(n) -------- --------for x, y in edges: ------------if not dg.union(x, y): ----------------return False --------return True ---- class DisjointedGraph: ----def \_\_init\_\_(self, size): --------self.root = [i for i in range(size)] --------self.rank = [1 for i in range(size)] -------- ----def find(self, x): --------if x is not self.root[x]: ------------self.root[x] = self.find(self.root[x]) ------------return self.root[x] --------return x ---- ----def union(self, x, y): --------rootX = self.find(x) --------rootY = self.find(y) --------if rootX is rootY: ------------return False --------if rootX is not rootY: ------------if self.rank[rootX] [greater than] self.rank[rootY]: ----------------self.root[rootY] = rootX ------------elif self.rank[rootY] [greater than] self.rank[rootX]: ----------------self.root[rootX] = rootY ------------else: ----------------self.root[rootY] = rootX ----------------self.rank[rootX] += 1 --------return True
- Number of Connected Components in an Undirected Graph
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph
- you see an object has N nodes, you see there are edges, instantly think disjointed graph!
- This one is very simple create the disjointed graph with optimized find and union, run find on all the nodes to check for old root references, add all the find results to a set, return len(set)
time: O (N + a(m)) where a(m) is ackerman’s function, which is constant, max goes up to 4
space: O N for the graph/response
class Solution:
- —def countComponents(self, n: int, edges):
- ——-graph = Dg(n)
- ——-response = n
- ——-for x, y in edges:
- ———–response -= graph.union(x, y)
- ——-‘’’
- ——-If you don’t see how each successful union would subtract 1 from the total possible nodes, you can do a regular disjointed graph,
- ——-then do find on each node, adding each find result to a set, return length of set
- ——-for i in range(len(graph.root)):
- ———–root = graph.find(i)
- ———–response.add(root)
- ———–return len(response)
- ——-‘’’
- ——-return response
- alternative non-disjointed graph method, requires a decent understanding of how you can represent the edges via a list
- —def DFS(self, n: int, edges):
- ——-li = [[] for i in range(n)]
- ——-visited = [False for i in range(n)]
- ——-ans = 0
- ——-for x, y in edges:
- ———–li[x].append(y)
- ———–li[y].append(x)
- ——-for i in range(n):
- ———–if not visited[i]:
- —————ans += 1
- —————self.search(li, visited, i)
- ——-return ans
- —def search(self, li, visited, i):
- ——-visited[i] = True
- ——-for x in li[i]:
- ———–if not visited[x]:
- —————self.search(li, visited, x)
class Dg:
- —def __init__(self, size):
- ——-self.root = [i for i in range(size)]
- ——-self.rank = [1 for i in range(size)]
- —def find(self, x):
- ——-if x is not self.root[x]:
- ———–self.root[x] = self.find(self.root[x])
- ———–return self.root[x]
- ——-return x
- —def union(self, x, y):
- ——-rootX = self.find(x)
- ——-rootY = self.find(y)
- ——-if rootX is not rootY:
- ———–if self.rank[rootX] [greater than] self.rank[rootY]:
- —————self.root[rootY] = rootX
- ———–elif self.rank[rootX] [less than] self.rank[rootY]:
- —————self.root[rootX] = rootY
- ———–else:
- —————self.root[rootY] = rootX
- —————self.rank[rootX] += 1
- ———–return 1
- ——-else:
- ———–return 0
The Earliest Moment When Everyone Become Friends
There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi.
Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b.
Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return -1.
- we have N-1 items, some semblance of connectivity? disjointed graph!
- if you need to figure out when all the edges are grouped (have 1 root node) each successful union subtract 1 from N, when you get 1 you have 1 node left
time: e*log(e) + N + e, sorting + create graph + loop through edges
space: N for the graph + N for recursion depth of quick sort (average could be log(n))
class Solution:
- —def earliestAcq(self, logs, n):
- ——-self.root = [i for i in range(n)]
- ——-self.rank = [1 for i in range(n)]
- ——-islands = n
- ——-response = -1
- ——-for t, x, y in sorted(logs):
- ———–islands -= self.union(x, y)
- ———–if islands == 1:
- —————return t
- ——-return response
- —def find(self, x):
- ——-if x is not self.root[x]:
- ———–self.root[x] = self.find(self.root[x])
- ———–return self.root[x]
- ——-return x
- —def union(self, x, y):
- ——-rootX = self.find(x)
- ——-rootY = self.find(y)
- ——-if rootX is not rootY:
- ———–if self.rank[rootX] [greater than] self.rank[rootY]:
- —————self.root[rootY] = rootX
- ———–elif self.rank[rootY] [greater than] self.rank[rootX]:
- —————self.root[rootX] = rootY
- ———–else:
- —————self.root[rootY] = rootX
- —————self.rank[rootX] += 1
- ———–return 1
- ——-return 0
Smallest string with swaps
You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd"
- nested list with pairs? DISJOINTED GRAPH
- after you union and create the graph you can make a map with collections import defaultdict, with defaultdict(lambda: []) of root nodes, and all possible children of that root node
- “dcab” = {0:[d, b], 1: [c, a]}.
- if you use binary search to find the first index larger than your search target, you can create a sorted list for each index in log(N) time
- then, to create the best answer, you loop through the string and call find on each index, to return the specific root node list, then pop(0) to get the smallest value (or smallest letter)
time: creating graph is N, greating defaultdict while keeping the lists sorted is Nlog(N), returning final response is N, so N + Nlog(n)
space: N for the graph, N for the default dict, so 2N or just N
class Solution: ----def smallestStringWithSwaps(self, s, pairs): --------from collections import defaultdict --------graph = Dg(len(s)) -------- --------for x, y in pairs: ------------graph.union(x, y) -------- --------m = defaultdict(lambda: []) --------for i in range(len(s)): ------------index = graph.find(i) ------------found_index = self.binary_search(s[i], m[index]) ------------m[index].insert(found_index, s[i]) -------- --------response = [] --------for i in range(len(s)): ------------response.append(m[graph.find(i)].pop(0)) --------return "".join(response) -------- ----def binary_search(self, target, arr): --------if len(arr) is 0: ------------return 0 --------high = len(arr)-1 --------low = 0 --------while high [greater than]= low: ------------mid = (high + low) // 2 ------------if arr[mid] is target: ----------------return mid ------------elif arr[mid] [greater than] target: ----------------high = mid - 1 ------------elif arr[mid] [less than] target: ----------------low = mid + 1 --------return low -------- class Dg: ----def \_\_init\_\_(self, size): --------self.root = [i for i in range(size)] --------self.rank = [1 for i in range(size)] ----def find(self, x): --------if x is not self.root[x]: ------------self.root[x] = self.find(self.root[x]) ------------return self.root[x] --------return x ----def union(self, x, y): --------if x [less than] y: ------------low = x ------------high = y --------else: ------------low = y ------------high = x --------rootX = self.find(low) --------rootY = self.find(high) --------if rootX is not rootY: ------------if self.rank[rootX] [greater than] self.rank[rootY]: ----------------self.root[rootY] = rootX ------------elif self.rank[rootX] [less than] self.rank[rootY]: ----------------self.root[rootX] = rootY ------------else: ----------------self.root[rootY] = rootX ----------------self.rank[rootX] +=1
- Evaluate Division
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Example 1:
Input: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
Example 2:
Input: equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:
Input: equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
Output: [0.50000,2.00000,-1.00000,-1.00000]
- this is a graph problem
- this is a HARD graph problem
time: O((equations + queries )* log(N) ) where N is the number of nodes in the disjointed graph we make. We have to loop through equations to make the map and the graph, the queries to get the answer
space: O(equations), this would count the size of the map and graph. If we included size of output, we add queries to space too
class Solution:
- —def calcEquation(self, equations, values, queries):
- ——-mappings = {}
- ——-index = 0
- ——-for x, y in equations:
- ———–if x not in mappings:
- —————mappings[x] = index
- —————index += 1
- ———–if y not in mappings:
- —————mappings[y] = index
- —————index += 1
- ——-dg = Dg(index)
- ——-for i in range(len(equations)):
- ———–letter1, letter2 = equations[i]
- ———–value = values[i]
- ———–dg.union(mappings[letter1], mappings[letter2], value)
- ——-result = []
- ——-for letter1, letter2 in queries:
- ———–if letter1 not in mappings or letter2 not in mappings:
- —————result.append(-1.0)
- ———–else:
- —————rootX, weightX = dg.find(mappings[letter1])
- —————rootY, weightY = dg.find(mappings[letter2])
- —————if rootX != rootY:
- ——————-result.append(-1.0)
- —————else:
- ——————-result.append(weightX / weightY)
- ——-return result
class Dg:
- —def __init__(self, size):
- ——-self.root = [[i, 1] for i in range(size)]
- —def find(self, x):
- ——-root, weight = self.root[x]
- ——-if x != root:
- ———–new_root, new_weight = self.find(root)
- ———–self.root[x] = [new_root, weight * new_weight]
- ———–return self.root[x]
- ——-return self.root[x]
- —def union(self, x, y, value):
- ——-rootX, weightX = self.find(x)
- ——-rootY, weightY = self.find(y)
- ——-if rootX != rootY:
- ———–self.root[rootX] = [rootY, value * weightY / weightX]
BRUTE FORCE
- create a custom graph with all the edges, performing calculations on each edge
- backtrack through the queries using a backtracing function, check if the queries inputs are equal and return 1 if they are (the backtrack method doesn’t account for equals naturally)
- figure out the base case, when do we want to return something? not always, we want to return it when it is not -1 in the loop, but we also want to return -1 if there are no other options
time: O(equations * queries), each equation in the graph can be seen by each query in the second loop
space: O(N), the graph’s edges are 2N with no overlap, the keys then count for N. The recursion depth fo the backtracking is also N
class Solution:
- —def calcEquation(self, equations, values, queries):
- ——-from collections import defaultdict
- ——-graph = defaultdict(defaultdict)
- ——-for i in range(len(equations)):
- ———–x, y = equations[i]
- ———–value = values[i]
- ———–graph[x][y] = value
- ———–graph[y][x] = 1 / value
- ——-response = []
- ——-for x, y in queries:
- ———–if x not in graph or y not in graph:
- —————value = -1.0
- ———–elif x == y:
- —————value = 1.0
- ———–else:
- —————visisted = set()
- —————value = self.backtracking(x, y, 1, visisted, graph)
- ———–response.append(value)
- ——-return response
- —def backtracking(self, x, y, value, visited, graph):
- ——-visited.add(x)
- ——-children = graph[x]
- ——-response = -1.0
- ——-if y in children:
- ———–return value * children[y]
- ——-else:
- ———–for child, child_value in children.items():
- —————if child in visited:
- ——————-continue
- —————’’’
- —————We do it this way bc there is no guarantee that the recursion finds anything important. It could return -1
- —————if the first child has no children since it won’t continue through the backtracing. This is a problem if the————————second has the answer. For this reason we have to employ the back tracking base case
- —————method which is, we need to know what we are looking for, if it isn’t -1, we found it
- —————’’’
- —————response = self.backtracking(child, y, value * child_value, visited, graph)
- —————if response != -1.0:
- ——————-break
- —————# else:—————-
- —————#—- return self.backtracking(child, y, value * child_value, visited, graph)
- ——-# not needed, but it must improve it somehow, I don’t see it.
- ——-# visited.remove(x)
- ——-return response
find if path exists in graph
There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
You want to determine if there is a valid path that exists from vertex start to vertex end.
Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.
optimized union find, union all the edges, test if start is connected to end
time: N + E*ackerman(N)
space: N for the graph
alternative
- DFS or BFS
- make a graph
- start traversal at the node we are starting, each time we search its children we check if the target == end, if it does we return True, if we fail to find it we return False
time: N + E bc we traverse through all the edges to make the graph, then all the nodes in the search
space: N^2, worst-case each node is connected to each other node (check graph card, traversing all paths between 2 points explanation)
from collections import defaultdict
class Solution:
- —def validPath(self, n: int, edges, start: int, end: int):
- ——-if not edges:
- ———–return True
- ——-graph = defaultdict(lambda: [])
- ——-for x, y in edges:
- ———–graph[x].append(y)
- ———–graph[y].append(x)
- ——-visited = set()
- ——-if self.find_path(start, end, graph, visited):
- ———–return True
- ——-return False
- —def find_path(self, root, target, graph, visited):
- ——-visited.add(root)
- ——-if root == target:
- ———–return True
- ——-children = graph[root]
- ——-for child in children:
- ———–if child not in visited:
- —————if self.find_path(child, target, graph, visited):
- ——————-return True
- ——-return False
- —def BFS(self, n: int, edges, start: int, end: int):
- ——-if not edges:
- ———–return True
- ——-graph = defaultdict(lambda: [])
- ——-for x, y in edges:
- ———–graph[x].append(y)
- ———–graph[y].append(x)
- ——-visited = set()
- ——-queue = [start]
- ———–current = queue.pop(0)
- ———–if current not in visited:
- —————visited.add(current)
- —————for child in graph[current]:
- ——————-if child == end:
- ———————–return True
- ——————-queue.append(child)
- ——-return False
All Paths From Source to Target
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
Example 1:
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
- backtracking!
- traverse graph, the index of the graph shows all paths from that index
- base case is there are no children left or that the input equals the target
- after each loop OR when we find the target, pop an item off the current list
time: O((2^N) * N), adding another node doubles the possible paths for a DAG, (undirected is N!), and N bc for each path we append an item to the result which takes N time
space: O((2^N) * N), we have that many paths that have N length in the response, but without response we just have N bc of the carry_list + recursion stack
from functools import lru_cache class Solution: ----def allPathsSourceTarget(self, graph): --------n = len(graph) - 1 --------response = [] -------- --------self.backtrack(graph, 0, [], response, n) --------return response ---- ----def backtrack(self, graph, index, carry_list, response, n): --------carry_list.append(index) --------if index == n: ------------response.append(list(carry_list)) ------------carry_list.pop() ------------return -------- --------for child in graph[index]: ------------self.backtrack(graph, child, carry_list, response, n) ------------ --------carry_list.pop()
- same time/space as above, but you have to be creative on how you make the recursive function
- you need a nested list for the recursive function to make sense, not very intuitive
- —def dynamic_programming(self, graph):
- ——-self.n = len(graph) - 1
- ——-self.memo = {}
- ——-self.graph = graph
- ——-response = self.helper(0)
- ——-return response
- —@lru_cache(maxsize=None)
- —def helper(self, current):
- ——-# if current in self.memo:
- ——-#—- return self.memo[current]
- ——-if current == self.n:
- ———–return [[current]]
- ——-result = []
- ——-for child in self.graph[current]:
- ———–for r in self.helper(child):
- —————result.append([current] + r)
- ——-# self.memo[current] = result
- ——-return result
- same time analysis as before
- queues are necessary for almost all BFS solutions
- —def BFS(self, graph):
- ——-n = len(graph) - 1
- ——-response = []
- ——-
- ——-queue = [[0]]
- ——-while queue:
- ———–current = queue.pop(0)
- ———–paths = graph[current[-1]]
- ———–for path in paths:
- —————if path == n:
- ——————-response.append(current + [path])
- —————else:
- ——————-queue.append(current + [path])
- ——-return response
Clone Graph
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List neighbors;
}Test case format:
For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
- DFS! I call it backtracking, without pop it is probably DFS
- make a visited map, check if you have seen map before, make sure to work with the same nodes once you have created it
- copy as you go, get the node you are working with if it exists, if not make one
time: O(N + M) where N is the nodes and M are edges, it looks like it could be N^2, but you see each node during the DFS algo, and each node will call each of their edges. This can be confusing, but it is standard graph theory if you do DFS with a map checking if you have seen it before
space: O(n) bc of the map, the recursion stack would give O(H) but worst case H=N since each node could be connected to each other node
class Solution:
- —def cloneGraph(self, node: ‘Node’) -[greater than] ‘Node’:
- ——-if not node:
- ———–return None
- ——-ans = Node(node.val)
- ——-self.map = {}
- ——-self.backtracking(node, ans)
- ——-return ans
- —def backtracking(self, current, new_current):
- ——-if current.val in self.map:
- ———–return
- ——-self.map[current.val] = new_current
- ——-for child in current.neighbors:
- ———–if child.val in self.map:
- —————new_child = self.map[child.val]
- ———–else:
- —————new_child = Node(child.val)
- ———–new_current.neighbors.append(new_child)
- ———–self.backtracking(child, new_child)
- with BFS, you usually have to start off the stack/queue with some values, make sure you if you initialize 1 data structure to begin a function, do the other ones related to it as well, in this case, that is the visited map
- instead of for each while loop checking if we have seen current before, we only add current to the stack if we have not seen that child yet, this will prevent infinite looping
time/space are same as above
- —def BFS(self, node: ‘Node’) -> ‘Node’:
- ——-if not node:
- ———–return node
- ——-visited = {node.val: Node(node.val)}
- ——-queue = deque([node])
- ——-while queue:
- ———–current = queue.popleft()
- ———–for child in current.neighbors:
- —————if child.val not in visited:
- ——————-queue.append(child)
- ——————-new_child = Node(child.val)
- ——————-visited[child.val] = new_child
- —————else:
- ——————-new_child = visited[child.val]
- —————visited[current.val].neighbors.append(new_child)
- ——-return visited[node.val]
Reconstruct itinerary
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
Output: [“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]
- backtracking
- need a way to check if we have seen the values before during the backtracking sessions
- careful how you start the backtracking list, since we know we start from JFK we can init the list with that
- because we created the graph in ABC order, we know the first solution we find will be the best one, so we have to return it and stop the problem
time: O(E^D) where E is the number of flights and D is the flights from airports
space: A + E A is the number of airports and E is the number of flights. The hashmaps we make are A+ E, recursive stack is at most E bc of the result
from collections import defaultdict
import random
class Solution:
- —def findItinerary(self, tickets):
- ——-self.target_length = len(tickets) + 1
- ——-self.graph = defaultdict(list)
- ——-self.seen = defaultdict(list)
- ——-for start, destination in tickets:
- ———–# index = self.binary_insert(graph[start], destination)
- ———–self.graph[start].append(destination)
- ———–self.seen[start].append(False)
- ——-for start, destinations in self.graph.items():
- ———–self.qs(destinations, 0, len(destinations) - 1)
- ———–# destinations.sort() # qs, bubble sort, heap sort, merge sort
- ——-self.response = []
- ——-self.graph_search(“JFK”, [“JFK”])
- ——-return self.response
- —def graph_search(self, current, carry_list):
- ——-if len(carry_list) == self.target_length:
- ———–self.response = list(carry_list)
- ———–return True
- ——-for i in range(len(self.graph[current])):
- ———–if not self.seen[current][i]:
- —————dest = self.graph[current][i]
- —————self.seen[current][i] = True
- —————carry_list.append(dest)
- —————done = self.graph_search(dest, carry_list)—-
- —————self.seen[current][i] = False
- —————carry_list.pop()
- —————if done:
- ——————-return True
- ——-return False
- —def qs(self, arr, left, right):
- ——-if right [greater than]= left:
- ———–pi = self.partition(arr, left, right)
- ———–self.qs(arr, left, pi - 1)
- ———–self.qs(arr, pi + 1, right)
- —def partition(self, arr, left, right):
- ——-pivot_index = random.randint(left, right)
- ——-arr[right], arr[pivot_index] = arr[pivot_index], arr[right]
- ——-low = left
- ——-for i in range(left, right):
- ———–if arr[i] [less than] pivot:
- —————arr[low], arr[i] = arr[i], arr[low]
- —————low += 1
- ——-arr[right], arr[low] = arr[low], arr[right]
- ——-return low
populating next node’s pointer
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.Initially, all next pointers are set to NULL.
Example 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.
- Since we are given another use of the data structure, it is DEFINITELY RELEVANT.
- if the root node has a right, then the root.right.next is equal to the root.next.left
- in this case, the recursive stack doesnt count as space (as per the problem statement)
- you can also think of nodes on the same level as a linked list
time: O(n), we visit all the nodes
space: O(n) recursive stack (constant otherwise)
class Solution:
- —def optimal(self, root: ‘Node’) -[greater than] ‘Node’:
- ——-if not root:
- ———–return root
- ——-root.next = None
- ——-self.recursive(root)
- ——-return root
- —def recursive(self, root):
- ——-if root.left:
- ———–left = root.left
- ———–right = root.right
- ———–left.next = right
- ———–if root.next:
- —————right.next = root.next.left
- ———–self.recursive(left)
- ———–self.recursive(right)
time: O(n), we visit all the nodes
space: constant
- —def iterative(self, root: ‘Node’) -[greater than] ‘Node’:
- ——-if not root:
- ———–return root
- ——-root.next = None
- ——-left_most = root
- ——-while left_most.left:
- ———–head = left_most
- ———–while head:
- —————head.left.next = head.right
- —————if head.next:
- ——————-head.right.next = head.next.left
- —————head = head.next
- ———–left_most = left_most.left
- ——-return root
time: O(n), we visit all the nodes
space: O(n), the queue
- —def BFS(self, root: ‘Node’) -[greater than] ‘Node’:
- ——-if not root:
- ———–return root
- ——-root.next = None
- ——-queue = [root]
- ——-while queue:
- ———–for i in range(len(queue)):
- —————current = queue.pop(0)
- —————if current.left: queue.append(current.left)
- —————if current.right: queue.append(current.right)
- ———–for i in range(len(queue) - 1):
- —————queue[i].next = queue[i + 1]
- ——-return root
shortest path in binary matrix
Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.
2 solutions do the same thing except 1 modifies the input data. It is important to ask if we can do this as a clarification so the interviewer thinks we are smart. This is bc in a multithreaded program, we cannot modify the input bc another thread might be using it
- shortest path in a graph? BFS!
- create a visited map and make sure we do not visit the same point on the grid twice
- bfs uses queues not stacks
- know base case, if we are at the bottom right of the graph, check the graph to begin to make sure it is possible to have a solution
- you can use a generator here to improve time, in the unique case of a generator here, the for-loop in the generator that is called using another for-loop does not reset on each external loop, each item in the generator for-loop function is only called once
time: O(n), the visited matrix only allows each cell to be visited once. The inner loop for all the surrounding cells is also size 8, so it is a constant operation
space: O(n), the queue can grow to size very close to N in large inputs, also the visited matrix could be size N
class Solution:
—-def overwrite_input(self, grid):
——–self.grid = grid
——–self.n = len(self.grid)
——–if self.grid[0][0] != 0 or self.grid[self.n - 1][self.n - 1] != 0:
————return -1—-
——–
——–self.directions = [
————(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
——–
——–queue = [(0,0)]
——–self.grid[0][0] = 1
——–
——–while queue:
————row, col = queue.pop(0)
————distance = self.grid[row][col]
————if row == self.n - 1 and col == self.n - 1:
—————-return distance
————else:
—————-for adj_row, adj_col in self.get_valid_neighbors(row, col):
——————–self.grid[adj_row][adj_col] = distance + 1
——————–queue.append((adj_row, adj_col))
——–return -1
—-
—-def get_valid_neighbors(self, row, col):
——–for dr, dc in self.directions:
————new_row = row + dr
————new_col = col + dc
————if not (0 [less than]= new_row [less than]= self.n - 1 and 0 [less than]= new_col [less than]= self.n - 1):
—————-continue
————if self.grid[new_row][new_col] == 0:
—————-yield (new_row, new_col)
- —def dont_modify_input(self, grid):
- ——-max_row = len(grid) - 1
- ——-max_col = len(grid[0]) - 1
- ——-directions = [
- ———–(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
- ——-# Helper function to find the neighbors of a given cell.
- ——-def get_neighbours(row, col):
- ———–for row_difference, col_difference in directions:
- —————new_row = row + row_difference
- —————new_col = col + col_difference
- —————if not(0 <= new_row <= max_row and 0 <= new_col <= max_col):
- ——————-continue
- —————if grid[new_row][new_col] != 0:
- ——————-continue
- —————yield (new_row, new_col)
- ——-# Check that the first and last cells are open.
- ——-if grid[0][0] != 0 or grid[max_row][max_col] != 0:
- ———–return -1
- ——-# Set up the BFS.
- ——-queue = deque([(0, 0)])
- ——-visited = {(0, 0)}
- ——-current_distance = 1
- ——-# Do the BFS.
- ——-while queue:
- ———–# Process all nodes at current_distance from the top-left cell.
- ———–nodes_of_current_distance = len(queue)
- ———–for _ in range(nodes_of_current_distance):
- —————row, col = queue.popleft()
- —————if (row, col) == (max_row, max_col):
- ——————-return current_distance
- —————for neighbour in get_neighbours(row, col):
- ——————-if neighbour in visited:
- ———————–continue
- ——————-visited.add(neighbour)
- ——————-queue.append(neighbour)
- ———–# We’ll now be processing all nodes at current_distance + 1
- ———–current_distance += 1
- ——-# There was no path.
- ——-return -1
Rotting oranges
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
!!! You can keep track of ones and during bfs, if you have seen all the ones you saw in the initial loop, return answer. Start answer off at 0, increment it 1 each while loop. If this condition is never met, return -1 bc you will not find it.
time: O(N) where N is the size of the matrix
space: O(N) because the queue could take up N space if they are all 2s. In normal cases with lots of 2s, we’d have n/2 but still n.
from collections import deque class Solution: ----def modify_input(self, grid): --------answer = 0 --------y = len(grid) --------x = len(grid[0]) --------ones = 0 --------queue = deque() --------directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] -------- --------for row in range(y): ------------for col in range(x): ----------------if grid[row][col] == 1: --------------------ones += 1 ----------------elif grid[row][col] == 2: --------------------queue.append((row, col))---- -------- --------if ones == 0: ------------return 0 -------- --------while queue: ------------size = len(queue) ------------answer += 1 ------------for _ in range(size): ----------------cr, cc = queue.popleft() ----------------for dr, dc in directions: --------------------nr = cr + dr --------------------nc = cc + dc --------------------if not (y - 1 >= nr >= 0 and x - 1 >= nc >= 0): ------------------------continue --------------------if grid[nr][nc] == 1: ------------------------grid[nr][nc] = 2 ------------------------queue.append((nr, nc)) ------------------------ones -= 1 ------------------------if ones == 0: ----------------------------return answer --------return -1
- BFS! shortest time frame can be related to shortest distance, also all tomatoes rot at the same time so DFS does not make sense
- loop through grid to find all 2’s / 1’s, add 2’s to queue and 1’s to 1’s map
- get a 4-way direction list
- while the queue exists, loop through the starting length of queue, at each value check 4-way directions and if that value is in the 1’s map add it to the queue and remove it from the 1’s map
- the starting answer = -1 because the last value will add time to the answer even though there are no more fresh oranges, or at the end of the queue check if items have been added. If not items have been added, then the queue is done and do not add to the answer
time: O(N) where N is the size of the matrix
space: O(N) because the queue could take up N space if they are all 2s. In normal cases with lots of 2s, we’d have n/2 but still n.
class Solution:
- —def orangesRotting(self, grid):
- ——-#make answer -1 or at each queue, while-loop check if the queue is exhausted before adding to it
- ——-answer = -1
- ——-# This lets us not modify the initial input, if we are allowed to, we can forgo this method and just edit the grid
- ——-# to have a rotten value instead of a 1
- ——-ones_map = set()
- ——-y = len(grid)
- ——-x = len(grid[0])
- ——-queue = []
- ——-directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
- ——-for row in range(y):
- ———–for col in range(x):
- —————if grid[row][col] == 1:
- ——————-ones_map.add((row, col))
- —————elif grid[row][col] == 2:
- ——————-queue.append((row, col))
- ——-if len(ones_map) == 0:
- ———–return 0
- ——-while queue:
- ———–size = len(queue)
- ———–for _ in range(size):
- —————cr, cc = queue.pop(0)
- —————for dr, dc in directions:
- ——————-nr = cr + dr
- ——————-nc = cc + dc
- ——————-if not (y - 1 [greater than]= nr [greater than]= 0 and x - 1 [greater than]= nc [greater than]= 0):
- ——————-if (nr, nc) in ones_map:
- ———————–queue.append((nr, nc))
- ———————–ones_map.remove((nr, nc))
- ———–answer += 1
- ——-return answer if len(ones_map) == 0 else -1
Min Cost to Connect All Points
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
- see “distance” and “weights” when looking at connecting points, check out kruskal’s/prims algos
- calculate the manhattan distance, store values in an array
- we can create a class that has a custom __lt__ to compare 2 classes at the weight value, or we can make the array’s 0 index = the weight so the standard comparison works the way we want
- heapfiy the array
- while heap exists, heappop, union, if the roots are different perform actions, else pass and go on
time: O(E log E) where E is the number of edges (points ^ 2). In the heap section, we loop through the heap and heappop at each section, adding the logE time
space: O(E) where E is the edges, n^2 in respect to points
import heapq
class Solution:
—-def minCostConnectPoints(self, points):
——–manhattan = lambda p1, p2: abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
——–n = current = len(points)
——–response = 0
——–weighted_list = []
——–for i in range(n):
————for j in range(i+1, n):
—————-weight = manhattan(points[i], points[j])
—————-weighted_list.append([weight, i, j])
—————-
——–# sorted_weights = sorted(weighted_list, key = lambda x: x[2])
——–heapq.heapify(weighted_list)
——–disjointed_graph = DisjointedGraph(n)
——–
——–while weighted_list:
————w, i, j = heapq.heappop(weighted_list)
————if disjointed_graph.union(i, j):
—————-response += w
—————-current -= 1
————if current == 1:
—————-break
——–return response
——–
class DisjointedGraph:
- —def __init__(self, size):
- ——-self.root = [i for i in range(size)]
- ——-self.rank = [1] * size
- —def find(self, x):
- ——-if self.root[x] != x:
- ———–self.root[x] = self.find(self.root[x])
- ———–return self.root[x]
- ——-return x
- —def union(self, x, y):
- ——-rootX = self.find(x)
- ——-rootY = self.find(y)
- ——-if rootX != rootY:
- ———–if self.rank[rootX] [greater than] self.rank[rootY]:
- —————self.root[rootY] = rootX
- ———–elif self.rank[rootY] [greater than] self.rank[rootX]:
- —————self.root[rootX] = rootY
- ———–else:
- —————self.rank[rootX] += 1
- —————self.root[rootY] = rootX
- ———–return True
- ——-return False
Complexity analysis to traverse all paths in an undirected graph, a directed graph? In a directed graph?
undirected is (V-1)! time and V^3 space. This is bc to each vertex can have edges to all other graphs, meaning traversing it would be v-1 * v-2, * v-3…. and the space would mean the stack could have v^2 items on the stack, plus the number of paths per vertex, so v^3 (since each vertex on the graph has V paths to all other nodes)
directed is 2^n * n. Adding a node to a directed graph increases the possible edges by 2, so 2^n. Space is 2^n as well bc we need to store those in the stack.
Network delay time
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
No good brute force, just different implementations of Dijkstra’s
- heaps/priority queues are excellent for this task, they keep the lowest distance path in the front, ready for us to heappop(heap) it off!
- we need a graph of roots and their edges, make it
- we need a distance map, once the distance map is filled with all the nodes, we stop
- check if the len(distance) == n, since n is 1-indexed, we check direclty against n, not like the usual n - 1
time: O(E * log(E)) where E is the number of edges, hence the length of the time array. This is because we loop through edges to make the graph, then we go through them again in the heap using heappop
space: O (E + V), the queue can have E length, and the map has V + E length where V are the vertexes (N in this case too)
- —def dijkstra_heap(self, times, n, k):
- ——-graph = defaultdict(list)
- ——-for root, target, weight in times:
- ———–graph[root].append((target, weight))
- ——-heap = [(0, k)]
- ——-distances = {}
- ——-while heap:
- ———–dist, node = heapq.heappop(heap)
- ———–if node in distances: continue
- ———–distances[node] = dist
- ———–for target, weight in graph[node]:
- —————if target not in distances:
- ——————-heapq.heappush(heap, (dist + weight, target))
- ——-return max(distances.values()) if len(distances) == n else -1
time: O(V * E), every V could see every E in the worst case since we do not have any seen matrix
space: O(E + V), same reason as above, we can store all the edges in the list at once and the map is E + V
- —def ShorestPathFindingAlgo(self, times, n, k):
- ——-graph = defaultdict(list)
- ——-for root, target, weight in times:
- ———–graph[root].append((target, weight))
- ——-distance_map = {}
- ——-for i in range(1, n+1):
- ———–distance_map[i] = [float(‘inf’), None]
- ——-distance_map[k][0] = 0
- ——-distance_map[k][1] = None
- ——-queue = deque([k])
- ——-while queue:—-
- ———–current = queue.popleft()
- ———–for target, weight in graph[current]:
- —————parent_distance = distance_map[current][0]
- —————edge = distance_map[target]
- —————new_distance = parent_distance + weight
- —————if new_distance [less than] edge[0]:
- ——————-edge[1] = current
- ——————-edge[0] = new_distance
- ——————-queue.append(target)
- ——-total_distance = max(distance_map.values(), key=lambda x: x[0])
——–return total_distance[0] if total_distance[0] != float(‘inf’) else -1
Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
2 solutions, dijkstras or bellman-ford
- use basic bellman-ford optimized algorithm
- remember to swap prev with current each time, then use prev for the result bc the last loop involves swapping current with prev
- the K + 1 is tricky and hard to visualize. the destination doesn’t count as a stop, knowing that we have k + 1 iterations to perform
time: O( K * E ), we do K+1 iterations bc with K stops and each stop we iterate over each flight
space: O(V) for the vertexes occupied by the bellman-ford prev/current lists
from collections import defaultdict
import heapq
class Solution:
—-def bellman_ford(self, n, flights, src, dst, k):
——–prev = [float(‘inf’) for _ in range(n)]
——–current = [float(‘inf’) for _ in range(n)]
——–
——–prev[src], current[src] = 0, 0
——–
——–for _ in range(k+1):
————for e in flights:
—————-root, to, price = e
—————-current[to] = min(prev[root] + price, current[to])
————prev, current = current, prev
———-# prev = current.copy()
——–
——–return -1 if prev[dst] == float(‘inf’) else prev[dst]
- create a adjacency matrix for each vertexes edges
- dijkstras typically does not use stops or pre-populated distances list, but this one it is a lot easier to do so. Create 2 lists, stops/distances and make then infinity for N length.
- remember the distances/stops from the src are 0, make it so!
- put a tuple on the heap, (cost, stops, current), this will allow the heap to be a min-heap with respect to the first argument, cost!
- if we arrived at dest, return the cost, if we are at k+1 stops, continue, otherwise do dijkstra things
time: O( E log E ) where E is the lenght of edges. LC says V^2 log V, but other dijkstras implementations always say E log E, and that makes sense bc the heap can be as large as E when we heappush onto it
space: O (E + V), where E is the number of flights and V are the vertexes
- —def dijkstras(self, n, flights, src, dst, k):
- ——-matrix = [[0 for _ in range(n)] for _ in range(n)]
- ——-for x, y, z in flights:
- ———–matrix[x][y] = z
- ——-distances = [float(‘inf’) for _ in range(n)]
- ——-stops_list = [float(‘inf’) for _ in range(n)]
- ——-distances[src], stops_list[src] = 0, 0
- ——-heap = [(0, 0, src)]
- ——-while heap:
- ———–cost, stops, current = heapq.heappop(heap)
- ———–if current == dst:
- —————return cost
- ———–if stops == k + 1:
- —————continue
- ———–for neighbor in range(n):
- —————if matrix[current][neighbor] > 0:
- ——————-dU, dV, wUV = cost, distances[neighbor], matrix[current][neighbor]
- ——————-if dU + wUV < dV:
- ———————–distances[neighbor] = dU + wUV
- ———————–heapq.heappush(heap, (dU + wUV, stops + 1, neighbor))
- ——————-elif stops < stops_list[neighbor]:
- ———————–heapq.heappush(heap, (dU + wUV, stops + 1, neighbor))
- ——————-stops_list[neighbor] = stops
- ——-return -1 if distances[dst] == float(‘inf’) else distances[dst]
Path With Minimum Effort
You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
path finding, we need to think of dijkstras, bellman-ford, BFS and DFS
- looking for “min” value at each step, seems like a perfect idea for dijkstras!
- create a heap with the effort, value, row, col
- each iteration check if we have seen it, loop through the valid deltas, carry the max effort forward and onto the heap
- base case is when row and col = y and x, bc of min-heap, that will be the smallest value
time: O(rowcol * log(rowcol)), we loop through all the rows and columns, all the rows and columns can be on the list when we heappush
space: O(row * col ), this is for the seen matrix and the heap
import heapq
class Solution:
—-def dijkstra(self, heights):
——–seen = set()
——–y, x = len(heights) - 1, len(heights[0]) - 1
——–# effort, val, row, col
——–heap = [(0, heights[0][0], 0, 0)]
——–deltas = [(0, 1), (0, -1), (1, 0), (-1, 0)]
——–while heap:
————effort, val, row, col = heapq.heappop(heap)
————if row == y and col == x:
—————-return effort
————
————if (row, col) not in seen:
—————-seen.add((row, col))
————else:
—————-continue
—————-
————for dr, dc in deltas:
—————-new_row = row + dr
—————-new_col = col + dc
—————-if y >= new_row >= 0 and x >= new_col >= 0:
——————–height = heights[new_row][new_col]
——————–new_effort = max(effort, abs(val - height))
——————–heapq.heappush(heap, (new_effort, height, new_row, new_col))
- see that each row/col is a node in a disjointed graph
- create the edge list, we need to loop through matrix and calc the difference and flatten the row/col cordinates so we can do union/find operations using disjointed graphs
- with a 3x4 (row x col), to get a flattened index we do current_row * len(col) + current_col, at 1x2 (0-index) that gives us 4+2 =6, and if you follow that through on a matrix that is the 6th position 0th index on the matrix!
- sort the edge list so we get the smallest ones first
- perform unions on all the row/col pairs in the edge list, afterwards check if we found a path between 0 and row-1/col-1, if we have return the distance bc that will be the smallest
time: O(MN * log(MN)), we need to loop through the matrix and then sort it. If we do a heap the heappush will add the log time as well
space: O(M*N), the length of the new objects we create
- —def unionFind(self, heights):
- ——-row = len(heights)
- ——-col = len(heights[0])
- ——-if row == 1 and col == 1:
- ———–return 0
- ——-edge_list = []
- ——-deltas = [(0, 1), (0, -1), (1, 0), (-1, 0)]
- ——-seen = set()
- ——-for cr in range(row):
- ———–for cc in range(col):
- —————seen.add((cr, cc))
- —————for dr, dc in deltas:
- ——————-nr = cr + dr
- ——————-nc = cc + dc
- ——————-if (nr, nc) not in seen:
- ———————–if row - 1 >= nr >= 0 and col - 1 >= nc >= 0:
- —————————difference = abs(heights[cr][cc] - heights[nr][nc])
- —————————# flatten a matrix cordinates into a linear version of itself!
- —————————edge_list.append((difference, nr * col + nc, cr * col + cc))—————-
- ——-edge_list = sorted(edge_list, key = lambda x: x[0])
- ——-union_find = UnionFind(row*col)
- ——-for difference, x, y in edge_list:
- ———–union_find.union(x, y)
- ———–if union_find.find(0) == union_find.find(row*col-1):
- —————return difference
- ——-return -1
course scheduler 2
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Anytime you hear other things must be completed to continue, think topological sort!
- standard topological sort, we need to build an adjacency list and an indegree hashmap
- everytime we see a course, we increment the indegree value. the adjacency list’s key is the prereq and each item in the list is items that have this vertex as it’s prereq
- create a deque with everything that isn’t in the inedegree (they have no prereqs)
- each time you pop something, add it to the list, when an item is found during the loop decrement the indegree, if it is 0 add it to the queue
- this handles cycles bc cyles will cause the indegree to always be 1
time: O(V + E) where V are the vertexes and E are the edges
space: O(V + E) since we need the adjacency list
from collections import defaultdict, deque
class Solution:
—-def proper_topological(self, numCourses, prerequisites):
——–adj = defaultdict(list)
——–response = []
——–indegree = {}
——–for course, prereq in prerequisites:
————adj[prereq].append(course)
————indegree[course] = indegree.get(course, 0) + 1
——–
——–queue = deque([n for n in range(numCourses) if n not in indegree])
——–
——–while queue:
————current = queue.popleft()
————response.append(current)
————for child in adj[current]:
—————-indegree[child] -= 1
—————-if indegree[child] == 0:
——————–queue.append(child)
—————-
——–return response if len(response) == numCourses else []
- —def custom_topical(self, numCourses, prerequisites):
- ——-self.adj = defaultdict(list)
- ——-self.seen = set()
- ——-self.seen_recent = set()
- ——-self.response = []
- ——-for course, prereq in prerequisites:
- ———–self.adj[course].append(prereq)
- ——-for i in range(numCourses):
- ———–if i not in self.seen:
- —————if self.dfs(i):
- ——————-return []
- ——-return self.response
- —def dfs(self, index):
- ——-self.seen.add(index)
- ——-self.seen_recent.add(index)
- ——-for child in self.adj[index]:
- ———–if child not in self.seen and self.dfs(child):
- —————return True
- ———–elif child in self.seen_recent:
- —————return True
- ——-self.seen_recent.remove(index)
- ——-self.response.append(index)
- ——-return False
- alien dictionary
There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings words from the alien language’s dictionary, where the strings in words are sorted lexicographically by the rules of this new language.
Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return “”. If there are multiple solutions, return any of them.
A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.
- remember that “ABC” and ABZ” if we don’t know the ordering, we do not know if C comes before Z or vise versa. The ordering in the initial list of words is the only way we can start determining any order.
- we need a list of possible words with their indegree, so we make it using a double for loop
- loop through the words, as soon as a character isn’t equal, perform a standard topological sort operation, break the loop (bc we can’t make assumptions on anything past the first letters that are not equal
- apparently if the second word is a subword it causes a cycle (I think), not sure how you’d figure that out in an interview
- all items that have 0 indegrees go into queue, perform standard topological sort
time: O(W) where W is the length of the words in the initial word list. Each word can only give us 1 edge each, so if N is the total words, we can get N-1 edges. Also, if there are U unique characters, we can get U^2 edges assuming the input gives words like “AAA, AAB, AAC….” so each character has U edges, so that is U^2. BUT in both those cases, W is larger bc W > N as long as N has more than 1 character, and there are only U characters so W > U. comparing N to U, we know that if there are N = 100000, U=26, then we only have 26^2 edges, conversely, if we only have N=10, U=26, we only have 9 edges, so it is the min(N, U^2)
space: O(min(U^2, N). This is the same reason as the time complexity reasoning for U and N
from collections import defaultdict, deque
class Solution:
—-def alienOrder(self, words):
——–graph = defaultdict(set)
——–indegree = {}
——–for word in words:
————for s in word:
—————-indegree[s] = 0
——–# indegree = Counter({s:0 for word in words for s in word})
—————-
——–response = []
——–for first_word, second_word in zip(words, words[1:]):
————for x, y in zip(first_word, second_word):
—————-if x != y:
——————–if y not in graph[x]:
————————graph[x].add(y)
————————indegree[y] = indegree.get(y, 0) + 1
——————–break
————else:
# this test case makes the problem statement invalid, it fails on [‘abc’, ‘ab’], but ab < abc, so it should be the reverse if the problem statement was correct.
—————-if len(second_word) < len(first_word):
——————–return “”
——————–
————
——–queue = deque([s for s in indegree.keys() if indegree[s] == 0])
——–while queue:
————current = queue.popleft()
————for child in graph[current]:
—————-indegree[child] -= 1
—————-if indegree[child] == 0:
——————–queue.append(child)
————response.append(current)
——–
——–return ““.join(response) if len(response) == len(indegree.keys()) else “”
Minimum height trees
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
Return a list of all MHTs’ root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
brute force is create the adjacency graph, then for range(n) make a heap with root as the starting node in the heap, perform BFS, get the min height! O(V(V+E)) bc we loop through each V and E, V times where V is N, space is V+E
- you have to know that there are at most 2 centroid nodes, centroid nodes will give us the min-height bc they have the most edges spanning from them
- create standard adj_list with backwards edges except the dictionary has sets (we need to remove items from the set later!)
- add all leaf nodes, nodes that only have 1 edge, meaning 0 indegree to the queue
- instead of while queue, then for loop for size, do while nodes > 2, meaning once we have 2 nodes left we have reached the centroids, then do for loop for size
time: O(V + E) since we have a valid tree, V = n and E = n - 1. we create the adj_list and iterate over n-2 nodes
space: O(V+E) for the adj_list and the queue
from collections import defaultdict, deque class Solution: ----def findMinHeightTrees(self, n, edges): --------if n == 1: ------------return [0] --------graph = defaultdict(set) --------for x, y, in edges: ------------graph[x].add(y) ------------graph[y].add(x) -------- --------leaves = deque() --------for i in range(n): ------------if len(graph[i]) == 1: ----------------leaves.append(i) ---------------- --------nodes = n --------while nodes > 2: ------------size = len(leaves) ------------for i in range(size): ----------------nodes -= 1 ----------------current = leaves.popleft() ----------------child = graph[current].pop() ----------------graph[child].remove(current) ----------------if len(graph[child]) == 1: --------------------leaves.append(child) --------return leaves
- —# V(V+E), where V = n and edges = n-1 (valid trees have n-1 edges)
- —def custom(self, n, edges):
- ——-if n == 1:
- ———–return [0]
- ——-graph = defaultdict(list)
- ——-for x, y, in edges:
- ———–graph[x].append(y)
- ———–graph[y].append(x)
- ——-global_min = float(‘inf’)
- ——-min_dict = defaultdict(list)
- ——-for root in range(n):
- ———–count = 0
- ———–queue = deque([root])
- ———–recent_seen = defaultdict(lambda: False)
- ———–while queue:
- —————size = len(queue)
- —————for _ in range(size):
- ——————-current = queue.popleft()
- ——————-recent_seen[current] = True
- ——————-for child in graph[current]:
- ———————–if not recent_seen[child]:
- —————————queue.append(child)
- —————if len(queue) > 0:
- ——————-count += 1
- ———–min_dict[count].append(root)
- ———–global_min = min(global_min, count)
- ——-return min_dict[global_min]
-
Daily10
-
Design patterns and anit-patterns2
-
Systems Design50
-
Leetcode: Basic Algorithms32
-
Leetcode: Heaps2
-
Leetcode: Dynamic Programming9
-
Leetcode: Trees19
-
Leetcode: Linked Lists20
-
Leetcode: Strings18
-
Leetcode: Binary and Number Manipulation12
-
Leetcode: Matrix9
-
Leetcode: Graphs27
-
Leetcode: Arrays49
-
Databases9
-
Leetcode: Intervals6
-
Behavioral0
-
Linux28
-
Git2
-
Python2
-
Java/k8/Docker/Python4
-
UML Diagrams8
-
csharp3
