**Pattern Map - ALawliet/algorithms GitHub Wiki
edge cases
- check values or pointers for 0 and n-1 and n
- try to initialize/assume any values that you can for base cases
DP
- min, max, optimize, longest, shortest, subsequence
- if it's 2 strings put them on an xy grid
- giving it extra room +1 row/col helps with out of bounds cases
- 0/1 knapsack, unbounded (unlimited picks) knapsack
- problems where you can intuitively draw a decision tree and have a list of choices where you gotta go through a bunch of choices but there end up being repeated subproblems that can be cached
- come up with the recursive relation first
Backtracking
- if, else, for, recursion format usually
- subsets, combinations
- backtracking is just DFS but where you change state -> call recursion on that path with the changed state -> undo state for the next path to explore, the state can be kept as a variable or object that you change like an array that is mutated and undone or a fresh copy passed into the recursive call
- sometimes since it is DFS you have to return in the middle of the function e.g. def dfs(): ... if dfs(): return True
Hashmap
- a subsequence is an ordering that has skips, not contiguous, so it's helpful to store the last position for lookup usually
- more obvious: char to count, char to index, (r,c) coordinates,
- more obscure: subseq to index, num - diff, prefixsum - k, prefixsum % k
Prefix Sums
- subarrays
- products with two pointers from both ends
- squares
- random pick problems
Binary Search
- if it's sorted and you need to find a value
Sliding Window
- min substring
- some use deque like sliding window max
Trees
- know how to generate BST combinations from an array of numbers (DFS with LR subtree nested for loop)
- know how to validate a BST with min, max ranges
- the tricky problems tend to be post-order/bottom-up where the parent needs answers from the subtrees first
- you can store additional info as you traverse the tree such as level[col] or [node, count of something]
- sometimes you have to convert the tree to a graph format with DFS (a tree is an u-v undirected graph with no cycles) and do graph stuff on it like check for cycles
- sometimes are there are uncommon traversals like reverse postorder (right - left - root) or reverse inorder (right - root - left), they usually start off looking like a post-order but then you realize the reverse is easier/correct
- try storing examining the parent-child relationship and storing the parent
Reduction
- if you need to do it with 2 or 3, how would do it with 1 first? then expand it out to build the full answer
- e.g. 3sum, 4sum, max sum of 3 non-overlapping subarrays
Graph
- Dijkstra and Bellman-Ford both solve single weighted shortest path, but Dijkstra can only handle + weights whereas B-F can also handle - weights
- sometimes it's helpful to BFS backwards from source <- target instead of source -> target
- sometimes we need to store multiple states and append multiple to the queue e.g. (r, c, obstacles_smashed, path_len)
- word transformation is also a graph problem, we can use wordSet = set(wordList) for faster lookups
- in DFS, how would you detect a backedge?
- Tarjan's Critical Connections algo
- Hierholzer's Eulerian Path algo
Parentheses
- probably use a stack to solve the problem
- unless it's parsing () in a calculator, then use recursion
Stacks
- sometimes you want to push the index instead of the value
- sometimes you push a tuple e.g. (num, c) or push/pop twice in a row to get 2 values
Strings
- if you want to find substring lengths, try storing the indexes somehow
Intervals
- try sorting, usually by the start time
- try taking min end times
- do a case analysis
Calculator/Parsing
- can use a hashmap and one-pass to find the ) for (, then use recursion to parse the ()
- try a stack if it might be easier, but usually need recursion
- num*10 + int(c) to parse double digits
One-off Unique Memorization
- next permutation
- copy random pointer
- quickselect (lomuto partition)
- 3-way partition
Matrix/Grid
- can we use the offsets to make anything easier? like check and store diagonals with r+c or sort by (r+c, c)