More Algorithms and Techniques
Searching, more sorting algorithms, array techniques and algorithm design paradigms. Bubble, merge and quick sort, binary search and dynamic programming have their own pages earlier in this subject.
This is an overview — pick a sub-topic below.
Sub-topics (21)
Linear Search
Check each element in turn until found — $O(n)$, works on unsorted data.
Sorting Overview
Comparison sorts ($\Omega(n\log n)$) vs non-comparison sorts (linear for limited keys); stable vs unstable; in-place vs extra memory.
Selection Sort
Repeatedly select the smallest remaining element and swap it into place — $O(n^2)$, few swaps.
Insertion Sort
Insert each element into the sorted part on its left — $O(n^2)$, but $O(n)$ for nearly-sorted data.
Heap Sort
Build a max-heap, then repeatedly move the max to the end — $O(n\log n)$, in place, not stable.
Counting Sort
Count occurrences of each key and rebuild the array — $O(n + k)$ for keys in range $0..k$.
Radix Sort
Sort numbers digit by digit using a stable sort — $O(d(n + b))$.
Bucket Sort
Distribute values into buckets, sort each, then concatenate.
Two Pointers
Move two indices through a sequence to avoid nested loops.
Sliding Window
Maintain a window over a sequence, updating incrementally as it moves.
Prefix Sums
Precompute running totals so any range sum is one subtraction.
Difference Arrays
Apply many range-add updates in $O(1)$ each, then rebuild with one prefix sum.
Fast and Slow Pointers
Move one pointer twice as fast as another.
Recursion in Algorithms
Solve a problem by solving smaller instances of itself.
Backtracking
Build solutions step by step and undo choices that can't lead to a valid answer.
Divide and Conquer
Split into independent subproblems, solve recursively, combine.
Greedy Algorithms
Make the locally best choice at each step.
Memoization
Top-down dynamic programming: cache results of recursive calls.
Tabulation
Bottom-up dynamic programming: fill a table from the smallest subproblems up.
Bit Manipulation Techniques
Use binary operations for speed and compact state.
Branch and Bound
Search the solution tree while discarding branches whose best possible result can't beat the current best.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.