Here is a collection of different algorithms/ideas, which can be useful.

Tags

Here is collection of different tags/ideas you should think of when you see new problem. Some of them will help to solve the problem, some of them like linked-list, just to make easier navigation among similar problems.

2d-array 2sum accumulate anagram angle sweep
array backtracking bfs binary indexed tree binary lifting
binary search bit manipulation bit-dp brackets bst
bucket sort combinations connected components constructive counter
design dfs digit build dijkstra divide and conquer
dp dp-intervals game generating functions geometry
graph graph algo greedy groupby hall's lemma
hash table heap inorder traversal interactive intervals
kmp knuth optimization line sweep linked list LIS
math matrix power maximal flow meet in the middle merge sort
monotonic deque morris traversal palindrome parser permutation
queue quick select random recursion rolling hash
segment tree simulation sliding window sort spanning tree
sparse table sqrt decomposition stack string suffix array
three pointers topological sort tree trie two pointers
union find voting xor

Useful tricks:

DP arrays

N, M, K = 2, 3, 5
dp1 = [0] * M 
dp2 = [[0] * M for _ in range(N)]    # to create N x M array.
dp3 = [[[0] * M for _ in range(N)] for _ in range(K)]   # K x N x M  array

Flatten list of lists

from itertools import chain
equations = [[1,2,3],[4,5]]
list(chain(*equations))

Sort with lambda functions

result = [[4,5],[4,6],[6,7],[2,3],[1,1]]
result.sort(key = lambda x: x[0]**2 + x[1]**2): # inplace
result = sorted(result, key = lambda x: x[0]**2 + x[1]**2)

Graph algorithms

Number Theory and Algebra algorithms

Data Structures algorithms

String algorithms

Geometry algorithms

Linear algebra algorithms

Unsorted

Sprague-Grundy theorem

Useful if we have game problem which is sum of games. (add example?)

Modular arithmetics and number theory (from e-maxx)

Euler theorem: $a^{\phi(m)} \equiv 1 (m)$, where $(a, m) = 1$, where $\phi(m)$ is Euler function, can be used to find inverse element in $O(\log m)$ time complexity: $a^{-1} = a^{\phi(m)-1} $ However in python 3.8 inverse element is implemented already.

To solve recurrent equations, like fibonacci, we can use fast matrix expontiation with complexity $O(m^3\cdot \log n)$, where $m$ is order of recurrence (2 for fibonacci) and $n$ is term we want to get.

Given module $m$ we can find $1^{-1}, 2^{-1}, \dots, n^{-1}$ for any $n$ in just $O(n)$ time.

r = [1]*(n+1)
for i in range(2, n):
    r[i] = (-m//i*r[m%i]%m)%m

For checking all submasks of given masks in $O(3^n)$, check Leetcode problem 1655.

Bridges online. If we want to find the number of brides when we change our graph: add edge by edge. There is $O(n\log n + m)$ time complexity algorithm, where $m$ is number of edges (queries) and $n$ is number of nodes. The idea is to use two DSU structures: one for connected components and another for biconnected components.

To find spanning tree of graph we can use Prim’s algorithm or Kruskal’s algorithm (with dsu) with $O(m\log n)$ time complexity. There is also a way to find number of spanning trees with $O(n^3)$ complexity, using Kirchhoff’s theorem.

Prufer sequence and Cayley’s formula helps to enumerate all spanning trees of full graph as well as number of ways to make graph full, adding minumal number of nodes.

Euler path in graph can be found in $O(E)$ time complexity, see Leetcode 0332.

Least common ancestor LCA and range minimum query RMQ: there are a lot of different ways to solve these problems, with $O(n)$ preprocessing and $O(1)$ time being the best solution.

Maximum flow/Minimum cut algorithms: Edmonds-Karp with $O(VE^2)$ time complexity, Ford-Fulkerson with $O(Ef)$, where $f$ is maximal flow, but it can have infinite loop if weights are not integer. Push-relabel maximum flow with $O(V^2\sqrt{E})$ complexity.

Hungarian algorithm: given matrix of size $n\times n$, we need to put $n$ rooks, which don’t beat each other such that sum of all cells they occupy is minumal. There is $O(n^3)$ algorithm.

Kuhn’ Algorithm — Maximum Bipartite Matching, complexity is $O(mn)$.