Leetcode: Graphs Flashcards
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
