Home - ALawliet/algorithms GitHub Wiki
Strings/Arrays
- hashmap of char/index to count
- two pointers (especially if the array is sorted)
- sliding window for continuous/contiguous (often with a hashmap and meet condition/undo condition pattern)
- stack (parens)
- binary search leftmost (first bad version, k closest)
- sort and keep track of current index to remove duplicates
- cyclic sort for missing or duplicates
- binary search rotated sorted arrays
- prefix sum
Recursion/Backtracking
- "generate", "try all possibilities"
- generate parens, subsets, permutations, n queens, sudoku
Trees
- DFS
- BFS
- bottom-up inverted-V if you need to process a lower descendant down to the leaves before its upper ancestor to get the answer (univalue, LCA, ancestor problems)
- boundary walk if you need to track its predecessor (convert to DLL)
- stack iterative inorder, postorder
- hashmap of columns for vertical order
Graphs
- BFS: detect cross edge = cycle detection = bipartite (if cross edge on same level layer)
- BFS shortest distance
- BFS/DFS number of connected components
- topological sort (Kahn's indegree)
Heap
- kth largest
- k closest
- merge k
- also try bucket sort or quickselect (k top frequent)
- smallerHalfMaxHeap and largerHalfMinHeap to find median
- minCostHeap and maxProfitHeap
Intervals
- focus on the first 2 intervals to find the pattern, then loop it
- min/max
- case analysis
- sort by start times
Calculators
- stack to process the expression
- recursion/backtracking to try all possibilities or handle parens () grouped expressions
Subsets/Permutations
- next lexicographical permutation algorithm nayuki
- BFS
Palindromes
- two pointers
- recursion
Random Pick
- reservoir sampling
- prefix sum and search
Math Tricks
- task scheduler
- continuous subarray sum
- count unique binary search trees (nth catalan number)
- sliding window substrings
- DP in 1D array knapsack-like
- DP in 1D array 1 word
- DP in 2D grid paths
- DP in 2D with 2 words
- level-order traversal
- trie: autocomplete
- binary search
- quick select partition
- heap
- subsets/combinations
- permutations
- backtracking
- trees (see below)
- DFS/BFS with back/cross edges
- single bidirectional pass for arrays
- parentheses in a stack
Dynamic Programming
- what are we trying to optimize? a maximum? a minimum? other?
- can we solve the overall problem by solving its smaller subproblems first? is there a recursive pattern?
- what is the solution that each subproblem cell represents?
- what are the choices we can make at each step and how do they affect the answer to the current subproblem and the other choices to create the recurrence relation?
- will this be represented as a 1D array or 2D table?
- which cell is the final overall solution located?
- which cells can we prefill because we already know the solution to that subproblem?
- does it make it any easier if we try iterating backwards instead of forwards?
Backtracking
- when there are many decision points that we need to explore
- template
- choice - what choice do we make at each call of the function? recursion expresses decision
- constraints - when do we stop following a certain path? when do we not even go one way? can we optimize by bailing early?
- goal (base case) - what is our target? what are we trying to find?
each recursive call creates a new branch
driver(decisions):
helper(decisions, empty-partial-solution)
helper(decisions, partial-solution):
if (no more decisions and goal is reached): # base case
print/collect partial-solution
elif (hit constraints e.g. out of bounds, exceeded target amount):
return
else:
for (each possible choices):
make a choice # add to partial-solution
helper(remaining-decisions, partial-solution)
unmake choice # if mutable data structure is used
- if just 2 choices exclude/include then usually call those separately without for loop
- to skip duplicates some solutions will pass in a start index in for loop
Trees
- Tree Traversal
- BFS
- DFS (preorder, inorder, postorder)
- top-down, bottom-up (inverted-V), boundary walk, iterative stack-based
- Tree Construction
- top-down, left-to-right
# Edge case
if root is None: return
def dfs(non-null node, additional info from parent):
# Base case: Leaf node
if node.left is None and node.right is None:
# Leaf level processing -> generate answer in global bag
return
# Recursive case: Internal node
if node.left is not null:
dfs(node.left, additional info)
if node.right is not null:
dfs(node.right, additional info)
def dfs(node):
if not node.left and not node.right:
check local ans
update global ans
return local ans
if node.left:
store left bottomup = dfs(node.left)
check left and local val
if node.right:
store right bottomup = dfs(node.right)
check right and local val
check local ans
update global ans
return local ans
Graphs
Given: A set of n distinct objects
-
Sorting Problem: Sort them
-
Combinatorial Enumeration and Search: Enumerate all possible permutations & combinations (possibly filter out those which satisfy some constraints)
-
Searching Problem: Search for a given item in the collection.
-
Combinatorial Optimization: Find the "best" possible permutation/combination (DP, Greedy, Branch-n-Bound)
-
Given a set of n distinct objects (vertices) and m pairwise relationships (edges).
-
Topological Sort
-
Basic Graph Theory Graph representations General graph traversal
- BFS
- Shortest paths
- DFS
- Topological Sort
- or Kahn's Indegree
- Strongly Connected Components
- or Union-Find
- Topological Sort
- Both
- Traversals of undirected and directed graphs
- Finding connected components
- Detecting cycles
- BFS: is there a cross edge?
- DFS: is there a back edge?
- Bipartite
- Dijkstra
- Bellman-Ford
- Floyd-Warshall
- Prim
- Kruskal
- Best-first
- A*
- BFS
-
DAG -> Topological Sort
-
Critical Connections -> DFS: determine if tree edge connecting node to parent is critical or not