Leetcode for fun

One question a day to ensure a sharp mind.

Grading Criteria

• L0: straight forward question
• L1: variance of template
• L2: need to think for a while / complex implementation
• L3: need aha moment / unexpected algorithm

Roadmap

Study-order progression through all topic areas. Each entry links to the topic README with templates and notes.

Fundamentals

#	Topic	README	Description
1	String	README	String operations, Counter API
2	Hash Table	README	Counter operations, mapping
3	Linked List	README	Reverse, fast/slow pointers
4	Two Pointers	README	Same/different direction templates
5	Sliding Window	README	Fixed/dynamic window, at-most trick
6	Prefix Sum	README	1D/2D prefix sum, difference array
7	Binary Search	README	Template, bisect module
8	Stack	README	Monotonic stack, Eulerian path, tree traversal
9	Monotonic Queue	README	Sliding window max/min by deque
10	Histogram	README	Histogram model for matrices

Search and Graph

#	Topic	README	Description
11	BFS	README	Graph BFS template
12	BFS Tree	README	Tree level-order traversal
13	BFS/DFS Graph	README	Matrix and graph DFS
14	Dijkstra	README	Single-source shortest path
15	Floyd-Warshall	README	All-pairs shortest path
16	DFS Tree	README	Tree DFS traversal templates
17	LCA	README	Lowest common ancestor, binary lifting
18	Backtracking	README	Pruning, array/graph templates

Dynamic Programming

#	Topic	README	Description
19	DP Overview	README	Categories, matrix exponentiation
20	Knapsack	README	0/1 and unbounded knapsack
21	LIS	README	O(n^2) and O(n log n)
22	Longest Subsequence	README	LIS/LCS templates
23	Kadane	README	Maximum subarray
24	Digit DP	README	Digit DP templates with bounds

Greedy and Math

#	Topic	README	Description
25	Greedy	README	Assign/interval problems
26	Math	README	GCD/LCM, sieve, math functions
27	Combinatorics	README	Product rule, C(n,k), permutations
28	Primes	README	Sieve, factorization, LPF
29	Bezout's Lemma	README	Extended GCD
30	Game Theory	README	Minimax
31	Probability	README	Reservoir sampling, shuffle
32	Bit Manipulation	README	Bit operations, bitmask DP

Advanced Data Structures

#	Topic	README	Description
33	Trie	README	Insert, search, prefix
34	Union-Find	README	Path compression, union by rank, Kruskal's
35	Binary Indexed Tree	README	Fenwick tree
36	Segment Tree	README	Tree/array/ZKW, lazy propagation
37	Sorted Containers	README	SortedList complexity reference

Advanced Algorithms

#	Topic	README	Description
38	Sorting	README	Cycle sort
39	KMP	README	KMP pattern matching
40	Z-Function	README	Z-function pattern matching
41	Prim	README	Minimum spanning tree
42	Majority Voting	README	Boyer-Moore voting
43	Rolling Hash	README	Rabin-Karp
44	Greedy Heap	README	Heap-based greedy patterns
45	SQL	README	Query categories
46	System Design	README	General steps

Running Solutions

Solutions depend on header.py for shared imports and class definitions. Use the runner script:

python run.py path/to/solution.py

This pre-loads header.py into the namespace before executing the solution file.

Time Complexity Analysis

Row: input size(IS), column: time complexity(TC)

Input Size	O($2^n$)	O($n^4$)	O($n^3$)	O($n^2$)	O(nlogn)	O(n)	O(logn)	O(1)
1-10	✓	✓	✓	✓	✓	✓	✓	✓
10-50	✓	✓	✓	✓	✓	✓	✓	✓
50-100	✗	✗	✓	✓	✓	✓	✓	✓
100-500	✗	✗	✓	✓	✓	✓	✓	✓
500 - $10^3$	✗	✗	✗	✓	✓	✓	✓	✓
$10^3$ - $10^4$	✗	✗	✗	✓	✓	✓	✓	✓
$10^4$ - $10^5$	✗	✗	✗	?	✓	✓	✓	✓
$10^5$ - $10^6$	✗	✗	✗	✗	✓	✓	✓	✓
$10^6$ - $10^9$	✗	✗	✗	✗	✗	✗	✓	✓

TC	Algorithm
O($2^n$)	DFS-combination($2^n$), DFS-permutation(n!)
O($n^4$)	DP
O($n^3$)	DP, Floyd-Warshall
O($n^2$)	DP
O(nlogn)	Sorting, Heap, divide&conquer, Dijkstra-heap, QuickSort
O(n)	DP, DFS-tree(V), BFS(V+E), TopologicalSorting(V+E), BucketSort(N+K), MonotonicStack
O(logn)	BinarySearch, BinaryIndexTree
O(1)	Math

Approach Checklist

1. What is the data size?
2. Can I sort or group the elements?
3. Can I use DP, greedy or binary search?
4. Can I enumerate on a specific variable?
5. Can I use two passes?
6. Can I solve it reversely?
7. Can I convert the problem to another problem?
8. "Subarray" → consider sliding window, monotonic stack/queue, prefix sum + hash table, Kadane's algorithm.

Cheat sheet

Palindrome

Efficiently find all the palindrome numbers in a range 10**9:

pal = []
base = 1
while base <= 10000:
    # odd number
    for i in range(base, base * 10):
        x = i
        t = i // 10
        while t:
            x = x * 10 + t % 10
            t //= 10
        pal.append(x)
    # even number
    if base <= 1000:
        for i in range(base, base * 10):
            x = t = i
            while t:
                x = x * 10 + t % 10
                t //= 10
            pal.append(x)
    base *= 10
pal.append(1_000_000_001)  # sentinel

Reference

1. 用什么语言刷题？C++/Java/Python横向大比较
2. Leetcode 101: A Leetcode Grinding Guide(C++ Version)
3. Algorithms for Competitive Programming
4. 古城算法 slides(google drive)
5. 输入数据规模和时间复杂度的关系
6. 0x3ff-palindrome