Algorithms & Data Structures in C#

Big O measures how runtime grows as input grows — not absolute speed. Know O(1), O(log n), O(n), O(n log n), O(n²) cold.

// ── O(1) — constant: index access, dictionary lookup ─
int first = arr[0];                       // always 1 step
bool has  = dict.ContainsKey("key");      // hash, always ~1 step

// ── O(log n) — halves search space each step ──────────
// Binary search, BST lookup, heap insert
int BinarySearch(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;    // avoids int overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target)  lo = mid + 1;
        else                  hi = mid - 1;
    }
    return -1;
}

// ── O(n) — linear: single pass through input ──────────
int Sum(int[] a)
{
    int total = 0;
    foreach (var x in a) total += x;     // n iterations
    return total;
}

// ── O(n log n) — efficient sorts (Merge, Quick, Heap) ─
Array.Sort(arr);                          // .NET uses IntroSort
var sorted = list.OrderBy(x => x).ToList(); // LINQ — O(n log n)

// ── O(n²) — nested loops, bubble sort ─────────────────
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (arr[i] > arr[j]) Swap(arr, i, j);

// ── Big O cheat sheet ─────────────────────────────────
// Operation               | Array  | List<T> | Dictionary | SortedSet
// Access by index         | O(1)   | O(1)    | —          | —
// Search (unsorted)       | O(n)   | O(n)    | —          | —
// Search (sorted)         | O(log n) | —    | O(1) avg   | O(log n)
// Insert at end           | O(1)*  | O(1)*   | O(1) avg   | O(log n)
// Insert at beginning     | O(n)   | O(n)    | —          | —
// Delete                  | O(n)   | O(n)    | O(1) avg   | O(log n)
// *amortized

Space complexity counts auxiliary memory — not input size. Amortized analysis averages cost over a sequence of operations; List<T> doubling is O(1) amortized even though individual resizes are O(n).

// ── Space complexity examples ─────────────────────────
// O(1) extra space — only a few variables
int FindMax(int[] a)
{
    int max = a[0];                       // 1 variable regardless of n
    for (int i = 1; i < a.Length; i++)
        if (a[i] > max) max = a[i];
    return max;
}

// O(n) extra space — output or auxiliary array
int[] Doubled(int[] a) =>
    a.Select(x => x * 2).ToArray();      // n-element output array

// O(log n) extra space — recursion stack in binary search / merge sort
void MergeSort(int[] a, int lo, int hi)  // log n stack frames max
{
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    MergeSort(a, lo, mid);
    MergeSort(a, mid + 1, hi);
    Merge(a, lo, mid, hi);
}

// ── Amortized O(1) — List<T> Append ──────────────────
// When capacity is full, List<T> doubles its internal array (O(n) copy)
// but this happens so rarely that the average cost per Add is still O(1).
var list = new List<int>(capacity: 4);
for (int i = 0; i < 1_000_000; i++)
    list.Add(i);   // ← O(1) amortized, even though ~20 resizes occurred

// Pre-allocate when you know the size to avoid ALL resizes:
var preallocated = new List<int>(1_000_000);

// ── StringBuilder — same amortized principle ──────────
var sb = new StringBuilder(256);         // initial capacity hint
for (int i = 0; i < 1000; i++)
    sb.Append(i);   // O(1) amortized per Append

The hardest skill is reading existing code and naming its complexity. Key rules: nested loops multiply, independent loops add, recursion trees multiply with branching factor.

// ── Two independent passes — O(n) + O(n) = O(n) ──────
int[] FrequencyThenSort(int[] a)
{
    // Pass 1: count — O(n)
    var freq = new Dictionary<int, int>();
    foreach (var x in a)
        freq[x] = freq.GetValueOrDefault(x) + 1;

    // Pass 2: rebuild — O(n log n) dominates
    return [.. freq.OrderByDescending(kv => kv.Value)
                   .SelectMany(kv => Enumerable.Repeat(kv.Key, kv.Value))];
}   // Overall: O(n log n)

// ── Nested loops — O(n²) ─────────────────────────────
bool HasPairSum(int[] a, int target)
{
    for (int i = 0; i < a.Length; i++)          // O(n)
        for (int j = i + 1; j < a.Length; j++)  // O(n)
            if (a[i] + a[j] == target) return true;
    return false;
}
// ✅ Reducible to O(n) with a HashSet — see Section 7

// ── Recursion tree — O(2^n) fibonacci (naive) ────────
int Fib(int n) => n <= 1 ? n : Fib(n - 1) + Fib(n - 2);
// Each call spawns 2 more → 2^n total calls

// ── Same result — O(n) with memoization ───────────────
int Fib(int n, int[] memo)
{
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo);
}
// Each subproblem solved once → O(n) time, O(n) space

Merge Sort guarantees O(n log n) in all cases and is stable (equal elements keep their order). It's the algorithm behind LINQ's OrderBy and Array.Sort for reference types.

// ── Merge Sort ────────────────────────────────────────
// Time: O(n log n) | Space: O(n) auxiliary | Stable: yes
static void MergeSort(int[] arr, int lo, int hi)
{
    if (lo >= hi) return;                     // base case: 1 element
    int mid = lo + (hi - lo) / 2;
    MergeSort(arr, lo, mid);                  // sort left half
    MergeSort(arr, mid + 1, hi);              // sort right half
    Merge(arr, lo, mid, hi);                  // merge sorted halves
}

static void Merge(int[] arr, int lo, int mid, int hi)
{
    // Copy to temporary arrays
    int leftLen  = mid - lo + 1;
    int rightLen = hi - mid;
    var left  = arr[lo..(mid + 1)];
    var right = arr[(mid + 1)..(hi + 1)];

    int i = 0, j = 0, k = lo;
    while (i < leftLen && j < rightLen)
        arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];

    while (i < leftLen)  arr[k++] = left[i++];
    while (j < rightLen) arr[k++] = right[j++];
}

// ── Usage ─────────────────────────────────────────────
int[] data = [5, 2, 8, 1, 9, 3];
MergeSort(data, 0, data.Length - 1);
// data → [1, 2, 3, 5, 8, 9]

// ── .NET equivalent ───────────────────────────────────
// Array.Sort uses IntroSort (Quicksort + Heapsort + Insertion)
Array.Sort(data);

// For objects — LINQ OrderBy uses stable merge sort internally
var sorted = orders
    .OrderBy(o => o.Total)
    .ThenBy(o => o.Date)
    .ToList();

Quick Sort is in-place and cache-friendly — typically faster than Merge Sort in practice. The key is pivot choice: always-first pivot degrades to O(n²) on sorted input; median-of-three avoids this.

// ── Quick Sort with median-of-three pivot ─────────────
// Time: O(n log n) avg, O(n²) worst | Space: O(log n) stack | Stable: no
static void QuickSort(int[] arr, int lo, int hi)
{
    if (lo >= hi) return;
    int p = Partition(arr, lo, hi);
    QuickSort(arr, lo, p - 1);
    QuickSort(arr, p + 1, hi);
}

static int Partition(int[] arr, int lo, int hi)
{
    // Median-of-three: reduces worst-case probability on sorted input
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < arr[lo]) Swap(arr, lo, mid);
    if (arr[hi]  < arr[lo]) Swap(arr, lo, hi);
    if (arr[mid] < arr[hi]) Swap(arr, mid, hi);
    // arr[hi] is now the median → use as pivot
    int pivot = arr[hi];

    int i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (arr[j] <= pivot) Swap(arr, ++i, j);

    Swap(arr, i + 1, hi);
    return i + 1;
}

static void Swap(int[] arr, int i, int j) =>
    (arr[i], arr[j]) = (arr[j], arr[i]);

// ── Choosing a sort ───────────────────────────────────
// Built-in Array.Sort   → IntroSort (QS + HeapSort hybrid, not stable)
// LINQ .OrderBy         → stable merge sort, allocates
// For primitives        → Array.Sort (fastest, in-place)
// For objects           → Array.Sort / List.Sort with IComparer<T>
// For stability needed  → LINQ OrderBy or your MergeSort

// ── Span<T> sort (no allocation) ─────────────────────
Span<int> span = stackalloc int[] { 5, 2, 8, 1, 9, 3 };
span.Sort();   // System.MemoryExtensions.Sort — in-place, O(n log n)

Comparison-based sorts can't beat O(n log n). But if you know the value domain, Counting Sort and Radix Sort achieve O(n) — crucial for large arrays of bounded integers.

// ── Counting Sort — O(n + k) where k = value range ───
// Stable, O(n + k) time/space. Use when values are small integers.
static int[] CountingSort(int[] arr, int maxVal)
{
    var count  = new int[maxVal + 1];
    var output = new int[arr.Length];

    foreach (var x in arr) count[x]++;
    for (int i = 1; i <= maxVal; i++) count[i] += count[i - 1];
    for (int i = arr.Length - 1; i >= 0; i--)  // reverse for stability
        output[--count[arr[i]]] = arr[i];

    return output;
}

// Example: sort ages 0–120
int[] ages = [25, 17, 42, 25, 8, 17];
var sortedAges = CountingSort(ages, 120);

// ── Radix Sort — O(d * n) where d = number of digits ─
// Sort by least-significant digit first using stable counting sort
static int[] RadixSort(int[] arr)
{
    int max = arr.Max();
    for (int exp = 1; max / exp > 0; exp *= 10)
        arr = CountingSortByDigit(arr, exp);
    return arr;
}

static int[] CountingSortByDigit(int[] arr, int exp)
{
    var output = new int[arr.Length];
    var count  = new int[10];

    foreach (var x in arr) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    for (int i = arr.Length - 1; i >= 0; i--)
    {
        int digit = (arr[i] / exp) % 10;
        output[--count[digit]] = arr[i];
    }
    return output;
}

// ── When to use which sort ────────────────────────────
// General purpose, unknown range  → Array.Sort  (IntroSort, O(n log n))
// Stability required              → LINQ OrderBy (MergeSort, O(n log n))
// Integers, small range (0–k)     → Counting Sort (O(n + k))
// Integers, large range, few digits → Radix Sort  (O(d * n))

Binary search requires sorted input and halves the search space each step. Know both the iterative form (no stack overflow risk) and how to adapt it for "first/last occurrence" and boundary queries.

// ── Standard binary search ────────────────────────────
// Time: O(log n) | Space: O(1) | Pre-condition: array is sorted
static int BinarySearch(int[] arr, int target)
{
    int lo = 0, hi = arr.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;   // ← avoids (lo+hi) overflow
        if      (arr[mid] == target) return mid;
        else if (arr[mid] < target)  lo = mid + 1;
        else                         hi = mid - 1;
    }
    return -1;   // not found
}

// ── First occurrence (left boundary) ─────────────────
static int FirstOccurrence(int[] arr, int target)
{
    int lo = 0, hi = arr.Length - 1, result = -1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) { result = mid; hi = mid - 1; } // keep going left
        else if (arr[mid] < target) lo = mid + 1;
        else                        hi = mid - 1;
    }
    return result;
}

// ── Binary search on answer space ─────────────────────
// "Find the minimum capacity k such that n items fit in at most m bins"
static int BinarySearchOnAnswer(int[] items, int m)
{
    int lo = items.Max(), hi = items.Sum();   // min/max capacity bounds
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (FitsInBins(items, mid, m)) hi = mid;  // try smaller
        else                            lo = mid + 1;
    }
    return lo;
}

// ── .NET built-in binary search ───────────────────────
int[] sorted = [1, 3, 5, 7, 9, 11];
int idx = Array.BinarySearch(sorted, 7);   // returns index (>=0) or ~insertionPoint
if (idx < 0) Console.WriteLine($"Not found; insert at {~idx}");

// List<T> version
var list = new List<int> { 1, 3, 5, 7, 9 };
int pos = list.BinarySearch(5);   // same convention

BFS uses a queue and visits nodes layer by layer. It's the right algorithm whenever you need the shortest path in an unweighted graph, or want to process nodes level by level.

// ── BFS on a tree (level-order) ───────────────────────
class TreeNode(int val, TreeNode? left = null, TreeNode? right = null)
{
    public int Val   = val;
    public TreeNode? Left  = left;
    public TreeNode? Right = right;
}

static IList<IList<int>> LevelOrder(TreeNode? root)
{
    var result = new List<IList<int>>();
    if (root is null) return result;

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        int levelSize = queue.Count;
        var level = new List<int>();

        for (int i = 0; i < levelSize; i++)
        {
            var node = queue.Dequeue();
            level.Add(node.Val);
            if (node.Left  is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        result.Add(level);
    }
    return result;
}

// ── BFS shortest path on unweighted graph ─────────────
static int ShortestPath(Dictionary<int, List<int>> graph, int src, int dst)
{
    var visited = new HashSet<int> { src };
    var queue   = new Queue<(int node, int dist)>();
    queue.Enqueue((src, 0));

    while (queue.Count > 0)
    {
        var (node, dist) = queue.Dequeue();
        if (node == dst) return dist;

        foreach (var neighbour in graph[node])
        {
            if (visited.Add(neighbour))          // Add returns false if already present
                queue.Enqueue((neighbour, dist + 1));
        }
    }
    return -1;   // unreachable
}

DFS dives as deep as possible before backtracking. Use it for path finding, cycle detection, topological sort, and connected-component labelling. Prefer iterative DFS for deep graphs to avoid stack overflow.

// ── DFS on a tree (recursive) ────────────────────────
static int MaxDepth(TreeNode? node)
{
    if (node is null) return 0;
    return 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right));
}

// ── DFS on a graph (iterative — no stack overflow risk) ─
static bool HasPath(Dictionary<int, List<int>> graph, int src, int dst)
{
    var visited = new HashSet<int>();
    var stack   = new Stack<int>();
    stack.Push(src);

    while (stack.Count > 0)
    {
        int node = stack.Pop();
        if (node == dst) return true;
        if (!visited.Add(node)) continue;     // already explored

        foreach (var neighbour in graph[node])
            if (!visited.Contains(neighbour))
                stack.Push(neighbour);
    }
    return false;
}

// ── Cycle detection (undirected graph) ───────────────
static bool HasCycle(Dictionary<int, List<int>> graph)
{
    var visited = new HashSet<int>();

    bool Dfs(int node, int parent)
    {
        visited.Add(node);
        foreach (var nb in graph[node])
        {
            if (!visited.Contains(nb))
            {
                if (Dfs(nb, node)) return true;
            }
            else if (nb != parent) return true;   // back-edge = cycle
        }
        return false;
    }

    foreach (var node in graph.Keys)
        if (!visited.Contains(node) && Dfs(node, -1))
            return true;

    return false;
}

Arrays give O(1) random access and are the foundation of most other structures. Know their limits: O(n) insert/delete in the middle, and how List<T> amortizes resize cost.

// ── Array fundamentals ────────────────────────────────
int[] arr = new int[5];          // fixed size, zero-initialised
arr[0] = 10;                     // O(1) write
int v = arr[4];                  // O(1) read
// arr[5] = 1;                   // ❌ IndexOutOfRangeException

// Slices — zero-copy window into the same memory
int[] data = [10, 20, 30, 40, 50];
ReadOnlySpan<int> mid = data.AsSpan(1, 3);   // [20, 30, 40] — no alloc

// ── List<T> — dynamic array ──────────────────────────
var list = new List<int>([1, 2, 3, 4, 5]);
list.Add(6);                     // O(1) amortized
list.Insert(0, 0);               // O(n) — shifts all elements right
list.RemoveAt(0);                // O(n) — shifts all elements left
list.Sort();                     // in-place IntroSort

// ── Two-pointer: remove duplicates in-place ───────────
// Sorted input; pointer i = write head, j = read head
static int RemoveDuplicates(int[] arr)
{
    if (arr.Length == 0) return 0;
    int i = 0;
    for (int j = 1; j < arr.Length; j++)
        if (arr[j] != arr[i]) arr[++i] = arr[j];
    return i + 1;   // new length
}

// ── Two-pointer: reverse an array in-place ────────────
static void Reverse(int[] arr)
{
    int lo = 0, hi = arr.Length - 1;
    while (lo < hi) (arr[lo++], arr[hi--]) = (arr[hi], arr[lo]);
}

// ── Rotation (cyclic right shift by k) ───────────────
static void Rotate(int[] arr, int k)
{
    k %= arr.Length;
    Reverse(arr, 0, arr.Length - 1);
    Reverse(arr, 0, k - 1);
    Reverse(arr, k, arr.Length - 1);
}
static void Reverse(int[] a, int lo, int hi)
{
    while (lo < hi) (a[lo++], a[hi--]) = (a[hi], a[lo]);
}

Linked lists shine where you need O(1) insert/delete at a known node without shifting. Key patterns: fast/slow pointers (Floyd's cycle detection) and dummy-head simplification.

// ── Node definition ───────────────────────────────────
class ListNode(int val, ListNode? next = null)
{
    public int Val     = val;
    public ListNode? Next = next;
}

// ── Reverse a linked list (iterative) ────────────────
static ListNode? Reverse(ListNode? head)
{
    ListNode? prev = null, curr = head;
    while (curr is not null)
    {
        var next = curr.Next;
        curr.Next = prev;
        prev = curr;
        curr = next;
    }
    return prev;   // new head
}

// ── Floyd's cycle detection (fast/slow pointers) ──────
static bool HasCycle(ListNode? head)
{
    var slow = head;
    var fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (slow == fast) return true;   // pointers met → cycle
    }
    return false;
}

// ── Merge two sorted lists ────────────────────────────
static ListNode? MergeSorted(ListNode? l1, ListNode? l2)
{
    var dummy = new ListNode(0);     // sentinel head avoids null checks
    var curr  = dummy;
    while (l1 is not null && l2 is not null)
    {
        if (l1.Val <= l2.Val) { curr.Next = l1; l1 = l1.Next; }
        else                  { curr.Next = l2; l2 = l2.Next; }
        curr = curr.Next;
    }
    curr.Next = l1 ?? l2;           // attach remaining nodes
    return dummy.Next;
}

// ── Find middle node (slow/fast) ─────────────────────
static ListNode? Middle(ListNode? head)
{
    var slow = head;
    var fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }
    return slow;   // stops at floor(n/2)
}

// ── .NET LinkedList<T> ────────────────────────────────
var ll = new LinkedList<int>([1, 2, 3]);
ll.AddFirst(0);                         // O(1)
ll.AddLast(4);                          // O(1)
ll.Remove(ll.Find(2)!);                 // O(1) with node reference

Stack (LIFO) and Queue (FIFO) are the engines of DFS and BFS. The monotonic stack/queue is the secret weapon for "nearest greater element" and sliding-window maximum problems.

// ── Stack — LIFO ──────────────────────────────────────
var stack = new Stack<int>();
stack.Push(1); stack.Push(2); stack.Push(3);
int top    = stack.Peek();   // 3  — O(1), no remove
int popped = stack.Pop();    // 3  — O(1)

// ── Queue — FIFO ──────────────────────────────────────
var queue = new Queue<int>();
queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3);
int front    = queue.Peek();    // 1
int dequeued = queue.Dequeue(); // 1

// ── Deque (double-ended queue) ────────────────────────
var deque = new LinkedList<int>();   // or use .NET 9 Deque (if available)
deque.AddFirst(0);
deque.AddLast(1);
deque.RemoveFirst();
deque.RemoveLast();

// ── Valid parentheses (classic stack problem) ─────────
static bool IsValid(string s)
{
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') { stack.Push(c); continue; }
        if (stack.Count == 0) return false;
        char top = stack.Pop();
        if (c == ')' && top != '(') return false;
        if (c == ']' && top != '[') return false;
        if (c == '}' && top != '{') return false;
    }
    return stack.Count == 0;
}

// ── Monotonic stack — next greater element ────────────
static int[] NextGreater(int[] arr)
{
    var result = new int[arr.Length];
    Array.Fill(result, -1);
    var stack = new Stack<int>();  // stores indices

    for (int i = 0; i < arr.Length; i++)
    {
        while (stack.Count > 0 && arr[stack.Peek()] < arr[i])
            result[stack.Pop()] = arr[i];
        stack.Push(i);
    }
    return result;
}
// [2,1,2,4,3] → [4,2,4,-1,-1]

A BST keeps left subtree < node < right subtree, giving O(log n) average for all operations. A balanced BST (AVL, Red-Black) guarantees O(log n) worst-case; .NET's SortedDictionary/SortedSet use a Red-Black tree internally.

class BstNode(int val)
{
    public int Val      = val;
    public BstNode? Left, Right;
}

// ── Insert ────────────────────────────────────────────
static BstNode Insert(BstNode? node, int val)
{
    if (node is null) return new BstNode(val);
    if (val < node.Val) node.Left  = Insert(node.Left,  val);
    else if (val > node.Val) node.Right = Insert(node.Right, val);
    // if val == node.Val: ignore duplicates
    return node;
}

// ── Search ────────────────────────────────────────────
static bool Search(BstNode? node, int val)
{
    while (node is not null)
    {
        if      (val == node.Val) return true;
        else if (val <  node.Val) node = node.Left;
        else                      node = node.Right;
    }
    return false;
}

// ── Validate BST (range checking) ────────────────────
static bool IsValidBST(BstNode? node,
    long min = long.MinValue, long max = long.MaxValue)
{
    if (node is null) return true;
    if (node.Val <= min || node.Val >= max) return false;
    return IsValidBST(node.Left,  min, node.Val)
        && IsValidBST(node.Right, node.Val, max);
}

// ── .NET SortedDictionary — Red-Black tree ─────────
var sd = new SortedDictionary<int, string>();
sd[3] = "three"; sd[1] = "one"; sd[2] = "two";
foreach (var kv in sd)                // always in key order
    Console.WriteLine($"{kv.Key}: {kv.Value}");

// SortedSet<T> — O(log n) Add, Remove, Contains
var ss = new SortedSet<int> { 5, 1, 3, 7, 2 };
Console.WriteLine(ss.Min);  // 1
Console.WriteLine(ss.Max);  // 7

The four traversal orders each reveal a different aspect of the tree. Inorder of a BST yields sorted output. Postorder is used in expression evaluation and file-system deletion. Level-order (BFS) gives the visual top-to-bottom reading.

// ── Inorder: Left → Root → Right ─────────────────────
// BST inorder → sorted ascending sequence
static IEnumerable<int> Inorder(TreeNode? node)
{
    if (node is null) yield break;
    foreach (var v in Inorder(node.Left))  yield return v;
    yield return node.Val;
    foreach (var v in Inorder(node.Right)) yield return v;
}

// ── Preorder: Root → Left → Right ────────────────────
// Useful for cloning or serialising a tree
static void Preorder(TreeNode? node, IList<int> result)
{
    if (node is null) return;
    result.Add(node.Val);
    Preorder(node.Left,  result);
    Preorder(node.Right, result);
}

// ── Postorder: Left → Right → Root ───────────────────
// Used for: deleting a tree, evaluating expression trees
static void Postorder(TreeNode? node, IList<int> result)
{
    if (node is null) return;
    Postorder(node.Left,  result);
    Postorder(node.Right, result);
    result.Add(node.Val);
}

// ── Level-order (BFS) ─────────────────────────────────
static IList<IList<int>> LevelOrder(TreeNode? root)
{
    var result = new List<IList<int>>();
    if (root is null) return result;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var level = new List<int>();
        for (int i = 0, n = queue.Count; i < n; i++)
        {
            var node = queue.Dequeue();
            level.Add(node.Val);
            if (node.Left  is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        result.Add(level);
    }
    return result;
}

// ── Iterative inorder (no recursion) ─────────────────
static IList<int> InorderIterative(TreeNode? root)
{
    var result = new List<int>();
    var stack  = new Stack<TreeNode>();
    var curr   = root;
    while (curr is not null || stack.Count > 0)
    {
        while (curr is not null) { stack.Push(curr); curr = curr.Left; }
        curr = stack.Pop();
        result.Add(curr.Val);
        curr = curr.Right;
    }
    return result;
}

A heap is a complete binary tree where every parent satisfies the heap property. It gives O(1) peek at the min/max and O(log n) insert/remove. .NET's PriorityQueue<TElement,TPriority> wraps a 4-ary heap.

// ── PriorityQueue<T,P> — .NET 6+ ─────────────────────
// Min-heap by default (lowest priority value dequeued first)
var pq = new PriorityQueue<string, int>();
pq.Enqueue("low",    10);
pq.Enqueue("high",    1);
pq.Enqueue("medium",  5);

Console.WriteLine(pq.Dequeue());   // "high"   — priority 1
Console.WriteLine(pq.Dequeue());   // "medium" — priority 5

// ── Top K largest elements — O(n log k) ───────────────
static int[] TopKLargest(int[] nums, int k)
{
    // min-heap of size k: root is the smallest of the top-k
    var pq = new PriorityQueue<int, int>();
    foreach (var n in nums)
    {
        pq.Enqueue(n, n);
        if (pq.Count > k) pq.Dequeue();   // evict smallest
    }
    return [.. pq.UnorderedItems.Select(x => x.Element).OrderDescending()];
}

// ── K-way merge of sorted lists ───────────────────────
static IEnumerable<int> KWayMerge(IList<int[]> lists)
{
    var pq = new PriorityQueue<(int val, int li, int idx), int>();
    for (int i = 0; i < lists.Count; i++)
        if (lists[i].Length > 0)
            pq.Enqueue((lists[i][0], i, 0), lists[i][0]);

    while (pq.Count > 0)
    {
        var (val, li, idx) = pq.Dequeue();
        yield return val;
        int next = idx + 1;
        if (next < lists[li].Length)
            pq.Enqueue((lists[li][next], li, next), lists[li][next]);
    }
}

// ── Heap sort (in-place, O(n log n)) ─────────────────
static void HeapSort(int[] arr)
{
    int n = arr.Length;
    for (int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--)
    {
        (arr[0], arr[i]) = (arr[i], arr[0]);   // move max to end
        Heapify(arr, i, 0);
    }
}
static void Heapify(int[] arr, int n, int i)
{
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) { (arr[i], arr[largest]) = (arr[largest], arr[i]); Heapify(arr, n, largest); }
}

Adjacency list uses O(V + E) space and is the default for sparse graphs. Adjacency matrix uses O(V²) space but gives O(1) edge lookup — useful when the graph is dense or you frequently ask "is there an edge between u and v?".

// ── Adjacency list (sparse graphs — preferred) ────────
var graph = new Dictionary<int, List<int>>
{
    [0] = [1, 2],
    [1] = [0, 3],
    [2] = [0, 3],
    [3] = [1, 2, 4],
    [4] = [3]
};

// Add an edge (undirected)
void AddEdge(Dictionary<int, List<int>> g, int u, int v)
{
    g.GetOrAdd(u).Add(v);
    g.GetOrAdd(v).Add(u);
}

// ── Adjacency matrix (dense graphs / O(1) edge lookup) ─
int n = 5;
bool[,] matrix = new bool[n, n];
matrix[0, 1] = matrix[1, 0] = true;   // undirected edge 0—1
matrix[0, 2] = matrix[2, 0] = true;   // undirected edge 0—2
bool hasEdge = matrix[1, 3];           // O(1) query

// ── Weighted graph — adjacency list with edge weight ──
var weighted = new Dictionary<int, List<(int to, int weight)>>
{
    [0] = [(1, 4), (2, 1)],
    [2] = [(1, 2), (3, 5)],
    [1] = [(3, 1)],
    [3] = []
};

// ── Count connected components ────────────────────────
static int CountComponents(int n, int[][] edges)
{
    var adj = Enumerable.Range(0, n)
        .ToDictionary(i => i, _ => new List<int>());
    foreach (var e in edges)
    { adj[e[0]].Add(e[1]); adj[e[1]].Add(e[0]); }

    var visited = new HashSet<int>();
    int count   = 0;
    for (int i = 0; i < n; i++)
        if (visited.Add(i)) { Dfs(adj, visited, i); count++; }
    return count;
}
static void Dfs(Dictionary<int, List<int>> g, HashSet<int> vis, int node)
{
    foreach (var nb in g[node])
        if (vis.Add(nb)) Dfs(g, vis, nb);
}

Dijkstra finds the shortest path in a weighted graph with non-negative edge weights. Use a min-heap (PriorityQueue) for the efficient O((V+E) log V) implementation.

// ── Dijkstra — single-source shortest paths ───────────
// Time: O((V + E) log V) with PriorityQueue
// Pre-condition: all edge weights >= 0
static int[] Dijkstra(
    Dictionary<int, List<(int to, int w)>> graph, int src, int n)
{
    var dist = new int[n];
    Array.Fill(dist, int.MaxValue);
    dist[src] = 0;

    // (distance, node)
    var pq = new PriorityQueue<int, int>();
    pq.Enqueue(src, 0);

    while (pq.Count > 0)
    {
        pq.TryDequeue(out int node, out int d);
        if (d > dist[node]) continue;           // stale entry — skip

        foreach (var (to, w) in graph.GetValueOrDefault(node, []))
        {
            int newDist = dist[node] + w;
            if (newDist < dist[to])
            {
                dist[to] = newDist;
                pq.Enqueue(to, newDist);
            }
        }
    }
    return dist;   // dist[i] = shortest distance from src to i
}

// ── Reconstruct path ──────────────────────────────────
static List<int> ShortestPath(
    Dictionary<int, List<(int to, int w)>> graph, int src, int dst, int n)
{
    var dist = new int[n]; Array.Fill(dist, int.MaxValue); dist[src] = 0;
    var prev = new int[n]; Array.Fill(prev, -1);
    var pq   = new PriorityQueue<int, int>();
    pq.Enqueue(src, 0);

    while (pq.Count > 0)
    {
        pq.TryDequeue(out int node, out int d);
        if (d > dist[node]) continue;
        foreach (var (to, w) in graph.GetValueOrDefault(node, []))
        {
            int nd = dist[node] + w;
            if (nd < dist[to]) { dist[to] = nd; prev[to] = node; pq.Enqueue(to, nd); }
        }
    }

    var path = new List<int>();
    for (int at = dst; at != -1; at = prev[at]) path.Add(at);
    path.Reverse();
    return path[0] == src ? path : [];   // empty if unreachable
}

Topological sort orders nodes so every directed edge u→v has u before v. It's only possible on Directed Acyclic Graphs (DAGs). Use it for build systems, course scheduling, and dependency resolution.

// ── Kahn's algorithm (BFS-based topo sort) ────────────
// Returns [] if a cycle exists
static int[] TopologicalSort(int n, int[][] edges)
{
    var adj      = new List<int>[n].Select(_ => new List<int>()).ToArray();
    var inDegree = new int[n];

    foreach (var e in edges)
    {
        adj[e[0]].Add(e[1]);
        inDegree[e[1]]++;
    }

    var queue = new Queue<int>();
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) queue.Enqueue(i);

    var order = new List<int>();
    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        order.Add(node);
        foreach (var nb in adj[node])
            if (--inDegree[nb] == 0) queue.Enqueue(nb);
    }

    return order.Count == n ? [.. order] : [];   // [] = cycle detected
}

// ── DFS-based topo sort ───────────────────────────────
static int[] TopoSortDFS(int n, int[][] edges)
{
    var adj = new List<int>[n].Select(_ => new List<int>()).ToArray();
    foreach (var e in edges) adj[e[0]].Add(e[1]);

    var state  = new int[n];   // 0=unvisited, 1=in-stack, 2=done
    var result = new Stack<int>();
    bool hasCycle = false;

    void Dfs(int u)
    {
        if (hasCycle) return;
        state[u] = 1;
        foreach (var v in adj[u])
        {
            if (state[v] == 1) { hasCycle = true; return; }
            if (state[v] == 0) Dfs(v);
        }
        state[u] = 2;
        result.Push(u);
    }

    for (int i = 0; i < n; i++)
        if (state[i] == 0) Dfs(i);

    return hasCycle ? [] : result.ToArray();
}

DP solves problems by breaking them into overlapping subproblems and caching results. Top-down (memoization) is recursive + cache; bottom-up (tabulation) fills a table iteratively and avoids recursion overhead.

// ── Classic: Fibonacci ────────────────────────────────
// Naive: O(2^n)
// With memoization: O(n) time, O(n) space
static Dictionary<int, long> _memo = new();
static long FibMemo(int n)
{
    if (n <= 1) return n;
    if (_memo.TryGetValue(n, out var v)) return v;
    return _memo[n] = FibMemo(n - 1) + FibMemo(n - 2);
}

// Tabulation (bottom-up): O(n) time, O(1) space
static long FibTab(int n)
{
    if (n <= 1) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) (a, b) = (b, a + b);
    return b;
}

// ── Coin Change — minimum coins for amount ─────────────
// dp[i] = min coins needed to make amount i
static int CoinChange(int[] coins, int amount)
{
    var dp = new int[amount + 1];
    Array.Fill(dp, amount + 1);   // "infinity"
    dp[0] = 0;

    for (int i = 1; i <= amount; i++)
        foreach (var coin in coins)
            if (coin <= i)
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1);

    return dp[amount] > amount ? -1 : dp[amount];
}
// CoinChange([1,5,10,25], 36) → 3  (25+10+1)

// ── Longest Common Subsequence ────────────────────────
// dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
static int LCS(string s, string t)
{
    int m = s.Length, n = t.Length;
    var dp = new int[m + 1, n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i, j] = s[i-1] == t[j-1]
                ? dp[i-1, j-1] + 1
                : Math.Max(dp[i-1, j], dp[i, j-1]);
    return dp[m, n];
}
// LCS("abcde", "ace") → 3

Two pointers solve pair/triplet sum problems in O(n) on sorted arrays. Sliding window maintains a subarray or substring window in O(n), replacing O(n²) brute-force approaches.

// ── Two Sum II — sorted array, target sum ─────────────
// O(n) time, O(1) space
static (int, int) TwoSum(int[] arr, int target)
{
    int lo = 0, hi = arr.Length - 1;
    while (lo < hi)
    {
        int sum = arr[lo] + arr[hi];
        if      (sum == target) return (lo, hi);
        else if (sum <  target) lo++;
        else                    hi--;
    }
    return (-1, -1);
}

// ── 3Sum — find all triplets summing to 0 ─────────────
static IList<IList<int>> ThreeSum(int[] nums)
{
    Array.Sort(nums);
    var result = new List<IList<int>>();
    for (int i = 0; i < nums.Length - 2; i++)
    {
        if (i > 0 && nums[i] == nums[i-1]) continue;   // skip duplicates
        int lo = i + 1, hi = nums.Length - 1;
        while (lo < hi)
        {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum == 0)
            {
                result.Add([nums[i], nums[lo], nums[hi]]);
                while (lo < hi && nums[lo] == nums[lo+1]) lo++;
                while (lo < hi && nums[hi] == nums[hi-1]) hi--;
                lo++; hi--;
            }
            else if (sum < 0) lo++;
            else              hi--;
        }
    }
    return result;
}

// ── Sliding window — longest substring without repeats ─
// O(n) time, O(k) space where k = alphabet size
static int LengthOfLongestSubstring(string s)
{
    var seen = new Dictionary<char, int>();   // char → last seen index
    int max  = 0, left = 0;
    for (int right = 0; right < s.Length; right++)
    {
        char c = s[right];
        if (seen.TryGetValue(c, out int prev) && prev >= left)
            left = prev + 1;   // shrink window past the duplicate
        seen[c] = right;
        max = Math.Max(max, right - left + 1);
    }
    return max;
}
// "abcabcbb" → 3  ("abc")

Prefix sums turn O(n) range queries into O(1). A HashSet converts many O(n²) "find a pair" problems into O(n). Binary search on the answer space solves optimisation problems by turning them into feasibility checks.

// ── Prefix sum — O(1) range sum after O(n) build ──────
static int[] BuildPrefix(int[] arr)
{
    var prefix = new int[arr.Length + 1];
    for (int i = 0; i < arr.Length; i++)
        prefix[i + 1] = prefix[i] + arr[i];
    return prefix;
}
// Sum of arr[l..r] = prefix[r+1] - prefix[l]
// int[] a = [1,2,3,4,5];
// var p = BuildPrefix(a);
// Sum of a[1..3] = p[4] - p[1] = 9 - 1 = 9  (2+3+4)

// ── Subarray sum equals K (uses prefix + HashMap) ─────
static int SubarraySum(int[] nums, int k)
{
    var freq = new Dictionary<int, int> { [0] = 1 };
    int count = 0, sum = 0;
    foreach (var n in nums)
    {
        sum += n;
        count += freq.GetValueOrDefault(sum - k);
        freq[sum] = freq.GetValueOrDefault(sum) + 1;
    }
    return count;
}

// ── Two Sum I — unsorted (HashSet approach) ───────────
static (int, int) TwoSumHash(int[] nums, int target)
{
    var seen = new Dictionary<int, int>();   // value → index
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        if (seen.TryGetValue(complement, out int j))
            return (j, i);
        seen[nums[i]] = i;
    }
    return (-1, -1);
}

// ── Binary search on answer ───────────────────────────
// "Minimum largest sum when splitting array into k subarrays"
static int SplitArray(int[] nums, int k)
{
    int lo = nums.Max(), hi = nums.Sum();
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (CanSplit(nums, k, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
static bool CanSplit(int[] nums, int k, int limit)
{
    int parts = 1, sum = 0;
    foreach (var n in nums)
    {
        if (sum + n > limit) { parts++; sum = 0; }
        sum += n;
    }
    return parts <= k;
}