Algorithmic Idioms & Invariants
In competitive programming and staff-level engineering interviews, breakthroughs often hinge on mechanical strokes of genius, algebraic dualities, and geometric reductions that shatter standard complexity bounds. Master these tactical invariants once, and deploy them across hundreds of problems.
K-Way Matrix Frontier (Heap Wavefront)
Invariant:At any step t ∈ [1, K], the min-heap contains exactly the unconsumed minimum candidate element from each active row. The root of the heap is unconditionally the global minimum among all remaining matrix elements.
Three-Reversal Array Rotation
Invariant:Block transposition identity: For any sequence split into blocks A and B, the composition of blockwise reversals followed by a global reversal satisfies (A^R B^R)^R = B A.
Saddleback 2D Matrix Elimination
Invariant:The search window is bounded by matrix[r..M-1][0..c]. If target exists in the matrix, it is guaranteed to reside strictly within this remaining rectangular subgrid.
The Contribution Technique
Invariant:TotalSum = ∑_{i=0}^{N-1} (A[i] × LeftSpan[i] × RightSpan[i]). Every contiguous subarray has a unique minimum element (using strict inequality on one side to break ties), ensuring zero double-counting and zero missed subarrays.
The Difference Array (Range Derivative)
Invariant:For any array A and difference array D, A[i] = ∑_{j=0}^{i} D[j]. Applying D[L] += V and D[R+1] -= V alters the prefix sum by +V for all indices j ∈ [L, R] and by 0 for all indices j > R.
Virtual Doubling for Cyclic Arrays
Invariant:For any cyclic array A of size N, the circular traversal A[0] -> A[1] -> ... -> A[N-1] -> A[0] -> ... -> A[N-1] is isomorphic to traversing the linear virtual array V[i] = A[i mod N] for i ∈ [0, 2N - 1].
Sentinel (Dummy Head) Node Injection
Invariant:The sentinel nodes dummy_head and dummy_tail permanently anchor the list boundaries. Every real data node x satisfies: dummy_head.next ... == x and x.next ... == dummy_tail. The list is never empty.
Floyd's Modular Phase Alignment
Invariant:Phase 1 Collision Invariant: 2 × dist(slow) = dist(fast) = 2(L + k). In the cycle, 2(L + k) ≡ L + k (mod C) ⟹ L ≡ C - k (mod C). Therefore, advancing L steps from both head and collision point meets at the cycle origin.