Solving Matrix/Graph Problems on LeetCode using Python
787. Cheapest Flights Within K Stops
There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.
Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph looks like this:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.1. Steps to Solve Problems
Matrix can be expanded to a graph related problem. The steps are:
(1) building a graph where the index are the node number, and the graph[i] would be a list of elements (could be other_node or a tuple or a list (other_node, weight)).
(2) Second step is to decompose the problem into subproblems.
(3) where each subproblem could be resolved by Dynamic Programming (BFS or DFS). Note: There might need some minor changes to adopt the standard algorithms.
(4) After this, we need to further thinking about how to improve the efficiency (time and space). Normally, the condition that might lead near ending of the graph algorithm.
(5) Explain the difference of the time complexity and the space complexity to the interviewers
According to this order, the above example is resolved with the following python code:
import sys
class Solution(object):
def findCheapestPrice(self, n, flights, src, dst, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int
:rtype: int
"""
#(1). Construct Graph
#one dimension with elements to be list
graph = [[] for _ in xrange(n)]
for s,e,w in flights:
graph[s].append((e,w))
#(2) Graph Algorithm
q= [(src,0)] #stop and price
count = 0
min_price= sys.maxint #record the minimum price so far
while q:
next_stops = []
for cur, acc_price in q: #same level
for end,price in graph[cur]:
#conditional satisfied, save the price
if end==dst:
min_price = min(min_price, acc_price+price)
#(4) Cut down the complexity
#Instead of directly add the next stop, we only add those stops that have less accumulated price
if min_price>acc_price+price:
next_stops.append((end,acc_price+price) )
#(4) Instead of directly add the next stop, we only add those stops that have
if count==K:
if min_price<sys.maxint:
return min_price
else:
return -1
q=next_stops[:]
count+=1
# this is important too
if count<=K:
if min_price<sys.maxint:
return min_price
else:
return -1Another example focusing about python code: 399. Evaluate Division
2. Graph Algorithms
(a) Represent Graph
Adjacency list: [[1,2,3],[3,1],[4,6,1]], node 0 connects to 1,2,3, node 1 connect to 3,1, node 2 connects to 4,6,1
graph = [[] for _ in xrange(nodes)]Adjacency matrices:
graph = [[0 for _ in xrange(cols)] for _ in xrange(rows)] #normally, rows=colsIf you need a “name” for each node, and before the graph is complete, you do not know how many nodes you might get, use dictionary, for example, we are given a list of edges[[“a”,”c”],[b,c],[b,e]….]
from collections import defaultdict
d = defaultdict(set) # structure initialization
# add an edge (remember to add to both vertices!) for ver1, ver2 in edges:
d[ver1].add(ver2)graph = { "a" : ["c"],
"b" : ["c", "e"],
"c" : ["a", "b", "d", "e"],
"d" : ["c"],
"e" : ["c", "b"],
"f" : []
}
If we need weights for each edge, use dictionary from the default dictionary to represent:
graph= collections.defaultdict(dict)
for (num, den), val in zip(equations, values):
graph[num][num] = graph[den][den] = 1.0
graph[num][den] = val
graph[den][num] = 1 / val
#defaultdict(<type 'dict'>, {u'a': {u'a': 1.0, u'b': 2.0}, u'c': {u'c': 1.0, u'b': 0.3333333333333333}, u'b': {u'a': 0.5, u'c': 3.0, u'b': 1.0}})Function to generate the list of all edges:
def generate_edges(graph):
edges = []
for node in graph:
for neighbour in graph[node]:
edges.append((node, neighbour)) return edgesprint(generate_edges(graph))
(b) Breadth-First-Search (BFS)
#implement using a queue
def BFS(root):
q = [root]
root.visited = 1
while q:
n=q.pop()
visit(n) #finish visit
for node in n.adjacent:
if not node.visited:
node.visited = 1 #start to visit
q.insert(0,node)# a mutant for trees to visit it level by level
def BFS(root):
q = [root]
root.visited = 1
level = 0
while q:
n=q.pop()
visit(n) #finish visit
for node in n.adjacent:
if not node.visited:
node.visited = 1 #start to visit
q.insert(0,node)
Or we use the library Queue:
Example of how to wait for enqueued tasks to be completed:
def worker():
while True:
item = q.get()
do_work(item)
q.task_done()q = Queue()
for i in range(num_worker_threads):
t = Thread(target=worker)
t.daemon = True
t.start()for item in source():
q.put(item)q.join()
© Depth-First-Search (DFS)
#Recursive
def DFS(root):
#END Condition
if not root:
return
visit(root)
for node in root.adjacent:
if not node.visited:
DFS(node)#Iterative, implemented using a stack
def DFS_iter():
root.visited = 1
stack = []
stack.append(root)
while stack:
n=stack.pop()
visit(n)
n.visited=1
for node in n.adjacent:
if not node.visited:
stack.append(node)
Topological Sort:
Topological Sorting vs Depth First Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting
In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.
# The function to do Topological Sort. It uses recursive
# topologicalSortUtil()
def topologicalSort(self):
# Mark all the vertices as not visited
visited = [False]*self.V
stack =[]# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in n(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Print contents of stack
print stack# A recursive function used by topologicalSort
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
In some cases, we need to detect cycles:
# -1:being visiting, 0: not visited, 1: done visiting
def DFS_cycle_detect(self,v,visited,stack):
if visited[v]==-1: #visiting again
return False
elif visited[v]==1: #repeated visiting
return True
visited[v] = -1 #being visiting
for i in self.graph[v]:
if visited[i] == 0: #not visited
if not self.DFS_cycle_detect(i,visited,stack):
return False
stack.insert(0,v)
visited[v]=1 #done visiting
return True3. Examples
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
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 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].Solution: first to convert it into a graph, this is a path search, then do a DFS to find solution for this. Time complexity is O(k*(V+E)), k is the total number of queries, space complexity is O(V+E).
class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
quot = collections.defaultdict(dict)
for (num, den), val in zip(equations, values):
quot[num][num] = quot[den][den] = 1.0
quot[num][den] = val
quot[den][num] = 1 / val
def DFS_iter(src, end):
stack = [(src,1.0)] #source and value
visited =set([src]) #*** set needs [src] to initialize
while stack:
cur, val = stack.pop()
if cur == end:
return val
visited.add(node) for node, w in quot[cur].items():
if not node in visited:
stack.append((node, val*w))
return -1.0res = []
for num, den in queries:
if num not in quot:
res.append(-1.0)
else:
res.append(DFS_iter(num,den))
return res
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]You should return [1,2,3,6,9,8,7,4,5].
class Solution(object):
def spiralOrder(self, matrix):
def spiral_coords(r1, c1, r2, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2 - 1, c1, -1):
yield r2, c
for r in range(r2, r1, -1):
yield r, c1if not matrix: return []
ans = []
r1, r2 = 0, len(matrix) - 1
c1, c2 = 0, len(matrix[0]) - 1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_coords(r1, c1, r2, c2):
ans.append(matrix[r][c])
r1 += 1; r2 -= 1
c1 += 1; c2 -= 1
return ans
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
Solution: This is a cycle detect algorithm, also used topological sort, if we need to get the result.
def canFinish(self, numCourses, prerequisites):
graph = [[] for _ in xrange(numCourses)]
visit = [0 for _ in xrange(numCourses)]
for x, y in prerequisites:
graph[x].append(y)
def dfs(i,stack):
if visit[i] == -1:
return False
if visit[i] == 1:
return True
visit[i] = -1
for j in graph[i]:
if not dfs(j,stack):
return False
visit[i] = 1
stack.append(i) return True
for i in xrange(numCourses):
if not dfs(i, stack): #stack is optional, to get the result
return False
return True
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
- 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"]. - All airports are represented by three capital letters (IATA code).
- You may assume all tickets form at least one valid itinerary.
Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
Solution: for this one, we use DFS with backtracking. We add the current in the route, we remove the element from the adjacency list, if we found an itinerary that used all of the tickets, then we return True. If the recursive call failed, we recover the route and the ticket to try the next possible step.
from collections import defaultdict
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
d = defaultdict(list)
for flight in tickets:
d[flight[0]] += flight[1],
self.route = ["JFK"]
def dfs(start = 'JFK'):
if len(self.route) == len(tickets) + 1:
return self.route
myDsts = sorted(d[start])
for dst in myDsts:
d[start].remove(dst) #dst is used, wont be used next time
self.route.append(dst), #add an element
worked = dfs(dst) #keep searching
if worked:
return worked
#if not worked, recover the rount
self.route.pop()
d[start] += dst,
return dfs()Difference between BFS and DFS
Here you will learn about difference between BFS and DFS algorithm or BFS vs. DFS.
Breadth First Search (BFS) and Depth First Search (DFS) are two popular algorithms to search an element in Graph or to find whether a node can be reachable from root node in Graph or not. And these are popular traversing methods also.
When we apply these algorithms on a Graph, we can see following types of nodes.
- Non-Visited nodes(): These nodes not yet visited.
- Visited nodes(being visiting and its adjacent): These nodes are visited.
- Explored nodes (done visited): A node is said to be explored when it was visited and all nodes which are connected (adjacent) to that node also visited.
Difference between BFS and DFS
S. No. Breadth First Search (BFS) Depth First Search (DFS)
- BFS visit nodes level by level in Graph. DFS visit nodes of graph depth wise. It visits nodes until reach a leaf or a node which doesn’t have non-visited nodes.
- A node is fully explored before any other can begin. Exploration of a node is suspended as soon as another unexplored is found.
- Uses Queue data structure to store Un-explored nodes. Uses Stack data structure to store Un-explored nodes.
- BFS is slower and require more memory. DFS is faster and require less memory.
- Some Applications:
- Finding all connected components in a graph.
- Finding the shortest path between two nodes.
- Finding all nodes within one connected component.
- Testing a graph for bipartiteness.
Need to cover more graph related algorithms
Solved with graph algorithms: DPS
