Bag of Tricks

Goal: Map the problem to known tasks.

Thought Process

Note

  1. Does it form a group, chain, tree, graph? - union find, parent-child hashmap (set if parent-child is implicit).

  2. Does it have a search space? Is there a contiguous segment within this search space for which a condition satisfies? Is the problem about finding the boundaries of that segment? - binary search.

  3. Does the quantity grow monotonically with number of elements? - VLW.

  4. What bookkeeping is required? What involves recomputation? What else can we track to avoid it? - hashmap, bst, stack, queue, heap.

  5. Can we solve it in parts and combine the results? - divide and conquer, recursion, DP.

  6. What choices can be greedily eliminated? - two pointers, greedy, quicksort partitioning.

Find something

Types of Queries

  1. OGQ - Optimal Goal Query: VLW - variable length window + aux bookkeeping (monotonic goal), FLW - fixed length window (works for non-monotone)

  2. RSQ - Range Sum Query: \(\sum(l,r)\): Prefix sum, BIT, segment tree

  3. MSQ - Maximum Sum Query: \([0,n)->\max(\sum(l,r))\): Prefix sum->BIT, VLW->Kadane, divide and conquer->segment tree

  4. RMQ - Range Min Query: \(\min(l,r)\): [unordered] monotonic stack, monotonic queue (VLW), Cartesian tree, segment tree, [ordered] binary search, BST (VLW)

  5. RFQ - Range Frequency Query: \(c(l,r,key)\): Dict, segment tree

  6. EEQ - Earlier Existance Query: set, dict, bitmap

  7. LSQ - Latest Smaller Query: \(\max(l | l<r, v(l)<v(r))\): Monotonic stack (v1), Cartesian tree

  8. ESQ - Earliest Smaller Query: \(\min(l | l<r, v(l)<v(r))\): Monotonic stack (v2), (???) inversions/pointers?

  9. SEQ - Smallest Earlier Query: \(\min(v(l) | l<r, v(l)<v(r))\): pointer, bst, heap

  10. TKQ - Top K Query: heap

  11. RIQ - Range Intersect Query: Given point, find ranges that contains it: Interval tree

  12. ROQ - Range Overlap Query: Find intervals that overlaps with given range: Sorting + binary search, sorting + stack

  13. ECQ - Equivalence Class Query: Whether (x,y) belonds to the same group: Union find, dict for parent-child

  14. MEX - Minimum Excluded Element: (???)

  15. LCS - Longest common/increasing/palindromic subsequence: VLW, DP

  16. RUQ - Range Update Query: Prefix sum->BIT (+delta at begin, -delta at end), segment tree

General Techniques

Ordered

  1. Values explicit - vanilla Binary search.

  1. Range that satisfies the condition is on the left of the search space. Pruned range might move past it. Need to allow right to move past left.

  2. Range that satisfies the condition is on the right of the search space. Pruned range always contains it. Always reduces to size 1.

  3. Range that satisfies the condition is in the middle of the search space.

  1. Values NOT explicit

  1. Values bounded? Binary search on range. Condition check O(T(n)) -> total T(n)lg(W), W=precision

  2. Bounded either above/below? One way binary search from one end - move from i -> 2i or i -> i/2

  3. Target forms a convex function? Optimal exists at root?

  1. Can compute gradient? GD.

  2. Can compute Hessian? Newton.

Unordered

  1. Linear search

  2. Divide & conquer

  3. Use bookkeeping techniques

Bookkeeping

  1. KV map - multiple O(1) use-cases

  • freq counts - histogram delta >= 0, distinct count >=k, min freq count >= k, majority-non majority count (max freq - sum V)

  • detect earlier occurance, obtain earliest/latest occurance with paired value

  • parent-child relation (stores parent/child pointer), alternative to union-find

  1. Stack (maintains insert seq in rev + can maintain first k inserted + latest in O(1))

  2. Queue (maintains insert seq + can maintain last k inserted + earliest/latest in O(1))

  3. Dequeue (maintains insert seq + can maintain first+last k inserted + earliest/latest in O(1))

  4. BST (all earlier values searchable in O(lg n) - doesn’t maintain insert seq) - sortedcontainers.SortedList

  5. Order statistics tree (???)

  6. Heap (smallest/largest values from earlier range in O(1) + can maintain k smallest/largest - doesn’t maintain insert seq)

  7. Cartesian tree (RMQ tasks) - heap with insert seq: range min at root O(1). Constructive requires stack. Unbalanced.

  8. Monotonic stack - 2 types

  1. Type I: RMQ (Range Min/Max Query): Simulates Cartesian tree.

  1. Maintains longest monotonic subsequence from min (max) (including curr) ending at curr.

  2. At finish, corresponds to the rightmost branch of a Cartesian tree.

  3. Everything that has ever been on the stack is the min of some range. This covers all possible range mins.

  4. For every curr, all larger (smaller) values are popped - curr is RM of everything since popped.

  5. Once pushed, top is range min (max) of [S[-2]+1, top]. S[-2] is range min of [S[-3]+1, top]

  6. Bot is range min (max) for [0, top] (i.e., root of the Cartesian tree)

  7. Each value gets to be at the stack at some point.

  1. Type II: ESQ (Earliest Smaller/Larger Query)

  1. Maintains longest monotonic subsequence from first element.

  2. Everything that comes after, only pushed onto the stack if it’s larger (smaller)

  1. Monotonic queue - Same as monotonic stack except it works for sliding window as we can skip ranges by popping root (at front).

  2. Min (max) stack (maintains range min (max) for [0, curr] at top + keeps all elements + obtain in O(1))

  3. Min (max) queue (maintains range min (max) for [0, curr] at back + keeps all elements + obtain in O(1))

  4. Segment tree (RSQ/RMQ, all subarray sums with prefix/suffix/sum in tree) - mutable, extends to 2d

  5. Interval tree (find value in range)

  6. Multidimensional - KD tree

  7. Binary indexed tree (???) - mutable

  8. Sparse table (RMQ)

  9. Union find (equivalence classes)

  10. Trie (prefix matching)

  11. String hashing - Rabin Karp

  12. Make bookkeeping faster - sqrt decomposition

Count something

  1. Can we count compliment instead?

Modify something

  1. Two pointers + swap

  2. Dutch national flag

Schedule something

  1. Priority queue + optional external dict for value - greedy

  2. [Tarjan][Kahn] Topological sort

Assign something

  1. Two pointers

  2. [Kuhn] Maximal bipartite matching

Optimise something

  1. DP - Classic problems

  1. 0-1 knapsack

  2. Complete knapsack

  3. Multiple knapsack

  4. Monotone queue optimization

  5. Subset sum

  6. Longest common subsequence

  7. Longest increasing subsequence (LIS)

  8. Longest palindromic subsequence

  9. Rod cutting

  10. Edit distance

  11. Counting paths in a 2D array

  12. Longest Path in DAG

  13. Divide and conquer DP

  14. Knuth’s optimisation

  15. ASSP [Floyd Warshall]

  1. Greedy

  1. Two pointers

  2. Sliding window

  3. Shortest path - SSSP [Dijkstra][Bellman Ford]

  4. Lightest edge - MST [Prim][Kruskal]

Check connectivity, grouping & cyclic dependencies

  1. Tortoise & hare algorithm

  2. BFS for bipartite detection

  3. DFS with edge classification, union-find

  4. Lowest common ancestor - tree/graph - [Euler’s tour],[Tarjan],[Farach-Colton and Bender]

  5. Connected components

  6. Articulation vertex and biconneted components

  7. [Kosaraju] Strongly connected components

  8. Eulerian circuit for cycle visiting all vertices

Combine something

  1. Backtracking

Design something

  1. Mostly bookkeeping

Validate something

  1. Paring problems - Stack

  2. Regex problems - DP

Involves intervals

  1. Sort them - overlap check left-end >= right-start

  2. Sort by start - benefit (???)

  3. Sort by end - benefit (???)