After solved 1000 medium leetcode found these patterns — UnionFind, Devide And Conquer, Toposort
Here is another Leetcode Patterns , continuing summary leetcode problem patterns, all extracted from medium level problem.
these are previous posts if you have not read yet :DFS , BFS, DP, Backtracking, Mono-stack ,Pre-sum, greedy , Sliding window .
Lets start .
Devide and conquer
The core idea is split the problem into sub problems and keep merging the sub-answers into final answer . do not confuse with DP , they are very different. D and C split the problem into half-half, then 1/4 and 1/8, etc, and “merge” the 1/4 answers into “half” answer, then merge the half-half into final answer. in short, it is split input into half , recursive and merge . it is a very powerful idea .
DP is to solve the smaller input problem and cache them, then reuse the result for bigger input problem solving .in short, it is using array to cache result and reuse .
Core Idea
def solve(input):
if break_condition:
return
// do something with input[index]
solve(input[:index])
solve(input[index+1:])Sample Problem.
105. Construct Binary Tree from Preorder and Inorder Traversal
Thought process . since we got the preorder (current>left>right) and inorder (left>current>right) array . so preorder[0] is the root, now check its index in inorder array, keep it as index. so, inorder[:index] is left sub tree, inorder[index+1:] is right sub tree. and we could also split the preorder array based on the position of index (explained details in below comments) . repeat the same until get the results . so , it is a devide and conquer problem .
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
"""
first element in preorder is the root
the find the root's index in inorder. [left], [right] will be the sub trees
Sample :
[3 9 20 15 7] [9 3 15 20 7]
3
/ \
[9] [9] [20 15 7] [15 20 7]
/ 20
9 / \
[15] [7]
/ \
15 7
"""
def build(p, i):
if not p:
return None
r = TreeNode(val=p.pop(0))
idx = i.index(r.val)
r.left = build(p[:idx], i[:idx+1])
r.right = build(p[idx:], i[idx+1:])
return r
return build(preorder, inorder)106. Construct Binary Tree from Inorder and Postorder Traversal
this is very much similar thinking to 105 : find the index of postorder[-1] in inorder, base on the index split the array and recursively merge and get the result .
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
"""
Similar to #105 (construct from inoder and preorder)
in postorder , last element is the root
find the index in inoder ,[left] and [right] is sub tree. repeat the same
[9 3 15 20 7] [9 15 7 20 3]
3
/ \
[9] [9] [15 20 7] [15 7 20]
/ \
9 20
/ \
[15] [7]
"""
def build(p, i):
if not p :
return None
root = TreeNode(p.pop())
idx = i.index(root.val)
root.left = build(p[:idx], i[:idx])
root.right = build(p[idx:], i[idx+1:])
return root
return build(postorder, inorder)95. Unique Binary Search Trees II
Thought process . the D and C thinking is to try use every element as root, then combine its left and right sub-tree possibilities.
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def gen(left, right):
nonlocal n
if left > right :
return [None]
trees=[]
for i in range(left, right+1):
# use every node as root
l_tree=gen(left, i-1)
r_tree=gen(i+1, right)
# add each combination of left and tree sub tree
for l in l_tree:
for r in r_tree:
root = TreeNode(i)
root.left = l
root.right = r
trees.append(root)
return trees
return gen(1, n)241. Different Ways to Add Parentheses
Thought process. when generate expressions , while we split the inputs into smaller and smaller ,notice that the subproblem model actually equals current problem problem model . so that can “combine” and “merge” the sub-answers to become final answers . this is usually how to identify a D and C problem .
def diffWaysToCompute(self, expression: str) -> List[int]:
"""
Sample1 : 2*3-4 =>
* -
/ \ / \
2 - * 4
/ \ / \
3 4 2 3
let Tree(2*3-4) = result of 2*3-4
Sample2 : 2*3-4*5 =>
* * -
/ \ / \ / \
2 Tree(3-4*5) Tree(2*3-4) 5 * *
/ \ / \
2 3 4 5
"""
def val(left, right, operator):
if operator == '+':
return left+right
elif operator == '-':
return left-right
else:
return left*right
@cache # Cache result
def dwc(exp):
if all(e not in ['+', '-', '*'] for e in exp):
return [int(exp)]
res=[]
for i, e in enumerate(exp): # Loop through expression
if e not in ['+', '-', '*']: # Skip numbers
continue
left = dwc(exp[:i]) # Try put every operator as root node
right = dwc(exp[i+1:])
for l in left:
for r in right:
res.append(val(l, r, e))
return res
return dwc(expression)Please don’t get me wrong. above is definally not the whole idea of devide and conquer, they are just “leetcode D and C problems” .
More similar leetcode problems .
109. Convert Sorted List to Binary Search Tree
395. Longest Substring with At Least K Repeating Characters
889. Construct Binary Tree from Preorder and Postorder Traversal
894. All Possible Full Binary Trees
Union Find
Even there are not a lot problems on leetcode, but this is a very useful algorithm .
Whenever we see a “connectivity” problem, it is union find, it could also compress long branches tree, by linking the leaves to root .
Some connectivity problems could be solved by “count how many of DFS can do” , but they are more clean to be solved by Union Find .
Pattern :
class UF:
def __init__(self, row, col, grid):
self.parent = {}
#initialize parent values
def union(self, n1, n2):
p1, p2 = self.find(n1), self.find(n2)
if p1 != p2:
self.parent[p1] = p2
def find(self, node):
p = self.parent[node]
if p == node:
return node
return self.find(p)We got the union find class . it does 2 simple things , union the ancestor of 2 nodes if they are not same, and find the node ancestor .
Lets see how to use it into some sample problems .
Thought process . problem is clear , count how many islands .without knowing UnionFind , we could solve it by DFS ,once we see ‘1’ , do DFS mark each as 2 , by end of DFS do count +1; do the same see how many DFS we could do .
def numIslands(self, grid: List[List[str]]) -> int:
"""
Idea :
when there is '1', DFS mark the connected '1' as '2'
num of islands = How many times DFS can do
"""
row, col = len(grid), len(grid[0])
def mark(grid, r, c):
if r < 0 or c < 0 or r == row or c == col or grid[r][c] != '1':
return
grid[r][c] = '2'
mark(grid, r-1, c)
mark(grid, r+1, c)
mark(grid, r, c-1)
mark(grid, r, c+1)
res=0
for r in range(0, row):
for c in range(0, col):
if grid[r][c] == '1':
res+=1
mark(grid, r, c)
return resDFS works. but this algorithm is not a “perfect match” with the problem itself , DFS focus is search ,we used it as doing marking and counting . so it’s kind of workaround .
If we think this problem in this way : initialize total island=total number of ‘1’ , when we see ‘1’ (imagine 1 is island) , union all 4 direction islands into same island recursively. whenever we union 1 island, reduce 1 island, so we can get total number of island after we union everything .
class UF:
def __init__(self, row, col, grid):
self.parent = {} # {(row, col): (parent_row, parent_col) }
self.count = 0 # track num of islands
for r in range(row):
for c in range(col):
if grid[r][c] == '1': # only store parent for island
self.parent[(r,c)]=(r,c) # every island parent point to self first
self.count+=1
def union(self, n1, n2): # n1, n2 : (row, col)
p1, p2 = self.find(n1), self.find(n2)
if p1 != p2: # merge 2 parents. it doesn't matter which will be new parent
self.parent[p1] = p2
self.count -= 1
def find(self, node):
p = self.parent[node]
if p == node:
return node
return self.find(p)class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
"""
Idea :
when there is '1' ,check and union the left/right/up/down '1'
"""
row, col = len(grid), len(grid[0])
uf = UF(row, col, grid)
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def valid(r, c, row, col, grid):
if r < 0 or c < 0 or r == row or c == col or grid[r][c] == '0':
return False
return True
for r in range(0, row):
for c in range(0, col):
if grid[r][c] == '1':
for d in dirs:
r1, c1 = r+d[0], c+d[1]
if not valid(r1, c1, row, col, grid):
continue
uf.union((r, c), (r1, c1))
return uf.count
990. Satisfiability of Equality Equations
Thought process. problem looks like a DFS, to check if a==c , so could DFS all a equations and see if there is a=c or something=a and something=c. however if we think about , a=b, b=c, c=d … for this equations chain , the root is ‘a’ . and we coule store parent[a]=a, parent[b]=a … so this equation problem could be converted into : as long as parent[c]=parent[a] then a=c . so it is a union find problem .
class UF:
def __init__(self):
self.parent = {}
def find(self, n):
if n not in self.parent:
return n
return self.find(self.parent[n])
def union(self, r1, r2):
self.parent[r2] = r1class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
equations.sort(key=lambda x:x[1:3], reverse=True)
uf = UF()
for e in equations:
e1,op,e2 = e[0],e[1:3],e[3]
root1 = uf.find(e1)
root2 = uf.find(e2)
if op == '==':
if root1 == root2:
continue
uf.union(root1, root2)
else:
if root1 == root2:
return False
return True
More Union Find problems
547. Number of Provinces (very much similar to number of islands, try the DFS, then use UF)
947. Most Stones Removed with Same Row or Column
959. Regions Cut By Slashes (could be converted into number of islands)
Toposort
When we deal with graph , toposort is important algorithm to remove nodes by such sequence : remove each node if degree = 0 (no input or output node)
Pattern
def solve():
res=[]
g = build_graph() # <node: next_nodes>
while g:
nodes = [k for k in g.keys() if len(g[k]) == 0]
if not nodes:
break
# do something
for n in nodes:
for neighbor in g[n]:
g[neighbor].remove(n) # remove self from neighbor nodes
del g[n]Sample Problem
To finish all courses .need to start with the ones without dependecy, then remove it from its neighbor nodes, continue the same until finished all .
This is the classic problem of toposort : read the nodes in graph structure order by the number of dependencies .
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
pre = prerequisites
dependencies = {i:set() for i in range(0, numCourses)}
for k,v in pre:
dependencies[k].add(v)
while len(dependencies.keys())>0 :
# find the courses has no dependency
no_dependency = [x for x in dependencies.keys() if len(dependencies[x]) == 0]
if not no_dependency :
return False
for c in no_dependency:
# finish each course, remove it from all course dependency list
for k, dep in dependencies.items():
if c in dep:
dep.remove(c)
del dependencies[c]
return TrueMore Topo sort problems
210. Course Schedule II (Almost same as 207, just that need to store the result)
Conclusion
All these 3 Algorithms are just ideas of leetcode problems , however the real power behind them are much deep than what covered above.
Devide And Conquer . this is a very powerful idea . find the pivot (or index), split the input based on pivot and do it recursively , merge the answer. it is also the base of some famous sorting algorithms : quick sort and merge sort, heap .
UnionFind is about connectivity of nodes or group of roots. it is very useful in counting number of “connected nodes” in graph or tree or matrix .
Toposort is a way to traverse the graph by dependency ordering . remove the least dependency node and until finish all the nodes and until get a empty graph .
Thanks for reading . have a nice day , leetcoders !
