Advanced Techniques
The building blocks of hard problems
Each technique here is a ‘power-up’ that transforms a class of seemingly impossible problems into solvable ones. You don’t need to master all of these — focus on the ones most relevant to your target companies (crypto, trading, systems). Segment trees and binary search on answer are highest ROI.
For each technique, implement a reusable Rust template that you can paste and adapt in interviews. Speed comes from preparation, not improvisation.
📊Monotonic Stack & Deque
Transforms O(n²) ‘for each element, look left/right for the nearest greater/smaller’ into O(n). Directly applicable to time-series and order book processing.
The basic pattern. Process right to left, stack holds candidates.
Circular array — iterate twice through the array.
Monotonic deque. Maintain decreasing order; front is always the max.
THE canonical mono stack problem. Must solve in under 15 minutes.
Row-by-row histogram heights, then apply #84 per row.
Mono stack + prefix sum of prefix sums. Tests composing techniques.
🎯Binary Search on Answer
‘Minimize the maximum’ or ‘maximize the minimum’ = binary search on the answer + a feasibility check function. Appears constantly in optimization problems.
Binary search on max sum. Check: can we split into ≤k parts each ≤ mid?
Same template as #410. The greedy check is the same pattern.
Real-valued binary search. Use an epsilon or fixed iterations.
Binary search on time + greedy check on battery allocation.
🌲Segment Tree & BIT
Range queries + point/range updates in O(log n). Essential for trading systems (running statistics over sliding windows) and appears in the hardest LC problems.
Classic segment tree. Build, update, query. Implement from scratch in Rust.
BIT or merge sort. Process right to left, count elements smaller than current.
Coordinate compression + lazy propagation. A complete segment tree exercise.
Segment tree optimization on DP transitions. The ‘DP + data structure’ pattern.
🔀Advanced Graph
Bellman-Ford for negative cycles (your arb bot!), Tarjan’s for network reliability, Union-Find for dynamic connectivity. These appear in systems and crypto interviews.
Bellman-Ford with K rounds. You already know this from your arb bot.
Tarjan’s bridge-finding algorithm. Must-know for systems interviews.
Kruskal’s + edge classification. Deep graph understanding.
Dual Union-Find. Process shared edges first (greedy).
🔢Trie & Bitwise
XOR tries for maximum XOR queries. Bit manipulation for efficient state encoding. Both relevant to low-level systems and crypto.
Build the basic trie. In Rust, use Vec<Option<Box<TrieNode>>> or arena alloc.
Binary trie. Insert all numbers, then for each number greedily pick opposite bits.
Offline sort + incremental trie insertion + XOR query.
Pure bit-level reasoning. Think about each bit independently.
🎲Combinatorics & Counting
Your Olympiad strength. Modular arithmetic, nCr, Catalan numbers, inclusion-exclusion. Quant firms test this directly.
Solve with C(m+n-2, m-1) instead of DP. Precompute factorials.
Recursive decomposition + nCr. Beautiful problem for your background.
Stirling numbers of the first kind. Pure combinatorial DP.
Multinomial coefficients. Precompute factorial + modular inverse.