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

• 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?

• 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

• 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

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

• DAG -> Topological Sort

• Critical Connections -> DFS: determine if tree edge connecting node to parent is critical or not