**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)