Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

This post will be about shortest path problems when the weights may be negative: Bellman-Ford and Floyd-Warshall.

When to use

Dijkstra (see the Heaps post) is fantastic when all weights are non-negative, but as soon as negative edge weights appear (currency arbitrage, flight prices with refunds, or certain graph modeling tricks) Dijkstra fails.  

Bellman-Ford solves the single-source shortest path problem with negatives and can detect negative cycles.

• single source, possible negative edges, need to detect negative cycles (O(V·E) is acceptable).

Floyd-Warshall solves the all-pairs shortest path problem in one shot and also detects negative cycles.

• dense graph (E ≈ V²), need distances between every pair of nodes, V ≤ 400 (O(V³) is fine).

Typical problems: cheapest flights with refunds, arbitrage detection, transitive closure, "find the city with the smallest number of reachable neighbors within a distance threshold".

Theory

Relaxing an edge means that if the path from source to a destination node is shorter if doing it via an intermediate node, we update the estimate for the distance from source to destination. The term comes from the fact that the distance to a node is an upper bound (a "relaxed" estimate) on the true shortest-path distance. When we find a better path, we relax (lower) that upper bound. The operation never increases the estimate, and after enough relaxations the estimates become exact shortest-path distances.

Bellman–Ford, Dijkstra, A*, Johnson's algorithm and others use edge relaxing. 

Bellman-Ford

The core idea of the algorithm is to relax every edge |V|−1 times. After that, any further relaxation means a negative cycle exists.

Implementation:

int[] ShortestPath(int n, int[][] edges, int src)
{
    const int halfMax = int.MaxValue / 2;
    int[] dist = new int[n];
    Array.Fill(dist, halfMax);
    dist[src] = 0;

    // Relax |V|-1 times
    for (int i = 0; i < n - 1; i++)
    {
        foreach (var e in edges)
        {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != halfMax && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }

    // Check for negative cycle
    foreach (var e in edges)
    {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != halfMax && dist[u] + w < dist[v])
            return null; // negative cycle reachable from src
    }

    return dist;
}

int[][] edges = [
    [0, 1, 5],
    [1, 2, -3],
    [0, 2, 10]
];

var dist = ShortestPath(3, edges, 0);

Console.WriteLine(dist != null
    ? string.Join(", ", dist)   // 0, 5, 2
    : "Negative cycle detected");

Complexity

• Time: O(V*E)
• Space: O(V)

The O(V*E) time bound follows directly from |V| passes over the edge list, and the space is O(|V|). In practice the algorithm often converges early (no updates in a pass), but the worst-case analysis guarantees correctness even on adversarial inputs with negatives. This combination of dynamic-programming clarity, negative-weight tolerance, and built-in cycle detection makes Bellman-Ford the theoretical foundation for many more advanced shortest-path algorithms (Johnson’s algorithm, difference constraints, etc.).

The Bellman-Ford algorithm solves the single-source shortest-paths problem on a directed graph by exploiting the optimal substructure of shortest paths via dynamic programming. After the k-th iteration, every distance value in the array is already the shortest possible path from the source that uses at most k edges.

Each full pass over every edge checks whether there is a better way to reach any node by coming through one additional edge. Because the previous pass already had the best answers using up to k-1 edges, this new pass simply improves the answer to the best version that now allows one more edge.

A simple path in a graph can never use more than n-1 edges; if it did, it would have to visit the same node twice and therefore contain a cycle. That means after exactly n-1 complete passes, the array already holds the true shortest paths from the source to every reachable node, provided there are no negative cycles.

One final extra pass is then performed. If any distance can still be made smaller, it means there must be a negative cycle reachable from the source, because otherwise the distances would already be optimal and no further improvement would be possible. This extra check is what gives Bellman-Ford its ability to detect negative cycles, something Dijkstra cannot do.

Floyd-Warshall - shortest path

Floyd-Warshall starts with a table that only knows the direct edges between every pair of nodes (infinity for no connection). Then it goes through every possible intermediate node, one by one, and for every possible pair of start and end nodes it updates the table if the path through there becomes shorter.

Here is the implementation:

int[][] AllPairsShortestPath(int n, int[][] edges)
{
    const int halfMax = int.MaxValue / 2;
    var dist = new int[n][];
    for (var i = 0; i < n; i++)
    {
        dist[i] = new int[n];
        Array.Fill(dist[i], halfMax);
        dist[i][i] = 0;
    }

    foreach (var e in edges)
    {
        int u = e[0], v = e[1], w = e[2];
        dist[u][v] = Math.Min(dist[u][v], w);
    }

    for (var k = 0; k < n; k++)
        for (var i = 0; i < n; i++)
            for (var j = 0; j < n; j++)
                if (dist[i][k] != halfMax && dist[k][j] != halfMax)
                    dist[i][j] = Math.Min(dist[i][j], dist[i][k] + dist[k][j]);

    // Negative cycle check
    for (var i = 0; i < n; i++)
        if (dist[i][i] < 0)
            return null;

    return dist;
}

int[][] edges = [
    [0, 1, 5],
    [1, 2, -3],
    [0, 2, 10]
];

var distMatrix = AllPairsShortestPath(3, edges);
Console.WriteLine("0 -> 2: " + distMatrix[0][2]); // 2

Complexity

• Time: O(V³)
• Space: O(V²)

The Floyd-Warshall algorithm solves the all-pairs shortest-paths problem on a directed graph by using dynamic programming to consider every possible intermediate node in a systematic way. It begins with a distance table that contains only the direct edge weights between every pair of nodes. Then, for each potential stopping point in the graph, it checks every possible pair of start and end nodes and updates the recorded distance if routing through that stopping point produces a shorter total path.

Because it exhaustively tries every possible intermediate node exactly once, and does so in an order that builds upon previously discovered shorter routes, the final table contains the true shortest path between every pair of nodes, assuming no negative cycles exist. An extra check at the end looks for any negative values on the diagonal of the table to detect whether a negative cycle is present anywhere in the graph. This triple-loop approach is simple , turning what would be many separate single-source problems into a single computation.

Comparison

Best for

• Bellman-Ford: Single source, sparse graphs
• Floyd-Warshall: All-pairs, dense graphs (V≤400)

Detects negative cycles

• Bellman-Ford: Yes (reachable from source)
• Floyd-Warshall: Yes (anywhere in graph)

Time

• Bellman-Ford: O(V*E)
• Floyd-Warshall: O(V³)

Space

• Bellman-Ford: O(V)
• Floyd-Warshall: O(V²)

Typical problems:

• Bellman-Ford: Cheapest Flights variants, arbitrage
• Floyd-Warshall: City with smallest number of neighbors within distance., Evaluate division (variants), transitive closure

Code simplicity

• Bellman-Ford: Medium (edge list)
• Floyd-Warshall: Very simple (matrix)

Notes

• Dijkstra is faster when no negatives
• For Bellman-Ford, early termination after no updates in a pass is a nice optimization (still O(V*E) worst case).
• Floyd-Warshall is perfect when V ≤ 400; beyond that you usually need Johnson’s algorithm (Bellman-Ford + Dijkstra).
• Negative cycle detection: Bellman-Ford only detects cycles reachable from the source; Floyd-Warshall catches any cycle in the graph.
• Edge cases: self-loops, disconnected components, negative self-loops (instant cycle).

Conclusion

Bellman-Ford and Floyd-Warshall together solve the entire family of shortest-path problems that Dijkstra cannot touch: any graph with negative edge weights, negative cycle detection, and all-pairs shortest paths.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I am going to talk about data structures that help repeatedly query aggregates (sum, min, max, etc.) over ranges of an array and perform updates at the same time.

Segment Trees and Fenwick Trees (also called Binary Indexed Trees or BIT) both solve this in O(log n) per operation, turning impossible brute-force solutions into efficient ones.

When to use them

Use these when the problem has:

• Frequent range queries (sum/min/max/count of elements in [L, R])
• Frequent point updates (change value at index i)
• Array size n ≈ 10⁵–10⁶ and query count q ≈ 10⁵–10⁶

Classic scenarios:

• Mutable range sum queries
• Range minimum queries with updates
• Counting inversions or coordinate compression helpers
• Dynamic frequency queries

A segment tree is more flexible (supports range updates via lazy propagation, any associative operation like gcd/max).  

A Fenwick tree is simpler and lighter on memory, ideal for when you only need prefix sums (and derive range sums via prefix[R] - prefix[L-1]).

Segment Tree - Range sum query (mutable)

A Segment Tree is a full binary tree where:

• Each node represents a range (segment) of the array
• Leaf nodes hold individual array elements
• Internal nodes hold the aggregate (sum/min/max) of their children
• Built in O(n) space (typically 4n array size) and O(n) time

Operations:

• Build: O(n)
• Update (point): O(log n)
• Query (range): O(log n)

Classic problem: Range Sum Query - Mutable

Problem statement: Given an integer array nums, handle multiple queries of the following types:

• Update the value of an element in nums.
• Calculate the sum of the elements of nums between indices left and right inclusive, where left <= right.

int[] nums = [1, 3, 5];
var st = new SegmentTree(nums);
Console.WriteLine(st.Query(0, 2)); // 9
st.Update(1, 2);
Console.WriteLine(st.Query(0, 2)); // 8

public class SegmentTree
{
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums)
    {
        n = nums.Length;
        tree = new int[4 * n];
        Build(1, 0, n - 1, nums);
    }

    private void Build(int node, int start, int end, int[] nums)
    {
        if (start == end)
        {
            tree[node] = nums[start];
            return;
        }
        var mid = start + (end - start) / 2;
        Build(2 * node, start, mid, nums);
        Build(2 * node + 1, mid + 1, end, nums);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public void Update(int index, int val)
    {
        UpdateHelper(1, 0, n - 1, index, val);
    }

    private void UpdateHelper(int node, int start, int end, int idx, int val)
    {
        if (start == end)
        {
            tree[node] = val;
            return;
        }
        var mid = start + (end - start) / 2;
        if (idx <= mid)
            UpdateHelper(2 * node, start, mid, idx, val);
        else
            UpdateHelper(2 * node + 1, mid + 1, end, idx, val);

        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public int Query(int left, int right)
    {
        return QueryHelper(1, 0, n - 1, left, right);
    }

    private int QueryHelper(int node, int start, int end, int l, int r)
    {
        if (r < start || end < l) return 0;          // outside
        if (l <= start && end <= r) return tree[node]; // fully inside

        var mid = start + (end - start) / 2;
        var leftSum = QueryHelper(2 * node, start, mid, l, r);
        var rightSum = QueryHelper(2 * node + 1, mid + 1, end, l, r);
        return leftSum + rightSum;
    }
}

Complexity:

• Build: O(n)
• Update & Query: O(log n)
• Space: O(4n) ≈ O(n)

Fenwick Tree - Range sum query

A Fenwick Tree is an array-based structure that uses bit manipulation to simulate tree-like prefix computations. It only needs O(n) space and is easier to code for sum-based problems.

Key operations:

• update(idx, delta) - add delta to position idx
• prefixSum(idx) - sum from 1 to idx
  • Range sum [L,R] = prefix(R) - prefix(L-1)

Note: Fenwick Trees are 1-indexed in practice.

Here is the same usage as above, but using a Fenwick Tree:

int[] nums = [1, 3, 5];
var ft = new FenwickTree(nums);
Console.WriteLine(ft.Query(0, 2)); // 9
ft.Update(1, 2); //1-based
Console.WriteLine(ft.Query(0, 2)); // 8

public class FenwickTree
{
    private int[] bit;
    private int[] values; // store original values for set-style updates
    private int n;

    public FenwickTree(int[] nums)
    {
        n = nums.Length;
        values = new int[n];
        bit = new int[n + 2]; // 1-based + extra
        for (var i = 0; i < n; i++)
        {
            values[i] = nums[i];
            Add(i + 1, nums[i]);
        }
    }

    private void Add(int idx, int delta)
    {
        while (idx <= n)
        {
            bit[idx] += delta;
            idx += idx & -idx; // lowest set bit
        }
    }

    public void Update(int index, int val)
    {
        var delta = val - values[index]; // compute delta for set
        values[index] = val;
        Add(index + 1, delta);
    }

    private int PrefixSum(int idx)
    {
        var sum = 0;
        while (idx > 0)
        {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    }

    public int Query(int left, int right)
    {
        return PrefixSum(right + 1) - PrefixSum(left);
    }
}

Complexity:

• Update & Prefix Query: O(log n)
• Range Query: O(log n)
• Space: O(n)

Comparison

Space:

• Segment:O(4n)
• Fenwick: O(n)

Build time:

• Segment:O(n)
• Fenwick: O(n log n)

Update

• Segment:O(log n)
• Fenwick: O(log n)

Range Query

• Segment:O(log n)
• Fenwick: O(log n) (via two prefixes)

Flexibility

• Segment:"High: min/max/sum/gcd, lazy range updates"
• Fenwick: Mostly sums (or invertible ops)

Code length / ease

• Segment:"Longer, recursive"
• Fenwick: "Shorter, iterative, bit magic"

Best for

• Segment:"General aggregates, lazy propagation"
• Fenwick: Pure point update + range sum problems

Conclusion

Start with Fenwick if the problem is pure range sum + point updates (faster to code, less error-prone). Switch to Segment Tree if you need min/max, range updates, or non-invertible operations.

Edge cases: index 0/1 confusion, negative values/deltas, empty ranges.

For very tight memory, Fenwick wins.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Two classic algorithms solve dealing with lots of strings elegantly: the Trie (prefix tree) for multiple prefix-based lookups, and KMP (Knuth-Morris-Pratt) for fast single-pattern searching in text. Today I am going to cover them both.

The Trie - Find the index of first occurrence (Prefix tree)

In computer science, a trie, also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store their associated key. Instead, each node's position within the trie determines its associated key, with the connections between nodes defined by individual characters rather than the entire key.

So if a trie was an actual tree, then each branch would have a letter stamped on it. To find a "cat" you go on the "c" branch, then follow on the "a" subbranch and then on the "t" subbranch of "a". The computer science cat will be lying on that very branch - not to be confused with the spherical cow, that's another animal.

When to use

• Insert many words and frequently check if a word exists
• Check if any word starts with a given prefix (autocomplete!)
• Search for words with wildcards or collect all words with a common prefix

Typical problems: dictionary implementations, word search on boards, replace words in sentences.

The point of a try is that sharing prefixes saves space and makes prefix queries very fast.

All operations have O(L) complexity, where L = word length:

• Insert
• Search (exact word)
• StartsWith (prefix exists)

Here is an implementation of a trie:

var trie = new Trie();
trie.Insert("apple");
Console.WriteLine(trie.Search("apple"));     // true
Console.WriteLine(trie.Search("app"));       // false
Console.WriteLine(trie.StartsWith("app"));   // true
trie.Insert("app");
Console.WriteLine(trie.Search("app"));       // true

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = [];
    public bool IsEndOfWord { get; set; }
}

public class Trie
{
    private readonly TrieNode root = new();

    public Trie() { }

    public void Insert(string word)
    {
        var node = root;
        foreach (var c in word)
        {
            if (!node.Children.TryGetValue(c, out var child))
            {
                child = new TrieNode();
                node.Children[c] = child;
            }
            node = child;
        }
        node.IsEndOfWord = true;
    }

    public bool Search(string word)
    {
        var node = GetNode(word);
        return node != null && node.IsEndOfWord;
    }

    public bool StartsWith(string prefix)
    {
        return GetNode(prefix) != null;
    }

    private TrieNode GetNode(string s)
    {
        var node = root;
        foreach (var c in s)
        {
            if (!node.Children.TryGetValue(c, out node))
                return null;
        }
        return node;
    }
}

The trie stands as one of the most elegant data structures for associative retrieval over strings. Independently conceived in the late 1950s, it was first formally described by René de la Briandais in 1959 as a way to compress lexicographic dictionaries, but the term "trie" itself - deliberately extracted from the middle syllable of "retrieval" - was coined by Edward Fredkin in his influential 1960 paper "Trie Memory" published in Communications of the ACM. Fredkin presented it as an alternative to unordered lists, ordered lists, or simple pigeonhole hashing for fast prefix-based lookup, insertion, and membership testing in large sets of variable-length keys.

Mathematically, a trie can be viewed as a rooted, ordered tree that realizes a deterministic finite automaton (DFA) whose states correspond to prefixes of the stored strings. Each edge is labeled with a single symbol from a finite alphabet Σ (of size typically |Σ| = 26 for English lowercase, 256 for bytes, etc.), and the path from the root to any node spells a unique prefix. A special end-of-word flag (or terminal marker) distinguishes nodes that complete valid keys. The height of any path equals the length of its corresponding string, so the time complexity for insertion, exact search, and prefix search is strictly O(L), where L is the length of the key, independent of the total number of strings N stored in the structure (unlike balanced binary search trees, whose operations are O(log N + L)). This prefix-independent bound arises because the trie performs exactly one transition per character, with no backtracking or comparison of entire keys.

Space complexity, however, reveals a classic time–space tradeoff. In the worst case (no shared prefixes), a trie requires Θ(∑ L_i) nodes and up to Θ(|Σ| × number of nodes) pointers, which can be far larger than a simple list or hash table. Yet in practice, for natural-language vocabularies or DNA sequences with significant prefix overlap, the compression is dramatic: the number of nodes often grows sublinearly with N, approaching a value proportional to the total number of distinct characters across all strings. Variants such as compressed tries (or Patricia tries / radix trees) further mitigate space by merging chains of unary nodes, achieving tighter bounds in many applications. Modern analyses (e.g., of hybrid or burst tries) frequently model expected node count and access cost using probabilistic methods over random string sets, confirming the trie's asymptotic superiority for prefix-heavy workloads despite its memory footprint.

Knuth-Morris-Pratt - Find the index of first occurrence (strStr)

KMP avoids unnecessary backtracking by precomputing the Longest Proper Prefix which is also Suffix (LPS / pi array) for the pattern.

Core steps:

• Build LPS array for the pattern (what is the longest prefix that is also a suffix at each position)
• Use the LPS to skip characters when mismatch happens - never backtrack in the text

When to use

• Find if/where a pattern appears in a long text (especially if you do it repeatedly)
• Avoid the O(n*m) worst-case of naive string search
• Typical problems: implement strStr() / find substring index, repeated string matching,

Yes, you in the back! "But Siderite, isn't Boyer-Moore (with Galil rule) much better than Knuth-Morris-Pratt? Why are we even talking about this?"

That is an excellent question. The answer is that KMP is easier to implement under pressure and comprehend in a teaching context. Here are more reasons for KMP:

• guaranteed linear time O(n + m)
• boils down to the concept of LPS / failure / prefix table, which is a single array computed in O(m) and used in a clean two-pointer sliding window
  • it teaches prefix/suffix overlap, failure transitions, and amortized analysis in a compact way.
• classic problems like "Implement strStr()", repeated substring patterns, or finding the first occurrence often map cleanly to KMP.
• KMP (1977) is taught in almost every undergraduate algorithms textbook (CLRS dedicates space to it), while Boyer-Moore (1977, but refined later) is often presented as an "advanced" or "practical optimization" follow-up.

And speaking of strStr, let's see an implementation:

int StrStr(string haystack, string needle)
{
    if (needle.Length == 0) return 0;
    if (haystack.Length < needle.Length) return -1;

    var lps = ComputeLPS(needle);

    var i = 0; // index in haystack
    var j = 0; // index in needle

    while (i < haystack.Length)
    {
        if (haystack[i] == needle[j])
        {
            i++;
            j++;
        }

        if (j == needle.Length)
            return i - j; // found at i - j

        else if (i < haystack.Length && haystack[i] != needle[j])
        {
            if (j != 0)
                j = lps[j - 1]; // smart skip
            else
                i++;
        }
    }
    return -1;
}

int[] ComputeLPS(string pattern)
{
    var lps = new int[pattern.Length];
    var len = 0; // length of previous longest prefix suffix
    var i = 1;

    while (i < pattern.Length)
    {
        if (pattern[i] == pattern[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
                len = lps[len - 1];
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

var haystack = "This is a Knuth-Morris-Pratt algorithm implementation";
Console.WriteLine(StrStr(haystack, "implementation")); //39

Complexity:

• Building LPS: O(m)
• Searching: O(n)
• Total: O(n + m)

KMP is useful for repeated searches on the same pattern (build LPS once), or very long texts with many partial matches. If the problem has multiple patterns, consider Aho-Corasick (Trie + KMP ideas combined), but that's more of a practical real life problem than an interview one, so who cares, right?

The LPS (which stands for Longest Prefix Suffix) is a list created just from the pattern string before any searching starts. For each position in the pattern, the list records how long the beginning part of the pattern matches the ending part ending at that position (using the longest such match that is not the whole string up to there). When the search process finds a mismatch between pattern and text, instead of starting over from the beginning of the pattern, the algorithm uses the LPS value to skip ahead and resume checking from a later spot in the pattern.

In the example above, the LPS is just an array of zeroes, all except for the second 'i' in 'implementation' where the value is 1. So when a character mismatches that 'i', you start from index 1 and length 1, because 'implementation' starts with an 'i'.

You may be interested to know that the IndexOf implementation in .NET is neither KMP or BM, instead it's an optimized ordinal or culture-aware search that is implemented in native code (inside the CLR and CoreCLR runtime). So if you want either of these for specific cases, you will have to implement them yourself anyway. Or use a NuGet...

Conclusion

If you're into algorithms, the ones on strings are beautiful! People have been thinking about these for almost a century and there are some really cool implementations and ideas. I can't even begin to cover such a vast field.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I will be covering Binary Search, used to efficiently search sorted arrays or otherwise monotonic spaces.

When to use Binary Search

You already know classic binary search on a sorted array. But the real power shows up when the array is not obviously sorted, or when there is no array at all - only a monotonic (always increasing or always decreasing) decision space.

Classic signs:

• The array is sorted but rotated / shifted
• You need to find the minimum / maximum in a rotated sorted array
• You're searching for the boundary between two behaviors (first true / last false)
• You want the minimal / maximal value that satisfies some condition
• The answer lies in a large but monotonic range (0 to 10⁹, days, capacity, speed, etc.)
• Linear search would be too slow, but the property lets you discard half the search space every step

One-sentence rule: Whenever you can define a monotonic predicate "is it possible / good enough at value X?" and the answer changes only once (from false to true or viceversa), binary search on the answer range will usually give you O(log N) time instead of O(N).

Classic Binary Search Template

I know that C# already has a method called Array.BinarySearch , but the problems you're going to get usually have a little quirk that forces you to implement it manually, like the array is sorted, then rotated. But it's really easy.

Use this pattern - it avoids off-by-one errors and integer overflow:

int BinarySearchLeftMost(int[] arr, int target)
{
    int left = 0;
    // note: one past the end
    int right = arr.Length;           

    while (left < right)
    {
        // same as (left+right)/2, but avoiding overflows
        int mid = left + (right - left) / 2;

        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }

    return left;   // insertion point or first >= target
}

Just remember:

• left < right loop
• mid = left + (right - left)/2 prevents overflow
• When condition is true, shrink right
• When false, shrink left
• At the end left is usually the boundary you want
• You may choose to use a simpler search algorithm when the size of the search is small enough

Example – Search in Rotated Sorted Array

Problem statement: You are given a sorted array that has been rotated an unknown number of times. Find the index of target or return -1.

Example: nums = [4,5,6,7,0,1,2], target = 0, expected output: 4

Here is the solution:

int Search(int[] nums, int target)
{
    var left = 0;
    var right = nums.Length - 1;

    while (left <= right)
    {
        var mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        // Left half is sorted
        if (nums[left] <= nums[mid])
        {
            if (nums[left] <= target && target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        // Right half is sorted
        else
        {
            if (nums[mid] < target && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }

    return -1;
}

int[] nums = [4, 5, 6, 7, 0, 1, 2];
var target = 0;
Console.WriteLine(Search(nums, target)); //4

It's silly, really. You just have an extra if/then block to figure out which of the halves is the unrotated one. Other than that it's a classic binary search.

Complexity goes from O(n) (the naive linear scan) to O(log n) for the binary search.

Example - Capacity to ship packages within D days

The problem is called Binary Search on Answer (Capacity To Ship Packages Within D Days).

Problem statement: Given weights of packages and D days, find the minimal ship capacity needed to ship all packages in D days.

Solution:

int ShipWithinDays(int[] weights, int days)
{
    // at least the heaviest package
    var left = weights.Max();
    // at most everything in one day
    var right = weights.Sum();

    while (left < right)
    {
        var mid = left + (right - left) / 2;

        if (CanShip(weights, mid, days))
        {
            // try smaller capacity
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }

    return left;
}

bool CanShip(int[] weights, int capacity, int days)
{
    var current = 0;
    var neededDays = 1;

    foreach (var w in weights)
    {
        var newCurrent = current + w;
        if (newCurrent > capacity)
        {
            neededDays++;
            current = w;
            if (neededDays > days) return false;
        }
        else
        {
            current = newCurrent;
        }
    }
    return true;
}
Console.WriteLine(ShipWithinDays([1, 3, 45, 6, 4, 32, 24, 5, 6, 32], 4)); //49

Step-by-step checklist to recognize monotonicity in the example above:

• What are we actually searching for?
  • We are searching for the smallest possible ship capacity (let's call it C) such that it is still possible to ship all packages in ≤ days days.
• Define the clear yes/no question (the predicate): Is it possible to ship all packages using capacity ≤ C within ≤ days days?
  • We call this predicate CanShip(C, weights, days)
  • It returns true or false
• Ask the crucial monotonicity question: If CanShip(C) is true, what happens when we increase C to C+1, C+2, etc.?
  • Answer: If you could already ship everything with capacity C, then you can definitely ship everything with any larger capacity (C+1, C+10, C+1000, ...).
  • In other words: larger capacity can only make the problem easier or keep it equally easy - never harder.
  • Formally: If CanShip(C) == true, then  CanShip(C') == true for all C' > C
  • The opposite is also true: If CanShip(C) == false, then CanShip(C') == false for all C' < C
• Conclusion from the above:
  • The predicate CanShip(C) is monotonic non-decreasing with respect to C.
  • There exists some threshold value C_min such that:
    • for all C < C_min, meaning CanShip(C) = false
    • for all C ≥ C_min, meaning CanShip(C) = true
  • This is the classic "staircase" / "boundary" shape that binary search loves.

Visual intuition

Capacity: 

          false  false  false   true   true   true   true

                       ↑

                 the minimal valid capacity we want

Whenever increasing the search variable (capacity, speed, height, number of bananas per hour, pages per day, etc.) can only help (never hurt) the feasibility, then the feasibility function is monotonic, so binary search applies.

Ask yourself these two questions:

• "If I make the constraint looser (bigger capacity, more days, higher speed limit, etc.), does the answer become easier or stay the same?
• "If I make the constraint stricter (smaller capacity, fewer days, lower speed, etc.), does the answer become harder or stay the same?

If both answers are yes the feasibility is monotonic, therefore binary search on the answer is applicable.

Counter example: "find a number in an unsorted array" - increasing the search range doesn't consistently help or hurt. One must use linear scan or hash set, not binary search.

So in short: you know Example 2 is monotonic because making the ship capacity larger can only help (never hurt) the ability to finish in D days and that consistent direction creates the perfect binary-search-friendly boundary.

Example - Consistent hashing

Advanced Application: Consistent Hashing. Binary search shines on any sorted structure, not just arrays. One of the most elegant real-world uses is consistent hashing, the algorithm that powers load balancers, distributed caches, and databases like Cassandra and DynamoDB.

Use it when you are distributing keys (users, requests, cache entries) across a changing set of servers. Traditional hashing (key % numServers) forces every key to be remapped whenever a server is added or removed. Consistent hashing limits the damage to roughly 1/N of the keys.

Imagine a clock (the "ring") with numbers from -∞ to +∞.  

• Each server gets many "virtual nodes" placed on the ring (via hash(server + replica)).  
• The virtual nodes are kept sorted.  
• To find where a key goes: hash the key (binary search for the first virtual node clockwise - the next larger hash, or wrap to the beginning).  
• When a server is added/removed, only the keys between its old and new neighbors move.

We implement the ring with a List<long> (kept sorted) and BinarySearch, exactly the technique covered in this post.

Here is the solution:

var chr = new ConsistentHashRing();

chr.AddServer("server1");
chr.AddServer("server2");
chr.AddServer("server3");

Console.WriteLine("Before removal:");
Console.WriteLine($"key1   -> {chr.GetServerForKey("key1")}");
Console.WriteLine($"user42 -> {chr.GetServerForKey("user42")}");
Console.WriteLine($"cacheX -> {chr.GetServerForKey("cacheX")}");

chr.RemoveServer("server2");   // only ~1/3 of keys will move

Console.WriteLine("\nAfter removing server2:");
Console.WriteLine($"key1   -> {chr.GetServerForKey("key1")}");
Console.WriteLine($"user42 -> {chr.GetServerForKey("user42")}");
Console.WriteLine($"cacheX -> {chr.GetServerForKey("cacheX")}");

public class ConsistentHashRing
{
    private readonly List<long> ring = [];
    private readonly Dictionary<long, string> hashToServer = [];
    private readonly Dictionary<string, List<long>> serverToHashes = [];
    private const int VirtualNodesPerServer = 100; // increase for better distribution

    private long Hash(string key)
    {
        return Math.Abs(key.GetHashCode());
    }

    public void AddServer(string server)
    {
        if (serverToHashes.ContainsKey(server)) return;

        var hashes = new List<long>(VirtualNodesPerServer);
        for (int i = 0; i < VirtualNodesPerServer; i++)
        {
            long hash = Hash(server + "#" + i);

            int idx = ring.BinarySearch(hash);
            if (idx < 0) idx = ~idx;

            ring.Insert(idx, hash);
            hashToServer[hash] = server;
            hashes.Add(hash);
        }
        serverToHashes[server] = hashes;
    }

    public void RemoveServer(string server)
    {
        if (!serverToHashes.TryGetValue(server, out var hashes)) return;

        foreach (var hash in hashes)
        {
            int idx = ring.BinarySearch(hash);
            if (idx >= 0)
            {
                ring.RemoveAt(idx);
                hashToServer.Remove(hash);
            }
        }
        serverToHashes.Remove(server);
    }

    public string GetServerForKey(string key)
    {
        if (ring.Count == 0) return null;

        long hash = Hash(key);

        int idx = ring.BinarySearch(hash);
        if (idx < 0) idx = ~idx;
        if (idx == ring.Count) idx = 0; // wrap around the ring

        return hashToServer[ring[idx]];
    }
}

GetServerForKey does exactly one BinarySearch on the sorted list of virtual node hashes.

• If the key hash lands exactly on a node then use it.
• Otherwise ~idx gives the insertion point, i.e. the next server clockwise.
• The wrap-around (if idx == Count) makes the ring circular.

That's O(log (N * replicas)) lookup, blazing fast even with thousands of virtual nodes.

Complexity:

• Lookup (GetServerForKey): O(log (N * replicas)) thanks to BinarySearch
• Add/Remove server: O(replicas * log (N * replicas)) (insert/delete in the list)

In practice N is small (10–1000 servers) and add/remove is rare, so it’s perfect.

Real-world notes:

• Cassandra, DynamoDB, Redis Cluster, and most CDNs use this exact pattern.
• In production replace the simple Hash with MD5, MurmurHash3, or SHA-1.
• Virtual nodes (the 100 replicas) make distribution even - without them some servers would get way more keys than others.

Conclusion

Advanced binary search is one of the most powerful patterns in coding interviews. Once you see a monotonic property or decision boundary, you can often turn a brute-force O(n) or worse solution into O(log n) or O(n log n) with very little code.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I cover Union-Find (Disjoint Set Union).

When to use Union-Find

Determine problems that can be solved with Union-Find by these signs:

• You need to repeatedly merge groups (union) and ask "are these two items in the same group?" (find).
• You're counting connected components in a graph (number of provinces, number of islands alternative).
• You're detecting cycles in an undirected graph or finding the redundant edge.
• You're building a Minimum Spanning Tree (Kruskal's algorithm).
• The graph is given as edges or adjacency matrix and n ≤ 10⁴ (Union-Find is blazingly fast here).

One-sentence rule: If you repeatedly merge sets and check connectivity, Union-Find with path compression + union-by-rank gives you practically O(1) per operation (inverse Ackermann function α(n) - it never exceeds 5 for any practical n).

The data structure (reusable template)

We are going to use a class called UnionFind for all of the examples. It looks like this:

public class UnionFind
{
    private int[] parent;
    private int[] rank;
    public int Components { get; private set; }

    public UnionFind(int n)
    {
        parent = Enumerable.Range(0, n).ToArray();
        rank = new int[n];
        Components = n;
    }

    public int Find(int x)
    {
        var parentOfX = parent[x];
        if (parentOfX != x)
        {
            // path compression
            parentOfX = Find(parentOfX);
            parent[x] = parentOfX;
        }
        return parentOfX;
    }

    public bool Union(int x, int y)
    {
        var rootX = Find(x);
        var rootY = Find(y);

        // already same set -> cycle!
        if (rootX == rootY) return false;

        // Union by rank
        switch (rank[rootX].CompareTo(rank[rootY]))
        {
            case 1:
                parent[rootY] = rootX;
                break;
            case -1:
                parent[rootX] = rootY;
                break;
            case 0:
                parent[rootY] = rootX;
                rank[rootX]++;
                break;
        }

        Components--;
        return true;
    }
}

Example - Number of provinces

Let's check out the problem called Number of Provinces.

Problem statement: There are n cities. Some are connected by roads. A province is a group of directly or indirectly connected cities. Return the total number of provinces.

The input is a n*n matrix containing 1 (connected) or 0 (not connected).

Here is the code:

int FindCircleNum(int[][] isConnected)
{
    var n = isConnected.Length;
    var uf = new UnionFind(n);

    for (var i = 0; i < n; i++)
    {
        // upper triangle only
        for (var j = i + 1; j < n; j++)
        {
            if (isConnected[i][j] == 1)
            {
                uf.Union(i, j);
            }
        }
    }

    return uf.Components;
}

var matrix = new int[][]
{
    [1,1,0],
    [1,1,0],
    [0,0,1]
};
Console.WriteLine(FindCircleNum(matrix)); // 2

A possible naive approach: Run DFS or BFS from every unvisited city and count how many times you start a new traversal.

• Time: still O(n²) because you may visit every edge/cell.
• Problems: lots of extra code, recursion depth can exceed 10⁴ leading to stack overflows, slower constants because of repeated visits and visited-array management.

Union-Find approach: We walk the matrix once, merging groups on the fly. No recursion, almost no extra memory, and each merge/check is practically O(1).

Complexity: O(n² α(n)) where α(n) is the inverse Ackermann function (effectively constant). In practice this is faster than DFS/BFS and uses less memory.

Theory - why Union-Find is really fast

Imagine you have a bunch of people and you keep merging friend groups. A super-naive version would just keep a list for each group - merging two lists takes forever and checking "are these two friends?" also takes forever.

Without optimizations, Union-Find can degenerate into a long chain (like a linked list). In the worst case every Find would walk all the way to the root - O(n) time - and your whole algorithm would become O(n²). That's what the naive approaches usually suffer from. Union-Find fixes this with two tricks that you learn once and then use forever:

• Path compression (the "flattening" trick): Every time you call Find(x), you make every node you touched point straight to the root. The next time anyone asks about those nodes, the answer is just one step.
• Union by rank (the "keep trees short" trick): Instead of randomly attaching one tree under another, we always attach the shorter tree under the taller one (using the rank array). This guarantees the tree height stays tiny (at most log n in the worst case).

Together these two techniques give an amortized time per operation of O(α(n)), where α(n) is the inverse Ackermann function.

Don't worry about the math: α(n) grows so slowly that for any number you will ever meet in programming (even bigger than the number of atoms in the universe), α(n) ≤ 5. In practice it feels like constant time. That's why Union-Find turns problems that feel O(n²) into something that runs in the blink of an eye.

Example - Redundant connection

This problem is called Redundant Connection.

Problem statement: Given a list of edges that form a tree plus exactly one extra edge, return the extra edge that creates a cycle (the last one in the input if multiple).

The input is an array of n * 2 representing the edges between nodes.

A possible naive approach: For every new edge, temporarily add it and run a full DFS/BFS to see if u and v are already connected.

• Time: O(n) per edge meaning O(n²) total.
• Problems: slow, lots of code, and you still have to clean up the graph after each test.

Union-Find approach: We process each edge in one pass. Every union/find is amortized O(α(n)). As soon as we try to union two nodes that already have the same root, we found the cycle - no extra traversal needed.

Complexity: O(n α(n)) ≈ O(n). Dramatically faster and cleaner than any graph-traversal alternative.

using Algorithms;

int[] FindRedundantConnection(int[][] edges)
{
    // n edges for n nodes (labeled 1 to n)
    var n = edges.Length;
    var uf = new UnionFind(n + 1);

    foreach (var edge in edges)
    {
        var (u, v) = (edge[0], edge[1]);
        if (!uf.Union(u, v))
        {
            // this edge created the cycle
            return edge;
        }
    }

    return []; // never reached per problem constraints
}

var edges = new int[][]
{
    [1,2], [1,3], [2,3]
};
var result = FindRedundantConnection(edges);
Console.WriteLine($"[{result[0]},{result[1]}]"); // [2,3]

Example - Minimum spanning tree (Kruskal)

Problem statement: you are given n cities a list of possible connections between them. Each connection has a cost. Return the minimum total cost to connect all cities into one single network (i.e. a Minimum Spanning Tree). If it is impossible to connect all cities, return -1.

This is exactly Kruskal’s algorithm, the one we already mentioned in the "When to use Union-Find" section.

Input:

• int n - number of cities
• int[][] connections - each row is [city1, city2, cost]

Here is the complete solution (re-using the exact UnionFind class from the top of this post):

using Algorithms;

int MinimumCost(int n, int[][] connections)
{
    // Sort edges by increasing cost (greedy choice)
    var sorted = connections.OrderBy(e => e[2]).ToArray();

    var uf = new UnionFind(n + 1); // cities are 1..n
    var totalCost = 0;
    var edgesUsed = 0;

    foreach (var edge in sorted)
    {
        var u = edge[0];
        var v = edge[1];
        var cost = edge[2];

        if (uf.Union(u, v))
        {
            totalCost += cost;
            edgesUsed++;
            if (edgesUsed == n - 1) break; // MST is complete
        }
    }

    // We only need n-1 edges for n cities. If we found them → connected!
    return edgesUsed == n - 1 ? totalCost : -1;
}

var connections = new int[][]
{
    [1, 2, 3],
    [1, 3, 5],
    [2, 3, 1]
};
Console.WriteLine(MinimumCost(3, connections)); // 4  (edges 2-3 cost 1 + 1-2 cost 3)

A possible naive approach is to build a full graph and run Prim’s algorithm (priority queue + visited set).

• Time: O(E log V) with a binary heap.
• Problems: more code, needs adjacency list + heap, and you still have to handle disconnected graphs manually.

The Union-Find (Kruskal) approach:

• Sort all possible edges by cost (O(E log E)).
• Greedily add the cheapest edge that does not create a cycle (just call Union — if it returns false, skip it).
• Stop when we have added n-1 edges or when Components == 1.

No graph traversal, no heap, no recursion — just the tiny UnionFind template we already have.

Complexity:

• Time: O(E log E α(n)) — the sorting dominates, union/find is practically O(1) per operation.
• Space: O(n) for the UnionFind arrays.

In practice this is often faster and simpler than Prim’s for sparse graphs (exactly the case in most interview problems).

Comparison

• Use Kruskal + Union-Find when the graph is given as an edge list (most common in interviews).
• Use Prim + Priority Queue (see the Heaps/Priority Queues post) when you already have an adjacency list or the graph is dense.

Both give the correct Minimum Spanning Tree - Union-Find just wins on simplicity and speed for this pattern.

Conclusion

Union-Find (Disjoint Set Union) is the hidden champion of graph problems: tiny code, good speed, and it turns "connected components" or "cycle detection" into trivial work. Once you internalize this template with path compression and union-by-rank, you'll spot it instantly in interviews and real code.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I cover Heaps and Priority Queues.

When to use Heaps / Priority Queues

   We already saw a heap in action in the Greedy post (Task Scheduler), but today we'll zoom in on the data structure itself and why it's the perfect tool whenever you need the "best" or "worst" item right now without sorting the whole collection.

Recognize the problems that can be solved by heaps / priority queues by the following signs:

• You need repeated access to the current minimum or maximum element while the collection keeps changing (insertions, deletions, updates).
• You only care about the top-k (best/worst) elements, not the full sorted order.
• You have to process tasks, events or nodes in priority order (highest frequency, earliest deadline, smallest value, etc.).
• The data is dynamic - elements arrive over time and you need O(log n) updates.
• Brute force would require sorting the entire set repeatedly (O(n log n) per operation) but you can do much better.
• The problem mentions "k largest/smallest", "merge k sorted", "median finder", "task scheduler with cooldown", "Dijkstra shortest path", etc.

If the collection is static and you need everything sorted, just .Sort() or .OrderBy. Heaps shine when you only ever need the extreme values and you need them fast - O(log n) per insert or extract.

Classic patterns appear in LeetCode/HackerRank: Kth Largest Element, Merge K Sorted Lists, Task Scheduler, Find Median from Data Stream, Top K Frequent Elements, etc.

One-sentence rule: If you need the "best" (or "worst") item right now, repeatedly, while the set changes, and you don't need the full sorted list, use a heap (priority queue).

Example - Kth largest element

The problem is called Kth Largest Element.

Problem statement: Given an integer array nums and an integer k, return the k-th largest element in the array.

Naïve solution: sort the array, complexity O(n log n).

Better solution: keep a min-heap of size exactly k. At the end the root of the heap is the kth largest.

int FindKthLargest(int[] nums, int k)
{
    // Min-heap: smallest of the k largest candidates sits at the top
    var pq = new PriorityQueue<int, int>();

    foreach (var num in nums)
    {
        if (pq.Count < k)
        {
            pq.Enqueue(num, num);           // priority = value (min-heap)
        }
        else if (num > pq.Peek())
        {
            pq.Dequeue();
            pq.Enqueue(num, num);
        }
    }

    return pq.Peek();
}

var nums = new[] { 3, 2, 1, 5, 6, 4 };
Console.WriteLine(FindKthLargest(nums, 2)); // 5

It's basically the classic find min/max loop, but with an interval of k values instead of a single value.

We only ever keep the k largest numbers seen so far. Because it's a min-heap, the smallest among them is always at the root. Any number smaller than that root can be discarded forever - it can never be part of the top-k. At the end we have exactly the k largest elements and the root is the kth.

Works perfectly for streaming data or when k is much smaller than n.

Complexity:

• Time: O(n log k) - each of the n elements costs at most one heap operation
• Space: O(k)

Theory

A (binary) heap is a complete binary tree that satisfies the heap property:

• Max-heap: every parent ≥ children
• Min-heap: every parent ≤ children

Because it's complete, it can be stored in an array with beautiful cache locality (parent at i, children at 2i+1 and 2i+2).

C# gives us PriorityQueue<TElement, TPriority> (available since .NET 6). By default it is a min-heap on the priority value.

QuickSort works like this:

• Pick a pivot.
• Partition the array so everything smaller is on the left, everything larger on the right.
• Recurse on both sides.

QuickSelect does exactly the same partition, but then throws away the side that cannot contain the k-th element and recurses on only one side. That single decision is what drops the average time from O(n log n) to O(n).

Heaps / Priority Queues template

Even though the concept is simple, there is a reusable pattern:

• Decide min-heap or max-heap (C# PriorityQueue is min-heap by default on the priority value).
• Create the queue: new PriorityQueue<TElement, TPriority>() (or with custom comparer).
• Seed the heap with initial elements (often first k or first node of each list).
• While you need the next "best" item:
• Peek() or Dequeue() the top
• If more data exists for that source, Enqueue the next one
• Stop when you have extracted what you need.

Common patterns:

• Same value for element and priority -> PriorityQueue<int, int>
• Max-heap -> use negative priority or a custom IComparer<TPriority>
• Complex objects -> store a tuple or a small record as the element and the sorting key as priority.

In C# it looks like this:

var comparer = Comparer<TPriority>.Create(/* custom logic */);
var pq = new PriorityQueue<TElement, TPriority>(comparer);

// Enqueue / Dequeue / Peek are all O(log n)
// Count and Peek are O(1)

Common Pitfalls & Trade-Offs:

• Choosing min-heap vs max-heap - double-check with a small example.
• Custom comparers on complex types - make sure they are consistent (same as IComparable if you mix approaches).
• Using a heap when you actually need the full sorted list later - sometimes two heaps (or a sorted set) are cheaper.
• Memory pressure when k is huge - O(k) space is fine for k ≤ n/2, otherwise a QuickSelect can be better (see the theory chapter)
• Ties - if two items have the same priority, the heap doesn't guarantee FIFO order unless you add an extra index to the priority.

Example - Merge k sorted lists

A more impressive use case is Merge K Sorted Lists.

Problem statement: You are given an array of k linked lists, each sorted in ascending order. Merge them into one sorted linked list and return it.

Example: lists = [ [1,4,5], [1,3,4], [2,6] ]

Output: [ 1, 1, 2, 3, 4, 4, 5, 6 ]

Naive way (merge two at a time repeatedly) is painfully slow.

Heap way:

ListNode MergeKLists(ListNode[] lists)
{
    if (lists == null || lists.Length == 0) return null;

    // Min-heap: priority = node.Value
    var pq = new PriorityQueue<ListNode, int>();

    // Seed with the head of every non-empty list
    for (int i = 0; i < lists.Length; i++)
    {
        if (lists[i] != null)
        {
            pq.Enqueue(lists[i], lists[i].Value);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (pq.Count > 0)
    {
        ListNode node = pq.Dequeue();
        tail.Next = node;
        tail = tail.Next;

        if (node.Next != null)
        {
            pq.Enqueue(node.Next, node.Next.Value);
        }
    }

    return dummy.Next;
}

ListNode[] lists = [
    new [] {1, 4, 5},
    new [] {1, 3, 4},
    new [] {2, 6},
];

Console.WriteLine(MergeKLists(lists));

The ListNode class is this:

using System.Text;

public class ListNode(int value)
{
    public int Value { get; set; } = value;
    public ListNode Next { get; set; }

    /// <summary>
    /// Define a linked list from an int array
    /// </summary>
    /// <param name="values"></param>
    public static implicit operator ListNode(int[] values)
    {
        if (values == null || values.Length == 0)
            return null;

        var head = new ListNode(0);
        var current = head;

        foreach(var value in values)
        {
            current.Next = new ListNode(value);
            current = current.Next;
        }

        return head.Next;
    }

    public override string ToString()
    {
        var list = new List<int>();
        var node = this;
        while (node is not null)
        {
            list.Add(node.Value);
            node = node.Next;
        }
        return "[ "+string.Join(", ", list) + "]";
    }
}

This is optimal:

• Every node is enqueued and dequeued exactly once - O(N log k) where N is total nodes
• At any moment the heap holds at most k nodes (one per list)
• Space: O(k)
• Beats the naive O(N * k) or repeated pairwise merging dramatically

More theory

Dijkstra's algorithm computes the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. It works exactly like a "greedy best-first" expansion: keep a min-heap (priority queue) of nodes ordered by their current known distance from the source. Repeatedly extract the node with the smallest distance, then relax (update) all its neighbors. Because we always process the closest unsettled node next, the first time a node is dequeued its distance is guaranteed to be optimal. The heap is what makes the repeated "extract the current best candidate" operation blazingly fast - turning the algorithm into the go-to solution for routing, GPS, network delay, and hundreds of other real-world problems.

Don't hate me. We need this for the next example.

Example - Dijkstra shortest path

Problem name is Dijkstra's Shortest Path.

Problem statement: Given a weighted graph with non-negative edges represented as an adjacency list (List<List<(int node, int weight)>>) and a source node, return the shortest distance from the source to every other node.

Example graph (4 nodes):

// 0 ──4──► 1
// │        ▲
// │        │
// 1        2
// │        │
// ▼        ▼
// 2 ──5──► 3
// (plus 2→1 weight 2 and 1→3 weight 2)
var graph = new List<List<(int node, int weight)>>
{
    new() { (1, 4), (2, 1) },   // from 0
    new() { (3, 2) },           // from 1
    new() { (1, 2), (3, 5) },   // from 2
    new() {}                    // from 3
};
int source = 0;

Expected output: [0, 3, 1, 5]

(0 -> 2 -> 1 costs 1+2=3, better than direct edge 4; 0 -> 2 -> 1 -> 3 costs 5)

int[] Dijkstra(List<List<(int node, int weight)>> graph, int source)
{
    var n = graph.Count;
    var dist = Enumerable.Repeat(int.MaxValue, n).ToArray();
    dist[source] = 0;

    // Min-heap: (current_distance, node)
    var pq = new PriorityQueue<(int distance, int node), int>();

    pq.Enqueue((0, source), 0);

    while (pq.Count > 0)
    {
        var (distance, node) = pq.Dequeue();
        if (distance > dist[node]) continue;   // outdated entry - ignore

        foreach (var (destNode, destDistance) in graph[node])
        {
            var newDistance = dist[node] + destDistance;
            if (newDistance < dist[destNode])
            {
                dist[destNode] = newDistance;
                pq.Enqueue((newDistance, destNode), newDistance);
            }
        }
    }

    return dist;
}

var graph = new List<List<(int node, int weight)>>
{
    new() { (1, 4), (2, 1) },   // from 0
    new() { (3, 2) },           // from 1
    new() { (1, 2), (3, 5) },   // from 2
    new() {}                    // from 3
};

int source = 0;
var distances = Dijkstra(graph, source);
Console.WriteLine(string.Join(", ", distances));   // 0, 3, 1, 5

The priority queue always hands us the next "best" (closest) unsettled node. The check if (d > dist[u]) continue is the classic lazy-deletion trick that handles duplicate entries efficiently. With non-negative weights, the first time we dequeue a node its distance can never be improved later, exactly the same "process the current global best" pattern we saw in Merge K Lists and Kth Largest.

Complexity:

• Time: O((V + E) log V)
• Space: O(V)

Conclusion

Heaps / Priority Queues turn repeated "find the current best" operations from O(n log n) into O(log k) or O(log n) and power everything from task schedulers to Dijkstra's shortest path to median finders. Once you get it, you stop reaching for .Sort() when you only need the extremes.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I cover greedy algorithms. 

When to use Greedy algorithms

Recognize the problems that can be solved by greedy algorithms by the following signs:

• The problem asks for a maximum or minimum value under constraints (e.g., max profit, min jumps, min number of something, max items selected).
• A locally optimal choice at each step leads to a globally optimal solution (greedy choice property).
• Making the best immediate decision never forces you to regret it later (no need to backtrack or reconsider past choices).
• The problem has optimal substructure but greedy avoids full dynamic programming (DP) by using a simple rule or priority.
• Sorting or prioritizing by a specific key (end time, value/weight ratio, farthest reach, density) unlocks the optimal solution.
• Brute force or DP would be too slow (exponential or quadratic), but a greedy rule gives linear or n log n time.

Classic patterns appear: activity selection, interval scheduling, fractional knapsack, coin change (canonical coins), jump game reachability, task scheduling with cooldown.

An algorithm is greedy when it follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

Classic greedy algorithm problems:

• Jump Game I & II
• Task Scheduler
• Fractional Knapsack
• Activity Selection / Non-overlapping Intervals
• Huffman Coding
• Minimum Number of Platforms (train scheduling)

One sentence rule: "If I can always pick the 'best' available option right now according to some clear criterion, and doing so never hurts the final answer, it's probably greedy."

Example - Activity selection

The classic "poster problem" for greedy algorithms is Activity Selection (also known as Interval Scheduling).

Problem statement: You are given n activities with their start time and finish time. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time. Return the maximum number of activities that can be selected.

Example: activities = [[1,4], [3,5], [0,6], [5,7], [3,8], [5,9], [6,10], [8,11], [8,12], [2,14], [12,16]]

Output: 4 (one possible selection: [1,4], [5,7], [8,11], [12,16])

Constraints:

• 1 <= n <= 10⁵
• 0 <= start < finish <= 10⁹

Let's see how a naive solution would look like, using DP and brute force:

var countOps = 0;

// Extremely slow - exponential time
int MaxActivitiesNaive(int[][] activities)
{
    var n = activities.Length;
    var max = 0;

    // Generate all 2^n subsets (impossible for n>20)
    for (var mask = 0; mask < (1 << n); mask++)
    {
        List<int[]> selected = [];
        for (var i = 0; i < n; i++)
        {
            if ((mask & (1 << i)) != 0)
            {
                selected.Add(activities[i]);
            }
        }
        countOps++;
        if (IsNonOverlapping(selected))
        {
            max = Math.Max(max, selected.Count);
        }
    }
    return max;
}

bool IsNonOverlapping(List<int[]> acts)
{
    if (acts.Count <= 1) return true;

    // Sort by start time
    acts.Sort((a, b) => a[0].CompareTo(b[0]));

    // Check consecutive pairs
    for (var i = 1; i < acts.Count; i++)
    {
        var (prevEnd, currStart) = (acts[i - 1][1], acts[i][0]);

        // If previous ends after (or at) current starts -> overlap
        if (prevEnd > currStart)
        {
            return false;
        }
    }

    return true;
}

int[][] activities = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], 
                      [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];
Console.WriteLine(MaxActivitiesNaive(activities));
Console.WriteLine(countOps);

This code will display 4, as expected, and then display 2048, the number of checks for IsNonOverlapping.

Why it fails:

• Time complexity O(2ⁿ * n log n) which is useless for n > 20
• No smart way to prune invalid subsets early

Now let's check the optimal Greedy Solution:

• Sort activities by finish time (earliest ending first).
• Then greedily pick the next activity that starts after the previous one ends.

var countOps = 0;

int MaxActivities(int[][] activities)
{
    if (activities == null || activities.Length == 0) return 0;

    // Sort by finish time - this is the greedy choice
    Array.Sort(activities, (a, b) => a[1].CompareTo(b[1]));
    countOps += (int)Math.Ceiling(activities.Length * Math.Log(activities.Length));

    var count = 1;
    var lastEnd = activities[0][1];  // finish time of first selected

    for (var i = 1; i < activities.Length; i++)
    {
        countOps++;
        // Can take this activity if it starts after last selected ends
        if (activities[i][0] >= lastEnd)
        {
            count++;
            lastEnd = activities[i][1];
        }
    }

    return count;
}

int[][] activities = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], 
                      [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];
Console.WriteLine(MaxActivities(activities));
Console.WriteLine(countOps);

This displays a countOps of 37.

This is optimal because:

• Time: O(n log n) due to sorting + O(n) pass
• Space: O(1) extra (or O(log n) for sort)
• Correctness: Proof relies on "greedy stays ahead" or "exchange argument"
• Earliest finish leaves maximum room for future activities
• Any optimal solution can be transformed into this greedy one without decreasing size

This problem is the "hello world" of greedy algorithms:

• Simple to understand
• Shows why greedy works when many people think dynamic programming (DP) is needed
• Easy to prove correctness in interviews
• Appears in countless variations (meeting rooms, non-overlapping intervals, weighted interval scheduling -> DP)

Theory

OK, you will hate me for this, but I found it an interesting tidbit. And if the interview guy knows what a matroid is, you're either applying for a really good company or you're totally screwed. Anyway...

Greedy algorithms and matroids are very closely related in a precise mathematical way, as matroids provide one of the cleanest and most general explanations for when and why greedy algorithms work. But first we need some quick definitions:

Greedy algorithm: At each step, make the locally optimal choice (pick the best-looking option right now) according to some criterion, hoping it leads to a globally optimal solution.

Matroid: A mathematical structure that generalizes the notion of "independence" (like linear independence in vector spaces or acyclic sets in graphs).

It has two key axioms:

• Hereditary property: If a set is independent, all its subsets are independent.
• Exchange property: If two independent sets A and B exist and |A| < |B|, then there exists an element in B that can be added to A while keeping it independent.

The fundamental theorem (the relationship between them) was developed by Jack Edmonds and others in 1971: A greedy algorithm correctly finds the maximum-weight independent set in a weighted set system if and only if the set system is a matroid.

In other words:

• If the problem can be modeled as finding a maximum-weight independent set in a matroid, then the greedy algorithm (sort by weight descending, add if it keeps independence) is guaranteed to give the optimal solution.
• If greedy works correctly on a problem, then the underlying structure is usually a matroid (or can be reduced to one).

Greedy fails when not a matroid:

• 0/1 Knapsack: Greedy by value/weight ratio can fail - no matroid structure (doesn't satisfy exchange)
• General coin change (non-canonical denominations): Greedy can give suboptimal - not a matroid
• Traveling Salesman Problem: Greedy nearest neighbor fails badly - no matroid

The matroid is the set of rules, not anything in the problem statement, so that might be confusing. Let's simplify that for the five year old mind of a software developer. You have a pile of toys and in that case a matroid is a set of rules that tells you:

• if any handful of toys is considered "good", then any smaller handful is also "good". There is no way you can split a "good" pile of toys and get a "bad" one.
• if any two handfuls are "good", then moving any toy from one to the other also results in two "good" handfuls.

In our example above, the toys were the activities, the good handfuls were sets of non-overlapping activities, therefore the algorithm is proven to give the optimal solution.

Greedy algorithm template

And even if the name indicates something very generic, there is in fact a "template" of greedy algorithms:

1. define the greedy choice criterion - in our case, activity start time. Other examples:
   • Earliest finish time
   • Highest value/weight ratio
   • Maximum jump distance
   • Smallest end time
2. sort or prioritize the elements - this is a most common first step
   • sort arrays or use a priority queue if dynamic selection is needed
3. initialize result/tracking variables:
   • result count = 0
   • current end time / current capacity / current position / etc. = starting value
   • sometimes a "last selected" pointer or index
4. Iterate through the elements and for each:
   • Check if adding it is safe / possible / non-conflicting (greedy check: does it fit with previous choices?)
   • If yes, add it to solution (increment count, update end time/remaining capacity/position)
   • If no, skip it
5. Return the result

Variations of the template

• No sorting needed (pure linear pass)
  • Example: Jump Game I & II
  • Track farthest reachable, update when you hit current end
• Priority queue instead of sort
  • Example: Task Scheduler, Huffman coding
  • Repeatedly pick the max/min element from heap
• Two pointers or sliding window
  • Some greedy problems (longest substring, min platforms) use greedy + two pointers instead of explicit sort

In other words: prioritize by the magic key, then greedily take every valid next item that doesn't break the constraints.

Example - Task scheduler

Let's try to solve a more difficult problem. Let's call it Task Scheduler.

Problem statement: You are given n tasks represented by an array tasks where tasks[i] is the time needed to complete task i. You must schedule all tasks on a single CPU with these rules:

• The CPU can only work on one task at a time, and each task takes one unit of time to execute.
• After finishing a task, there must be at least cooldown units of time before you can start the same task again (if there are identical tasks).
• Tasks are not all unique - there can be duplicates (same task type).

You want to find the minimum total time needed to complete all tasks (including idle time). Return the minimum time units required.

Example: tasks = [1,1,2,2,3], cooldown = 2 - Output: 5

One possible schedule: 1,2,3,1,2

Total time = 5 (no idle slots)

int TaskScheduler(int[] tasks, int cooldown)
{
  // Step 1: Count the frequency of each task type (since same value = same type)
  // We use a dictionary to store how many instances of each task value there are
  var freq = new Dictionary<int, int>();
  foreach (var t in tasks)
  {
    freq[t] = freq.GetValueOrDefault(t, 0) + 1;
  }

  // Step 2: Create a max-heap (priority queue) to always pick the task type with
  // the most remaining instances. We use a custom comparer to make it max-heap
  // based on count (higher count first)
  var pq = new PriorityQueue<(int count, int task), int>(
    // Max-heap: higher count has higher priority
    Comparer<int>.Create((a, b) => b.CompareTo(a))  
  );

  // Enqueue all task types with their initial counts
  foreach (var kv in freq)
  {
    // Enqueue (count, task), prioritized by count
    pq.Enqueue((kv.Value, kv.Key), kv.Value);
  }

  // Step 3: Create a min-heap for tasks on cooldown
  // This tracks when a task type becomes available again after cooldown
  // (timeAvailable, task), prioritized by timeAvailable (earliest first)
  var cooldownQueue = new PriorityQueue<(int timeAvailable, int task), int>();

  // Step 4: Simulate time starting from 0
  var time = 0;

  // Loop until no more tasks in ready queue or cooldown queue
  while (pq.Count > 0 || cooldownQueue.Count > 0)
  {
    // Increment time by 1 each cycle (each unit represents a potential work or idle slot)
    time++;

    // Step 5: Move any tasks whose cooldown has ended back to the ready priority queue
    // Check the earliest cooldown task and dequeue if its timeAvailable <= current time
    while (cooldownQueue.Count > 0 && cooldownQueue.Peek().timeAvailable <= time)
    {
      var (availTime, task) = cooldownQueue.Dequeue();  // Remove from cooldown
      var remaining = freq[task];  // Get current remaining count for this task
      if (remaining > 0)
      {
        // Re-add to ready queue if still work left
        pq.Enqueue((remaining, task), remaining);
      }
    }

    // Step 6: If there is a ready task (pq not empty),
    // execute one instance of the most frequent one
    if (pq.Count > 0)
    {
      var (count, task) = pq.Dequeue();  // Get the task with highest remaining count
      count--;  // Execute one instance (decrement remaining)
      freq[task] = count;  // Update frequency

      // If still remaining instances, put it back on cooldown
      // Available again after current time + cooldown + 1 
      // (since time already includes this execution)
      if (count > 0)
      {
        cooldownQueue.Enqueue((time + cooldown + 1, task), time + cooldown + 1);
      }
    }
    // Else: No ready task -> CPU idles this time unit 
    // (time already incremented, so idle is counted)
  }

  // The final time is the minimum total units needed (work + idle)
  return time;
}

int[] tasks = [1, 1, 2, 2, 3];
int cooldown = 2;
Console.WriteLine(TaskScheduler(tasks, cooldown));

Here's what makes this solution greedy:

• It makes locally optimal choices at each step - at every time unit where the CPU can work (when pq is not empty), the code always picks the task type with the highest remaining count (the "best" available choice right now).
  • This is done via the max-heap (pq):var (count, task) = pq.Dequeue();
  • Picking the task with the most remaining instances is the greedy decision, it focuses on the current bottleneck (the type that still has the most work left).
• The greedy choice property holds (or is strongly believed to) - the key insight is: always working on the task type that has the most unfinished work (when it's ready) minimizes the total time, because it reduces the chance of being stuck waiting for cooldowns later.
  • This is the "never regret" part: choosing the highest-remaining task early tends to balance the load and avoid long idle periods caused by waiting for one type to become available again.
  • In practice, this heuristic works very well for this problem (and is the standard accepted greedy strategy).
• Irreversible decisions, no backtracking - once a task instance is executed at a certain time, the code never undoes it or reconsiders it.
  • No recursion, no trying alternative branches, no memoization table, just forward progress.
  • After executing: count--; freq[task] = count; if (count > 0) cooldownQueue.Enqueue(...); the choice is committed, and the task goes on cooldown if needed.
• Uses a priority queue to enforce the greedy rule. The max-heap is the classic greedy tool here:
  • It guarantees that at every decision point, you get the "best" (highest remaining count) ready task instantly.
  • This replaces sorting the entire input upfront (which wouldn't work well because tasks become ready dynamically over time).
• Overall algorithm is greedy-driven simulation - the loop simulates time tick by tick.
  • At each tick:
    • Move expired cooldown tasks back to ready (pq)
    • If anything is ready, greedily execute the one with most remaining work
    • If nothing ready, idle (time++ anyway)
  • This is a greedy event-driven simulation: always do the currently best possible action.

So it repeatedly chooses the currently best option (task with most remaining instances) using a max-heap. It relies on the greedy intuition that prioritizing high-remaining tasks leads to the minimum total time (the greedy choice property). There is no exhaustive search, no backtracking, no DP table, just forward greedy decisions.

However, if you were working on a real piece of software, this would probably not get you promoted. And the reason is that this entire thing can be calculated mathematically.

int[] tasks = [1, 1, 2, 2, 3];
int cooldown = 2;

var maxFreq = 0;
var countMax = 0;

foreach (var f in tasks.GroupBy(t=>t).Select(t=>t.Count()))
{
    if (f > maxFreq)
    {
        maxFreq = f;
        countMax = 1;
    }
    else if (f == maxFreq)
    {
        countMax++;
    }
}
var result = Math.Max(tasks.Length,(maxFreq - 1) * (cooldown + 1) + countMax);
Console.WriteLine(result);

maxFreq = the highest frequency of any single task type
countMax = how many task types have exactly that max frequency

Think of the schedule as consisting of "frames" or "cycles" separated by cooldown gaps. The task that appears most often creates the backbone of the schedule. Each pair of occurrences of that task needs at least cooldown idle slots between them. So for maxFreq occurrences you need (maxFreq - 1) gaps between them and each gap must be at least cooldown units long.

Therefore, you need (maxFreq - 1) * cooldown mandatory idle slots. Then add the maxFreq work slots for that frequent task, plus the work done by other tasks that can fill the gaps or after the last occurrence.

The tightest lower bound becomes: (maxFreq - 1) * (cooldown + 1) + countMax :

• (maxFreq - 1) gaps, each at least cooldown + 1 long (cooldown idles + 1 work slot for next same task)
• the number of tasks that share the max frequency (they all finish in the last cycle)

Finally take the max with total number of tasks (because you can't finish faster than the number of tasks if no idles are needed).

Conclusion

Greedy algorithms are useful when you can make an optimal decision at every step without fear of previous choices. In order word, independent choices. You need an insight about what the requirement actually is: sometimes greedy algorithm is another word for "Oh! That's what you really want!". And if you think well enough, you might not even need any greed, just computation.

That is why when you go on these algorithm interview sites, the problems in the greedy algorithm category have the most confusing descriptions and the most comments from people who didn't get what was asked of them.

Remember the matroid. In case of emergency, bring that up and see the other guy go silent.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I will cover Backtracking.

When to use Backtracking

Recognize a problem that can be solved with Backtracking by these signs:

• The problem asks for all possible solutions / combinations / permutations / arrangements / configurations.
• You need to find one (or all) valid solution(s) by making a sequence of choices/decisions.
• There is a decision tree structure: at each step you choose one option from several candidates.
• The number of possibilities is exponential (n!, 2ⁿ, etc.) but you can prune invalid branches early to avoid full enumeration.
• You can build the solution incrementally and check validity as you go (partial solutions are meaningful).
• Constraints allow early termination of a branch (e.g., sum exceeds target, board conflict, duplicate choice, invalid move).
• The problem involves puzzles, combinatorial search, or constraint satisfaction (Sudoku, N-Queens, crosswords, partitioning).

Words/phrases in the problem: "all possible", "generate", "find all combinations", "all permutations", "solve", "place", "fill", "arrange", "valid configurations", "every way to..."

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction or enumeration problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Classic backtracking problem patterns:

• Generate all subsets / combinations / permutations (with or without duplicates)
• N-Queens / chess piece placement puzzles
• Sudoku solver
• Word search / Boggle
• Palindrome partitioning
• Restore IP addresses
• Combination sum (with target)
• Letter combinations of a phone number
• Generate parentheses
• Rat in a maze / path finding with constraints

One-sentence rule: If the problem feels like "try every reasonable choice, go deeper, undo if it fails, and collect valid complete solutions" it is almost certainly backtracking.

Example - N-Queens

This is a problem often called "N-queens"

Problem statement: Place N queens on an N x N chessboard so that no two queens attack each other. Queens attack horizontally, vertically, or diagonally. Return one valid board configuration (or all, as a variation).

Represent the board as a list of strings where 'Q' = queen and '.' = empty.

Constraints: 1 <= N <= 9 (for N=1 to N=9 there is always at least one solution).

Example for N=4 (one possible solution):

. Q . .
. . . Q
Q . . .
. . Q .

Output as: [".Q..","...Q","Q...","..Q."]

Here is a naive implementation:

using System.Text;

var count = 0;

IList<IList<string>> SolveNQueens(int n)
{
    var result = new List<IList<string>>();
    char[,] board = new char[n, n];
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            board[i, j] = '.';

    PlaceQueensNaive(board, 0, n, result);
    return result;
}

void PlaceQueensNaive(char[,] board, int row, int n, IList<IList<string>> result)
{
    count++;
    if (row == n)
    {
        // Check if valid (very late)
        if (IsValid(board, n))
        {
            var sol = new List<string>();
            for (var i = 0; i < n; i++)
            {
                var sb = new StringBuilder();
                for (var j = 0; j < n; j++)
                    sb.Append(board[i, j]);
                sol.Add(sb.ToString());
            }
            result.Add(sol);
        }
        return;
    }
    for (var col = 0; col < n; col++)
    {
        board[row, col] = 'Q';
        PlaceQueensNaive(board, row + 1, n, result);
        board[row, col] = '.';  // backtrack
    }
}

bool IsValid(char[,] board, int n)
{
    // Check columns and diagonals for each queen
    for (var r = 0; r < n; r++)
    {
        for (var c = 0; c < n; c++)
        {
            if (board[r, c] != 'Q') continue;

            // Check right, down-right, down-left from this queen
            // (we only need to check one direction because we fill row by row)

            // Same column below
            for (var i = r + 1; i < n; i++)
                if (board[i, c] == 'Q') return false;

            // Down-right diagonal
            for (var i = r + 1, j = c + 1; i < n && j < n; i++, j++)
                if (board[i, j] == 'Q') return false;

            // Down-left diagonal
            for (var i = r + 1, j = c - 1; i < n && j >= 0; i++, j--)
                if (board[i, j] == 'Q') return false;
        }
    }

    return true;
}

var result = SolveNQueens(4);
Console.WriteLine("Executions: " + count);
foreach (var solution in result)
{
    Console.WriteLine(string.Join("\r\n", solution));
    Console.WriteLine();
}

Now, this outputs the two possible solutions for N=4 and 341 executions.

The IsValid method is not the most efficient implementation, but it's readable (also not really the focus of the post).

There are several issues with PlaceQueensNaive, though:

• Tries every cell -> nⁿ possibilities (for n=9: ~387 million)
• Validation only at the end -> wastes time exploring invalid partial boards
• No early pruning -> extremely slow even for n=8

Let's see a good solution:

using System.Text;

var count = 0;

IList<IList<string>> SolveNQueens(int n)
{
    var result = new List<IList<string>>();
    var board = new char[n, n];
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            board[i, j] = '.';

    var cols = new bool[n];
    var diag1 = new bool[2 * n - 1];  // row + col
    var diag2 = new bool[2 * n - 1];  // row - col + (n-1)

    Backtrack(0, board, cols, diag1, diag2, n, result);
    return result;
}

void Backtrack(int row, char[,] board, bool[] cols, bool[] diag1, bool[] diag2, int n, IList<IList<string>> result)
{
    count++;
    if (row == n)
    {
        var sol = new List<string>();
        for (var i = 0; i < n; i++)
        {
            var sb = new StringBuilder();
            for (var j = 0; j < n; j++) sb.Append(board[i, j]);
            sol.Add(sb.ToString());
        }
        result.Add(sol);
        return;
    }

    for (var col = 0; col < n; col++)
    {
        var d1 = row + col;
        var d2 = row - col + n - 1;

        if (cols[col] || diag1[d1] || diag2[d2]) continue;  // prune - attacked

        // Place
        board[row, col] = 'Q';
        cols[col] = true;
        diag1[d1] = true;
        diag2[d2] = true;

        Backtrack(row + 1, board, cols, diag1, diag2, n, result);

        // Backtrack
        board[row, col] = '.';
        cols[col] = false;
        diag1[d1] = false;
        diag2[d2] = false;
    }
}

var result = SolveNQueens(4);
Console.WriteLine("Executions: " + count);
foreach (var solution in result)
{
    Console.WriteLine(string.Join("\r\n", solution));
    Console.WriteLine();
}

Why this is optimal:

• One queen per row -> n! instead of n²
• Immediate pruning with column + diagonal tracking -> most branches die early
• Time: O(n!) worst case but in practice much faster due to heavy pruning
• For n=9 it runs almost instantly

The count of executions is 17.

Backtracking template

While the code above was simple and clear, it still carries a lot of the particular problem details. Can we imagine a generic backtracking solution? And we kind of can:

• start with a mechanism of generating candidate steps or a list of them
• then prepare a result which is a list of lists of steps
  • each list of steps will represent a solution and the result is the list of solutions
• then call the backtracking method, by adding an empty list as a partial solution
• In the method code:
  • first check if solution is valid, and if so add it to the result and return from the method
    • you may want to exit here permanently if the requirement is to find just a single solution
  • then check if you can prune it (invalidate partial solution as soon as possible), and if so return (abandon it)
  • then for all possible steps:
    • check if the step is valid for the partial solution (and if not, skip it)
    • add (place) the step to the solution - this represents the solution with an extra step
    • call the method on the new solution
    • remove (backtrack) the step from the solution - this prepares the solution for the next step

That's it. You note that we've used the recursive function idea here, but we can use a queue with the same purpose:

• start with a mechanism of generating candidate steps or a list of them
• then prepare a result which is a list of lists of steps
  • each list of steps will represent a solution and the result is the list of solutions
• then prepare a queue of lists of steps
  • each list of steps is a partial solution, the queue is the work list
• while there are items in the queue:
• dequeue an item
• first check if solution is valid, and if so add it to the result and continue to the next item in the queue
  • you may want to exit here permanently if the requirement is to find just a single solution
• then check if you can prune the solution, and if so continue to the next item in the queue
• then for all possible valid steps:
  • enqueue a new item from the solution with the step applied

So... where's the backtracking? These two forms are called recursive and iterative backtracking. The second gives you more control and might be needed when there are a lot of possible steps to escape the limitation of the call stack size. You may recognize it as the BFS/DFS method described in my previous post. Queue for BFS, stack for DFS.

You see, a lot of people refer to just the recursive version of backtracking as backtracking. It is:

• shorter and more elegant to write
• the "backtrack" action is implicit (you just return from the method)
• the undo step is done automatically when the method exits
• recursion uses the call stack

The iterative version is:

• more verbose
• you have to create a solution explicitly (generate/copy and add new list to queue)
• uses the heap, so it doesn't do stack overflows
• it doesn't backtrack as much as it doesn't follow up on invalid partial solutions 

Personally, I prefer the second, because it's more flexible and offers more control, but you be the judge.

Example - Generate parentheses

An almost as common interview question for backtracking is the Generate Parentheses problem.

Problem statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

And here is the solution:

IList<string> Backtrack(int n, string current="", int open=0, int close=0,  IList<string> result=null)
{
    result ??= [];
    // Base case: we used exactly n pairs and string is complete
    if (current.Length == n * 2)
    {
        result.Add(current);
        return result;
    }

    // Choice 1: add an opening parenthesis (if we can)
    if (open < n)
    {
        Backtrack(n, current + "(", open + 1, close, result);
    }

    // Choice 2: add a closing parenthesis (only if more opens than closes)
    if (close < open)
    {
        Backtrack(n, current + ")", open, close + 1, result);
    }
    return result;
}

var result = Backtrack(3);
Console.WriteLine(string.Join("\r\n",result));

I got a little fancy here:

• I used the same method as the solve and the backtrack method, taking advantage of the default parameter value feature of C#, but that meant I had to return the result all the time
• There is no loop over steps, because there are just two of them
• The pruning is done before calling the backtracking method, by checking the open and close values
• There is no backtracking per se, since we are using a new copy (concatenated string) in all calls
• You want to get extra fancy? Use a StringBuilder instead of a string, Append the parentheses, then decrement the StringBuilder length when you exit, thus implementing literal backtracking.
  • there is a gotcha here, though, see below in the Generic backtracking section

The output is the five possible solutions.

This is optimal because:

• Time complexity: O(4ⁿ / sqrt(n)) - this is the number of valid Catalan number sequences, roughly O(4ⁿ).
• Backtracking prunes almost all invalid paths early.
• Space complexity: O(n) recursion depth + O(4ⁿ) for output storage.
• No extra arrays or complex state - just track count of open and close parentheses.
• Very clean and efficient - runs instantly even for n=8.

Generic backtracking

I have tried to implement a generic class that does backtracking solving. And I made it, but it was really ugly. I tried simplifying it in several ways, but in the end I gave up. Why? Because backtracking in itself is such a general solution to a lot of problems that trying to create a class to encapsulate that results in a very thin thing that requires the solution type to implement everything.

If you think about it, the solver has to implement:

• a type for the solution
• a type for the current state
• a way to generate valid steps based on current state (and possibly the list of existing solutions)
• a way to apply the steps on the current solution and state (and unapply them, if you want standard backtracking)
• a way to determine validity of a solution
• a way to extract/clone the result from the solution

And you realize that you either have to provide a lot of functions as parameters to the solver, or you have to combine the solution type and state type and implement the methods there. And in the second case, the solver itself does nothing in particular.

My implementation, in order to solve the generate parentheses problem, assumed any solution is an IList<TItem> and the TItem was (char ch, int open, int closed, int pairCount), which was frankly ridiculous.

Sometimes it pays off, though, to try to achieve such things in order to understand why they would not work and what are the underlying assumptions in your code.

For example, you never considered that in both examples above we needed to clone the solution in order to add it to the result. In the first example we were putting in the result sb.ToString(), which generates a clone of the StringBuilder, and in the second example we were using string concatenation, which generates a new string every time. If you had added the StringBuilder itself to the result list, then it would have held the reference to the same object several times.

Conclusion

Backtracking is an important tool in any developer's toolkit and it is one of the first theoretical computer science concepts you are being taught in school. The magic is in three steps: choose an option, explore deeper by recursing, unchoose when you return. Everything else (pruning, skipping duplicates, validity checks) is just smart decoration around this loop.

But once you look "under the hood" you realize that in order to implement classic backtracking you are relying on programming language constructs that add syntactic sugar to an otherwise differently defined problem: growing a list of possible solutions and eliminating them early if they cannot yield a valid solution.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

  Today I will be covering Breadth First Search (BFS) in tree/graph traversals.

When to use BFS

  Recognize a problem that can be solved with BFS by these signs:

• The problem requires the shortest path, minimum steps, fewest moves, earliest time, or minimum operations in an unweighted graph, grid, tree, or similar structure (this is the single strongest signal - BFS is the only standard algorithm that guarantees shortest path in unweighted settings)
• All edges/moves have equal cost (unit cost / cost = 1, if costs vary -> Dijkstra / 0-1 BFS / A* instead)
• The solution needs level-by-level processing, results grouped by distance, or exploration ordered by increasing distance from the start(s) (includes collecting nodes per level, processing by depth, or any "by distance k" requirement)
• The problem has multi-source starting points (multiple cells/nodes begin simultaneously at distance/time 0) OR it involves spreading / propagation / infection / flooding from one or more origins over time

  Basically you are expanding your search by filling the solution space as close to the starting point as possible.

  Rule of thumb: if the problem says 'shortest', 'minimum steps', 'level by level' or 'multi-source spread' in an unweighted graph/grid/tree, then BFS is your friend.

Example - Shortest path in maze

In the previous post we've used a maze problem to demonstrate the use of depth first search (DFS). There we had to find if a maze can be solved, any solution would do, and it did find a solution which was ludicrously long. Now we're being asked to find the shortest path to escape the maze.

Problem statement: Given a 2D grid representing a maze (0 = open path, 1 = wall), find the minimum number of steps to go from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). You can move in 4 directions (up, down, left, right), but cannot go through walls or outside the grid. Return the shortest path length, or -1 if no path exists. Assume (0,0) and (m-1,n-1) are open (0).

Example grid (same as in the DFS post):

var maze = new int[][]
{
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 0]
};

Since we've already solved a maze question with DFS, why not do it here as well? Here is a possible attempt:

int minSteps = int.MaxValue;

int ShortestPath(int[][] maze, int row, int col, int steps = 0)
{
    var m = maze.Length;
    var n = maze[0].Length;

    if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
        return -1;

    if (row == m - 1 && col == n - 1)
    {
        minSteps = Math.Min(minSteps, steps);
        return minSteps;
    }

    // Mark as visited by setting to 1 (temporary)
    maze[row][col] = 1;

    // Explore all 4 directions
    ShortestPath(maze, row - 1, col, steps + 1);  // up
    ShortestPath(maze, row + 1, col, steps + 1);  // down
    ShortestPath(maze, row, col - 1, steps + 1);  // left
    ShortestPath(maze, row, col + 1, steps + 1);  // right

    // Backtrack: unmark
    maze[row][col] = 0;

    return minSteps == int.MaxValue ? -1 : minSteps;
}

var result = ShortestPath(maze, 0, 0);
Console.WriteLine(result);

The output is 6, which is correct, so is this a good solution? Let's see what the complexity of the algorithm is.

The time complexity is O(4^n*m) in worst cases (branching factor 4 - the directions - and depth up to m*n). This times out even on small grids! Then the marking and unmarking of things is also adding complexity and stack space: O(n*m), which would lead to stack overflows.

But what's worse is that this may not find the shortest path at all! And if it does, it explores longer paths when shorter ones exist.

With BFS, this doesn't happen. The standard form of a BFS solution looks like this:

public int SomeBfs(TreeNode root) {  // or int[][] grid, etc.
    if (root == null) return 0;
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    // bool[,] visited = ... if needed
    var level = 0;

    while (queue.Count > 0) {
        var size = queue.Count;  // process current level
        for (var i = 0; i < size; i++) {
            TreeNode node = queue.Dequeue();
            // Do something with node (e.g. collect value)
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        level++;
    }
    return level - 1;  // example: max depth
}

The inner loop processes one full level before moving deeper - that's the BFS guarantee - but it's not needed most of the time, since you can just dequeue node by node. The point is that by using a queue, you ensure a first in first out (FIFO) approach, proceeding one level further only when the previous one has been explored.

Let's see how that works for our problem:

int ShortestPath(int[][] maze)
{
    if (maze == null || maze.Length == 0)
        return -1;

    var m = maze.Length;
    var n = maze[0].Length;

    if (maze[0][0] == 1 || maze[m - 1][n - 1] == 1)
        return -1;

    var visited = new bool[m, n];
    var queue = new Queue<(int, int, int)>();
    queue.Enqueue((0, 0, 0));  // row, col, steps
    visited[0, 0] = true;

    int[][] directions = [
        [ -1, 0 ],
        [ 1, 0 ],
        [ 0, -1 ],
        [ 0, 1 ]
    ];  // up, down, left, right

    while (queue.Count > 0)
    {
        var (r, c, steps) = queue.Dequeue();

        if (r == m - 1 && c == n - 1)
            return steps;

        foreach (var dir in directions)
        {
            var nr = r + dir[0];
            var nc = c + dir[1];

            if (nr >= 0 && nr < m 
             && nc >= 0 && nc < n
             && maze[nr][nc] == 0 && !visited[nr, nc])
            {
                visited[nr, nc] = true;
                queue.Enqueue((nr, nc, steps + 1));
            }
        }
    }

    return -1;  // no path
}

Note the tuple used as the queue item type! In this kind of solutions, that type needs to hold all the information needed to process a step. In our case, it's the row and column position plus the number of steps to get there.

The execution is simple: start with (0,0,0 - top-left corner) in the queue, then process and remove items in the queue one by one and add four new ones, one for each direction. Constraints like never process the same cell twice, keeping in the borders of the grid and FIFO processing guarantee that when a solution is found, it's the shortest.

If you try to visualize how that works, imagine each cell as it is placed in the queue changing it's color to red:

If you have ever used a graphical image editor, you may recognize the "fill" feature, where you select a color to fill up the space taken by another color. That's another common problem for this kind of algorithm.

So, let's check the complexity. Time: O(n*m) as each cell is visited at most once. Space: O(n*m) for the visited array and the queue. BFS explores by increasing distance, so the first time it reaches the end is guaranteed to be the shortest path. No backtracking needed, and it stops as soon as possible.

Switching between DFS and BFS

I was planning on writing a separate post about this, but the setup is the same, so I will just make this another chapter here.

We've learned to use the stack of the programming language to do DFS, but for BFS we had to use our own data structure, the queue, where an item contains all of the information required to run a step. We also learned that the stack is limited (usually to around 1MB) so even a working DFS program might lead to a stack overflow if the input data is too large. This would not happen in the case of the BFS example. The queue would just take up as much space as it needs within the available memory. This means that using the default recursive execution mechanism of the programming language is making the solution brittle.

If only we could use the same mechanism we used for BFS to write a DFS solution! Well, if you think about it, the only reason the BFS is doing things level by level is the FIFO implementation of the queue. Replacing the queue with a stack (wait, stack? yes, it's the same thing as the one used by the recursive function calling) moves us from FIFO to LIFO (last in, first out) and translates BFS solutions to DFS solutions.

Replacing in our code above a Queue<T> with a Stack<T>, Enqueue with Push and Dequeue with Pop, you execute it and get the same result! But if you visualize the path the code takes, it looks like this:

Only the shape of the maze makes this finish in the same number of steps as the BFS one, so this is not a valid solution for the problem, but this simplifies the development model a little. All you need to do is write the same kind of code and choose the right data structure to generate a DFS or a BFS solution. And bonus points, you can tell the interviewers that you would never trust the tiny recursive execution stack to be large enough for your code.

Let's see the DFS example from the previous post, written with our own stack implementation:

bool HasPath(int[][] maze)
{
    var m = maze.Length;
    var n = maze[0].Length;

    var visited = new bool[m][];
    for (var i = 0; i < m; i++)
        visited[i] = new bool[n];
    var stack = new Stack<(int row, int col)>();
    stack.Push((0, 0));
    while (stack.TryPop(out var cell))
    {
        var (row, col) = cell;
        if (row < 0 || row >= m 
            || col < 0 || col >= n 
            || maze[row][col] == 1)
            continue;

        if (row == m - 1 && col == n - 1)
            return true;

        // avoid cycles by not visiting the same cell again
        if (visited[row][col])
            continue;

        // mark the cell as visited
        visited[row][col] = true;

        stack.Push((row-1, col));
        stack.Push((row+1, col));
        stack.Push((row, col-1));
        stack.Push((row, col+1));
    }
    return false;
}

var result = HasPath(maze);
Console.WriteLine(result);

This solution is completely equivalent, but using no recursion whatsoever. Note that the item type is just a pair of row and column, since the maze is a local parameter. To do that with recursion you need to declare a local function, which makes the code a lot less readable. Also, while maintaining the logic of the original method, this is not optimal. We are adding items in the stack and only checking the values in the item when we get it off the stack. If you check that before adding them to the stack, the code will become more efficient and even more readable.

The caveat, though, is that if you write the code badly, you have to wait for a memory overflow to know you fouled it up.

Example - Shortest path visiting all nodes

Let take a really nasty problem: Shortest Path Visiting All Nodes. This is a classic hard problem in the interviews, so let's see how it goes.

Problem statement: You are given an undirected, connected graph with n nodes labeled from 0 to n-1 and a list of edges (as adjacency list: graph[i] = list of neighbors of i). Return the length of the shortest path that visits every node exactly once (you can start at any node and return to visited nodes if needed, but must cover all). The path length is the number of edges traversed. If no such path exists, return -1 (but since the graph is connected, it always does).

Constraints

• 1 ≤ n ≤ 12
• 0 ≤ graph[i].Length < n (no self-loops, possible multiple edges but assume simple)
• The graph is undirected and connected.

Naive solution:

int[][] graph1 = [ [1, 2, 3], [0], [0], [0] ];
// Nodes: 0 connected to 1,2,3; others only to 0.
// Shortest path covering all: e.g., 3-0-1-0-2 (visits all, length 4)
// Output: 4

int[][] graph2 = [ [1], [0, 2, 4], [1, 3, 4], [2], [1, 2] ];
//A more connected graph.
//Shortest path: e.g., 0-1-2-3-4 (length 4, but check if shorter exists)
//Output: 4

int minLength = int.MaxValue;

int ShortestPathLength(int[][] graph)
{
    var n = graph.Length;
    for (var start = 0; start < n; start++)
    {
        var visited = new bool[n];
        visited[start] = true;
        Dfs(graph, start, 1, visited, 0);  // node, visited count, path length
    }
    return minLength == int.MaxValue ? -1 : minLength;
}

void Dfs(int[][] graph, int node, int visitedCount, bool[] visited, int length)
{
    if (visitedCount == visited.Length)
    {
        minLength = Math.Min(minLength, length);
        return;
    }

    foreach (var nei in graph[node])
    {
        if (!visited[nei])
        {
            visited[nei] = true;
            Dfs(graph, nei, visitedCount + 1, visited, length + 1);
            visited[nei] = false;  // backtrack
        }
        else
        {
            // Even allow revisits? But this explodes
            Dfs(graph, nei, visitedCount, visited, length + 1);
        }
    }
}

Console.WriteLine(ShortestPathLength(graph1));
Console.WriteLine(ShortestPathLength(graph2));

The DFS one has the issues we've seen with the simple maze example above:

• exponential complexity explosion: O(n! * n)
• no guarantee that the found path is shortest
• backtracking is inefficient 
• missing state as it doesn't track visited nodes efficiently

This fails with a terrible stack overflow exception. Of course, we could implement this with a Stack<T> and reach a much worse timeout/memory overflow exception.

Let's take a look at the BFS solution with the correct implementation:

int[][] graph1 = [ [1, 2, 3], [0], [0], [0] ];
// Nodes: 0 connected to 1,2,3; others only to 0.
// Shortest path covering all: e.g., 3-0-1-0-2 (visits all, length 4)
// Output: 4

int[][] graph2 = [ [1], [0, 2, 4], [1, 3, 4], [2], [1, 2] ];
//A more connected graph.
//Shortest path: e.g., 0-1-2-3-4 (length 4, but check if shorter exists)
//Output: 4

int ShortestPathLength(int[][] graph)
{
    var n = graph.Length;
    var target = (1 << n) - 1;  // all nodes visited: 111...1 (n bits)

    Queue<(int node, int mask, int steps)> queue = new();
    var visited = new bool[n, 1 << n];  // node + mask visited?

    // Start from every node (multi-source)
    for (var i = 0; i < n; i++)
    {
        var initMask = 1 << i;
        queue.Enqueue((i, initMask, 0));
        visited[i, initMask] = true;
    }

    while (queue.Count > 0)
    {
        var (node, mask, steps) = queue.Dequeue();

        if (mask == target)
            return steps;

        foreach (var nei in graph[node])
        {
            var newMask = mask | (1 << nei);  // visit nei

            if (!visited[nei, newMask])
            {
                visited[nei, newMask] = true;
                queue.Enqueue((nei, newMask, steps + 1));
            }
        }
    }

    return -1;  // though always connected
}

Console.WriteLine(ShortestPathLength(graph1));
Console.WriteLine(ShortestPathLength(graph2));

Bonus: uses a bit mask to store the visited nodes for each step. Interview people love bit operations and premature optimizations.

The solution starts from every single node to find the shortest path, a classical BFS sign. In the beginning the queue has an item for each node, a mask with a bit for that node only and a counter for the steps. Then it removes items one by one and adds items for each of the neighbors, mask updated, counter incremented. Again, because we use a FIFO queue, when we first get to the target (the mask is filled with 1s), it's guaranteed to have a the smallest count of steps. 

Note that this would also fail if n were allowed to be much larger than 12.

Time complexity: O(n * 2ⁿ * E / n) ≈ O(n * 2ⁿ) since E small - for n=12, ~50k states * avg degree ~3-5 = ~200k operations, fast.

Space complexity: O(n * 2ⁿ) for visited (~50k bools).

Example - Binary tree level order traversal

Let's do one more: Binary Tree Level Order Traversal.

Problem statement: Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Return the result as a list of lists, where each inner list contains the node values at that level.

Example:  

Output: [[3],[9,20],[15,7]]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 ≤ Node.val ≤ 1000

So here's the code:

IList<IList<int>> LevelOrder(TreeNode root)
{
    var result = new List<IList<int>>();

    if (root == null)
    {
        return result;
    }

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

    while (queue.Count > 0)
    {
        // Number of nodes at current level
        var levelSize = queue.Count;
        // Values for this level
        var currentLevel = new List<int>();

        // Process all nodes at the current level
        for (var i = 0; i < levelSize; i++)
        {
            TreeNode node = queue.Dequeue();
            currentLevel.Add(node.Value);

            // Enqueue children for the next level
            if (node.Left != null)
            {
                queue.Enqueue(node.Left);
            }
            if (node.Right != null)
            {
                queue.Enqueue(node.Right);
            }
        }

        result.Add(currentLevel);
    }

    return result;
}

TreeNode root = new()
{
    Value = 3,
    Left = new() { Value = 9 },
    Right = new()
    {
        Value = 20,
        Left = new() { Value = 15 },
        Right = new() { Value = 7 }
    }
};

var result = LevelOrder(root);
Console.WriteLine($"[ {string.Join(", ",result.Select(a=> $"[{string.Join(", ",a)}]"))} ]");

The time complexity is O(n) - we visit each node exactly once, the space complexity is O(w) - where w is the maximum width of the tree (size of the queue at the widest level), worst-case O(n) for a complete tree.

The inner for loop over queue.Count ensures we process one full level before moving deeper - that's what gives the level-by-level order. Without the level-size loop, you'd get a flat list instead of grouped by level.

DFS (recursive) can also collect levels (by passing depth parameter), but BFS feels more natural and intuitive for this exact requirement.

Conclusion

Exploring the solution space using graph traversal is a very powerful technique used in a lot of contexts. Go depth or breadth first, depending on the requirements, in order to get to the optimal solution.

• BFS: shortest path guarantee, but higher memory (queue can hold O(n) nodes)
• DFS: simpler recursion, lower memory in deep-but-narrow graphs, but no shortest-path promise
• When BFS loses: very deep trees, leading to recursion stack overflow risk (rare)
• Hybrid tip: use BFS when correctness > simplicity

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

  Today I will be covering depth first search (DFS) in tree/graph traversals.

When to use DFS

  Both DFS and BFS (Breadth First Search) are ways of exploring connected elements, but DFS comes more natural for people. You go as deep as you can, then backtrack when you get stuck. Unlike BFS, DFS explores exhaustively and doesn't care about levels. DFS is mostly used to find tree properties (depth, diameter), path finding, validation and most graph connectivity problems.

Recognize a problem that can be solved with DFS by these signs:

• it has a natural recursive structure (do the same thing for child/neighbor)
• you need to find a path or check the existence of one (and not necessarily the shortest one)
• the solution requires processing children/subtrees before their parents (height, diameter, subtree sum, bottom-up computation)
• is the problem about computing or validating a property along a path (path sum exists, is binary search tree (BST) valid, balanced tree, cycle exists)
• the input is a tree, binary tree, BST, N-ary tree, trie, or graph, and we do not need level-by-level processing or shortest-path distance

Basically you've got some kind of connected structure and you don't care about what happens on specific levels or you need to compare all paths to find the best.

Example - Maze path finding

The poster problem for DFS is maze path finding as it lends itself perfectly for the "go as deep as possible and backtrack" idea. Here is the problem statement:

Given a 2D grid representing a maze (0 = open path, 1 = wall), determine if there is a path from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). You can move in 4 directions (up, down, left, right), but cannot go through walls or outside the grid. Assume (0,0) and (m-1,n-1) are open (0).

Example grid:

var maze = new int[][]
{
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 0]
};

Let's look at the naive solution (recursion without visited marking):

bool HasPath(int[][] maze, int row, int col)
{
    var m = maze.Length;
    var n = maze[0].Length;

    if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
        return false;

    if (row == m - 1 && col == n - 1)
        return true;

    // Try all 4 directions
    return HasPath(maze, row - 1, col) ||  // up
           HasPath(maze, row + 1, col) ||  // down
           HasPath(maze, row, col - 1) ||  // left
           HasPath(maze, row, col + 1);    // right
}

var result = HasPath(maze, 0, 0);
Console.WriteLine(result);

Here we try all possible directions to get to a solution and the result is, because there are clearly several paths to the end... a StackOverflowException! This is the error thrown when the entire stack used internally for function recursion has been used up. In other words, we recursed ourselves out of memory. The problem is that we are going in loops forever: up, down, then up again and so on. The solution is marking the visited cells so that we don't do that:

bool HasPath(int[][] maze, int row, int col, 
    /* marking visited */bool[][] visited = null)
{
    var m = maze.Length;
    var n = maze[0].Length;

    // Initialize visited array on the first call
    if (visited == null)
    {
        visited = new bool[m][];
        for (int i = 0; i < m; i++)
            visited[i] = new bool[n];
    }

    if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
        return false;

    if (row == m - 1 && col == n - 1)
        return true;

    // avoid cycles by not visiting the same cell again
    if (visited[row][col])
        return false;

    // mark the cell as visited
    visited[row][col] = true;

    // Try all 4 directions (with visited tracking)
    return HasPath(maze, row - 1, col, visited) ||  // up
           HasPath(maze, row + 1, col, visited) ||  // down
           HasPath(maze, row, col - 1, visited) ||  // left
           HasPath(maze, row, col + 1, visited);    // right
}

var result = HasPath(maze, 0, 0);
Console.WriteLine(result);

The result now is True, as expected.

Now, the path that this version of the code found is really inefficient, too, because of the way the choice of the direction is made, however, in "big O", the complexity is still time O(m*n) and space O(m*n) (because of the visited array). So remember that efficiency in theoretical terms is not the same as efficiency in engineering terms.

It's a nice idea to ponder on how would you alter the algorithm so that it doesn't always try to go back the way it came.

This code guarantees termination (a critical issue in recursive algorithms), avoids redundancy and finds a path - which is not necessarily optimal. Classic DFS. And it is depth first because it goes how far it can go before "backtracking" to a previous position and trying a new path. A breadth first search is obviously possible, but it would take a lot more resources. It would be the best solution for a requirement of finding the fastest path out of the maze, though.

Theory

Now you may have noticed that in this post about trees and graphs I presented something that works with arrays. That's because there is a lot - and I mean a lot - of theory related to graphs in computer science. Trees, too, but they are a special case of graphs, so... remember that when you walk outside looking for shade. OK, enough shade thrown on the computer scientists! It's just very easy to make fun of their hard work.

So let's delve a little in that theory by describing a few terms that will help us understand a true graph problem:

• A graph is a collection of points (called vertices or nodes) connected by lines (called edges)
  • Vertices / Nodes are the things you care about (people, cities, web pages, computers, tasks, etc.)
  • Edges are the relationships or connections between them (friendship, road, hyperlink, network cable, dependency, etc.)
• An undirected graph is a graph where the edges don't have a direction or rather they are always bidirectional. If A is connected to B, then B is connected to A.
• A directed graph (or a digraph) is a graph where edges have a direction. If an edge connects A to B, you need another edge to connect B to A.
• A connected graph is a graph where all the nodes are connected to at least another node.
• A cycle is a path that starts and ends at the same node.
• An acyclic graph is a graph with no cycles.
• A tree is a fully connected graph with no cycles. Trees are found everywhere because they represent hierarchies: parent-child relationships.
  • every tree is an acyclic graph, but not the other way around. An acyclic graph can have more than one components (separated groups of connected nodes). A tree has N-1 edges, where N is the number of nodes.
• A binary tree is a tree where a node has at most two children, usually called the left and the right child. Binary tree nodes are assholes, they think of one child as the right one and the other is just left out.
  • they are used a lot in computer science and algorithms, but we're not going to explain them here. As usual, follow the links in the blog to find out more, if you're interested.
  • we will need to know what a binary tree is for when we hear the term BST (Binary search tree) which is used for data structures with fast search, insert and delete.
• A binary search tree (BST) is a tree where:
  • the values of all the nodes in the left subtree are smaller than the value of the root node
  • the values of all the nodes in the right subtree are larger than the value of the root node
  • all subtrees are valid BSTs

Usually in these problems we get a class called TreeNode which holds an integer value and the two child nodes, something like this:

class TreeNode {
  public int Value {get;set;}
  public TreeNode Left {get;set;}
  public TreeNode Right {get;set;}
}

Use a struct or a record to show you're fancy, but then you will have to explain what's the difference between structs, records and classes.

Other problems use adjacency lists or some other ways of storing graph data.

With this nomenclature in mind, let's see some examples.

Example - Validate Binary Search Tree

Problem statement: Given the root of a binary tree, determine if it is a valid binary search tree.

The solution is simple:

bool IsValidBSTDfs(TreeNode node, int min=int.MinValue, int max=int.MaxValue)
{
    if (node == null) return true;

    if (node.Value <= min || node.Value >= max) return false;

    return IsValidBSTDfs(node.Left, min, node.Value)
        && IsValidBSTDfs(node.Right, node.Value, max);
}

I didn't provide a naive solution, because this is a very simple problem, but one of the common errors developers make in trying to solve it is to assume that if the node value of the current node is between left and right and then you recurse, the tree is a valid BST. However, that leads to cases where a value in the left subtree is larger than the root node or a smaller one in the right tree. Always check the requirements!

The time complexity of this is O(n), because it goes through all of the nodes once. The space complexity is O(h), where h is the height of the tree, with worse case scenario O(n) if a tree is composed of nodes with just one child and h=n.

Now you might ask how is this O(h) in space if there is a class for each node? Remember, the O notation measures the complexity of the solution, not of the problem. By recursing through h levels (even if that means it adds and removes n elements on the stack) the stack never increases with more than h elements.

Since we are talking about checking all nodes, a breadth first search is also possible. I will discuss this in the BFS post, but also in another post that I plan to do on how to NOT use the native language recursion and control the entire stack/queue yourself. When you do that, the code gets a little bit more complex, but then the difference between DFS and BFS becomes the choice between a stack and a queue. Stay tuned, it's going to be an instructive post.

Example - Cycle detection in directed graph

Problem statement: Given a directed graph (as adjacency list: List<List<int>> graph), detect if it contains a cycle. Nodes are labeled 0 to V-1, where V = graph.Count. A cycle exists if there's a path that starts and ends at the same node (following directions).

In this situation the data structure changes again. The node doesn't have a value, it just has a list of directions towards other nodes and is defined by its index. The structure holding this is a list of lists, where the index in the list represents the node and the value in the list is a list of indexes towards other nodes.

Let's try some code:

bool HasCycle(List<List<int>> graph, int node, bool[] visited=null)
{
    visited ??= new bool[graph.Count];
    if (visited[node]) return true;
    visited[node] = true;

    foreach (var neighbor in graph[node])
    {
        if (HasCycle(graph, neighbor, visited))
        {
            return true;
        }
    }

    return false;
}

List<List<int>> graph = [
    [1,2],
    [2],
    []
];
Console.WriteLine(HasCycle(graph, 0)); // Output: True

The idea here is simple: start with each neighbor of each node then recurse. If you find any node that has been visited before, you have a cycle. Or do you? The code above has a conceptual bug. Can you find it? Look at the example and tell me, is the output correct?

The answer is no. One can reach the same node multiple ways (in our case the index 2 node), but because it's a directed graph, it might not be necessarily a cycle. In our case, node 0 connects to node 1, which then connects to node 2, but node 0 also connects to 2 directly. There is no way to get from node 2 back to 0, though, so there is no cycle.

How would you solve it? The solution - in terms of code - is very simple, but one has to have seen the problem before or have a lot of time to find it. That's why I think this kind of problems are terrible for determining if you're a good developer, but I digress. Here is the working solution:

bool HasCycle(List<List<int>> graph, int node, int[] visited=null)
{
    visited ??= new int[graph.Count];
    visited[node] = 1;

    foreach (var neighbor in graph[node])
    {
        if (visited[neighbor] == 1) return true;
        if (visited[neighbor] == 0 && HasCycle(graph, neighbor, visited))
        {
            return true;
        }
    }
    visited[node] = 2;
    return false;
}

List<List<int>> graph = [
    [1,2],
    [2],
    []
];
Console.WriteLine(HasCycle(graph, 0)); // Output: False

graph =
[
    [1],
    [2],
    [0]
];
Console.WriteLine(HasCycle(graph, 0)); // Output: True

Simply replace the type of the visited array to int, mark a node as "visiting" with 1, then as "visited" with 2. You ignore visited nodes, but if you find one that is in visiting state as a neighbor, then you're in a cycle.

Note: this would be a lot more readable with a three state Enum, and if you feel like it go for it. People will appreciate making the code more readable. But it will take you some extra time to write up the Enum definition, so this is - in my eyes - another reason why these tests measure the wrong thing.

The time complexity of this algorithm is O(V+E) where V is the number of vertices/nodes and E is the number of edges. The space complexity is O(V), as we create an array of size V as part of the solution.

Example - Maximum path sum in DAG

This one is very hard to figure out, but easy to implement. You just have to have a feeling for these things to get past the more obvious gotchas.

Problem statement: 

• You are given a directed acyclic graph (DAG) with n nodes numbered from 0 to n-1.
• The graph is given as an adjacency list: graph[i] = list of nodes you can go to directly from node i.
• Each node has a value given in array values[0..n-1].
• Return the maximum sum of node values you can collect by following any path in the graph

Example:

int[] values = [1, -2, 3, 4];
int[][] graph = [[1, 2], [3], [3], []];

This problem is deceptive for multiple reasons:

• It looks like "longest path" so people think NP-hard
• But it's a DAG, so longest path is solvable in linear time
• Many people waste time trying brute force / backtracking / permutations
• Many try to keep track of visited nodes unnecessarily (not needed in DAG)
• The correct insight is subtle for many: "longest path ending at each node" is easy to compute with DP + DFS
• Negative values make greedy impossible
• Large n forbids O(n²) solutions
• You must memoize properly or you'll exceed the accepted time limit
• The DP state "maximum path ending at node X" is not the first thing most people think of

The post is long enough already, so here is the code:

int[] values = [1, -2, 3, 4];
int[][] graph = [[1, 2], [3], [3], []];

int MaxPathSum(int[] values, IList<IList<int>> graph)
{
    var n = values.Length;
    var memo = new int?[n];   // longest path ending at i

    var globalMax = int.MinValue;

    for (var i = 0; i < n; i++)
    {
        globalMax = Math.Max(globalMax, Dfs(i, values, graph, memo));
    }

    return globalMax;
}

int Dfs(int node, int[] values, IList<IList<int>> graph, int?[] memo)
{
    if (memo[node].HasValue)
        return memo[node].Value;

    var best = values[node];   // just this node

    foreach (var nei in graph[node])
    {
        // take the best path ending at nei + current node
        int candidate = values[node] + Dfs(nei, values, graph, memo);
        best = Math.Max(best, candidate);
    }

    memo[node] = best;
    return best;
}

Console.WriteLine(MaxPathSum(values, graph));

A bonus in this implementation is methods using IList and accepting arrays. You've forgotten that arrays implement IList, didn't you?

Example - Topological sort (Course Schedule)

Another very common use of DFS on Directed Acyclic Graphs (DAGs) is Topological sorting, producing a linear ordering of nodes such that for every directed edge u -> v, node u comes before node v in the ordering.

Use it when you need to process tasks, courses, or build steps in the correct dependency order (build systems, task scheduling, course prerequisites, etc.). If the graph has a cycle, a valid order is impossible.

The DFS trick is simple: we perform the same traversal as in Example 3 (cycle detection), but we also record each node after all its children have been processed (post-order). When we reverse that list we get the topological order. The three-state visited array (0 = unvisited, 1 = visiting, 2 = visited) detects cycles exactly like before.

Let’s see it in action with the classic Course Schedule problem.

Problem statement: There are numCourses courses you have to take and you are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai.  Return true if you can finish all courses (i.e. there is a valid topological order), otherwise false.

Here’s the complete solution:

bool CanFinish(int numCourses, int[][] prerequisites)
{
    // Build adjacency list: graph[u] contains all courses that depend on u
    var graph = new List<int>[numCourses];
    for (var i = 0; i < numCourses; i++)
        graph[i] = [];

    foreach (var p in prerequisites)
    {
        graph[p[1]].Add(p[0]); // p[1] -> p[0] (prereq before course)
    }

    var visited = new int[numCourses]; // 0 unvisited, 1 visiting, 2 visited
    var order = new List<int>();       // will store post-order (reverse topo)

    for (var i = 0; i < numCourses; i++)
    {
        if (visited[i] == 0 && !Dfs(i, graph, visited, order))
            return false;
    }

    // If we reached here there is no cycle -> valid topological order exists
    // order is in reverse; if you need the actual order just do order.Reverse()
    return true;
}

bool Dfs(int node, List<int>[] graph, int[] visited, List<int> order)
{
    visited[node] = 1; // visiting (gray)

    foreach (var nei in graph[node])
    {
        if (visited[nei] == 1) return false; // cycle!
        if (visited[nei] == 0 && !Dfs(nei, graph, visited, order))
            return false;
    }

    visited[node] = 2; // visited (black)
    order.Add(node);   // record finishing time
    return true;
}

var numCourses = 4;
int[][] prerequisites = [
    [1, 0],
    [2, 0],
    [3, 1],
    [3, 2]
];

Console.WriteLine(CanFinish(numCourses, prerequisites)); // true

Complexity

Time: O(V + E) - we visit every node and edge exactly once.

Space: O(V) for the visited array, recursion stack, and adjacency list.

Notice how this re-uses the exact cycle-detection pattern from Example 3. The only new thing is pushing nodes to the order list after their dependencies are fully explored. If you want the actual ordering just return order reversed at the end.th extra preprocessing.

This technique is extremely common in system-design interviews too (task dependency graphs, build pipelines, etc.).

Conclusion

Graph theory is a very large and important category in computer science, so explaining all of it simply in a post or two is impossible. But I hope I've clarified a lot of stuff related to the field, at least in regards to interview questions. DFS is one of the most versatile tools in your interview toolbox. Once you get comfortable with the recursive pattern (visit node -> recurse on children/neighbors -> backtrack), you'll start seeing it everywhere: trees, graphs, backtracking, path problems, cycle detection, and more.

Intro

  At the moment I am looking for a job, so I was forced to enter the world of technical interviews and the weird places like Hackerrank and Leetcode. They absolutely suck, but they have some interesting problems that generations of developers have tried to solve. In my mind there are two kinds of problems: the ones that can be solved with a little thinking and the ones that require some sort of a priori computer science knowledge. Since I have not had a formal software development education and since no matter how many jobs I've had, they always ask me about algorithms, but then I never have to use them, the ones requiring such esoterics always scare me.

  Compounding this is the fact that documentation about such concepts is made for people in computer science courses by people teaching computer science courses, which are usually some kind of math people at heart. 90% of the effort of understanding any of that is reading through their obtuse formalizations. So I've decided I would help myself and other fellow programmers understand these concepts in a way that can be understood.

  In my research into these coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall 

  Today I will be covering Dynamic Programming (DP), which solves optimizations with overlapping subproblems. And no, I will not be making crass jokes about the abbreviation.

When to use Dynamic Programming

  Recognize a problem that can be solved with DP by these signs:

• it is too slow to solve with brute force
• the solution for the problem can be built from best solutions to subproblems
• the same subproblems (yielding the same result) need solving multiple times

Example - Fibonacci

  The poster problem for this category is Fibonacci numbers. It's funny, but when I first learned about this series of numbers I was in school, and I knew more math than programming. When you start with the mathematical definition of the Fibonacci function, the naive computer implementation is terrible, so learning Dynamic Programming with this seems reasonable. But after decades away from school, when presented with the problem, the implementation cannot be more different.

  Here is the general definition: a function F(x) which for 0 and 1 returns a defined number, then for any other x, it is computed as F(x-1)+F(x-2). Let's write this in C#, just so you see how silly it is:

int F(int x)
{
    if (x == 0) return 0;
    if (x == 1) return 1;
    return F(x - 1) + F(x - 2);
}

Readable, functional, faithful to the mathematical function, but completely inefficient. Let's add a counter to see how many times this function gets executed:

(int result,int count) F(int x)
{
    if (x == 0) return (0,1);
    if (x == 1) return (1,1);
    var (r1, c1) = F(x - 1);
    var (r2, c2) = F(x - 2);
    return (r1+r2, c1 + c2);
}

// F(10) returns (55, 89)
// F(20) returns (6765, 10946)
// F(30) returns (832040, 1346269)

Now let's think about the problem as a software developer. The client needs the last value of a series of numbers that start with 0, 1, and then add the last two numbers in the series to get the next one. It's an iteration function. The result, when you think about it in these terms, becomes obvious:

// loop solution
(int result, int count) F(int x)
{
    if (x == 0) return (0, 1);
    if (x == 1) return (1, 1);
    var (x1,x2) = (0,1);
    var c = 1;
    for (int i = 2; i <= x; i++)
    {
        (x1,x2) = (x2, x1 + x2);
        c++;
    }
    return (x2, c);
}

// F(30) returns (832040, 30)

So we optimized a function to run 30 times instead of 1.35 million times. Quite an improvement, and all it took was thinking like a software engineer, not like a math geek. This type of solution is called "bottom up dynamic programming" or "tabulation" and is usually the most efficient one. However, there is another solution called "top-down dynamic programming" or "memoization" which is what some computer science guys expect. Let's take a look:

var memo = new Dictionary<int, int>();

int F(int n)
{
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];

    memo[n] = F(n - 1) + F(n - 2);
    return memo[n];
}

Here we used the naive structure of the code, preserving the math semantics, but cached the results of the function for known values. This is actually the kind of stuff they expect from you, even if it's clearly less efficient! Because that's what they teach in school as an example. It's the printing of "hello, world!" and the unit test for a calculator class that only knows how to add two numbers all over again.

Yet, there is a very good reason to use memoization sometimes and that is if you plan to run the function multiple times using the same dictionary. You are basically constructing a table of key/value pairs and using that to cache the results. An even more efficient implementation - in this case - is using a `List<int>` rather than a dictionary, since the keys are sequential integers. Since you know you are going to need all values from 0 to n to calculate F(n), then you can already create/expand the list to have N items. 

They will also ask about complexity or the "Big O notation". If you don't know what that is, it's a fancy notation for describing the magnitude of time and space used by the algorithm. The naive implementation is O(Fibonacci(n+1)) in time, which is funny, as it describes the complexity with the function you're supposed to implement. The tabulation and the memoization versions are O(n) in time, or "linear", the complexity increases linearly with n. The space complexity is theoretically O(1) or "constant" for the naive and the tabulation version, while the memo version is O(n) because we store all n values in the dictionary with n keys..

I said theoretically, because practically, for the naive and memo versions, there is also extra overhead because of the recursive nature of the implementation. The data for each execution will be stored in the stack, which adds another O(n) in space and is also limited in size. Learn about Stack vs. Heap in programming and well as the Big O notation separately, if you want to drill down.

Theory

The definition sounds like this: Dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time. 

Two ways to do it:

• Top-down + Memoization - Start from the big problem, recurse down, but cache results in a dictionary/array so each unique subproblem is solved only once.
• Bottom-up + Tabulation - Start from the smallest subproblems, build a table iteratively up to the full problem. Usually uses less stack and is faster in practice.

The memoization approach is often easier and more natural, but every problem that can be solved with memoization can usually be solved with tabulation as well. If a problem has a correct recursive formulation with overlapping subproblems, you can always rewrite it as an iterative bottom-up solution by carefully filling a table (or multiple tables) in the right dependency order. The vast majority of DP problems taught and asked in interviews (Fibonacci, knapsack, coin change, longest common subsequence (LCS), edit distance, matrix chain multiplication, longest increasing subsequence, house robber, word break, regex matching, etc.) have clean bottom-up solutions.

Common Pitfalls & Trade-Offs

• Initialize dp correctly! (Often dp[0]=0 or 1, others int.MaxValue or -1)
• Watch for off-by-one (array size amount+1)
• Memo dict vs array: array/list is faster and uses less memory for integer keys 0..N
• Space: top-down can use O(N) stack + O(N) memo; bottom-up usually just O(N)
• When amount N is huge (>10⁵ - 10⁶), DP might not fit - look for math or greedy instead

Example - Coin change (minimum coins)

Let's take another example, the exact change coin problem. 

Problem: Given coins[] of different denominations and int amount, return the fewest coins needed to make exactly amount. Infinite supply of each coin. If impossible, return -1.

The memoization solution comes easier, because it's an iterative fix of the naive implementation:

Dictionary<int, List<int>?> memo = []; // memo: Memoization dictionary to store results for subproblems

IList<int> CoinChange(int[] coins, int amount)
{
    var result = FindMinCoins(coins, amount);
    return result ?? [];
}

List<int>? FindMinCoins(int[] coins, int remaining)
{
    if (remaining == 0)
        return [];

    if (remaining < 0)
        return null;

    if (memo.ContainsKey(remaining)) // memo: Check if the result for this amount is already computed
        return memo[remaining];

    List<int>? best = null;

    foreach (var coin in coins)
    {
        var subResult = FindMinCoins(coins, remaining - coin);
        if (subResult != null)
        {
            var candidate = new List<int>(subResult) { coin };
            if (best == null || candidate.Count < best.Count)
            {
                best = candidate;
            }
        }
    }

    memo[remaining] = best; // memo: Store the computed result in the memoization dictionary
    return best;
}

var result = CoinChange([1, 5, 10, 25], 30);
Console.WriteLine("["+string.Join(", ", result)+"]"); // returns [25, 5]

The lines with "memo:" comments are the difference between the naive and memoized versions.

So what did we do here? We started with the total amount of money and tried every single coin. Once a coin is used, the amount decreases with the value of the coin. If the amount if negative, we overspent and return null for an unusable solution. If the amount is 0, then we return an empty array and stop the recursive processing. If the amount is larger than zero, we now have to solve the exact same problem, but with a smaller amount.

Let's see the tabulation solution.

IList<int> CoinChange(int[] coins, int amount)
{
    if (amount == 0) return [];

    var dp = new int[amount + 1];     // dp[i] will hold the minimum number of coins needed for amount i
    var prev = new int[amount + 1];   // to reconstruct the solution

    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;

    for (var i = 1; i <= amount; i++)
    {
        foreach (var coin in coins)
        {
            if (i >= coin && dp[i - coin] != int.MaxValue)
            {
                var candidate = dp[i - coin] + 1;
                if (candidate < dp[i])
                {
                    dp[i] = candidate;
                    prev[i] = coin;          // remember which coin we used
                }
            }
        }
    }

    if (dp[amount] == int.MaxValue)
        return [];          // impossible

    // Reconstruct the list of coins
    List<int> result = [];
    var current = amount;

    while (current > 0)
    {
        var coin = prev[current];
        result.Add(coin);
        current -= coin;
    }

    return result;
}

var result = CoinChange([1, 5, 10, 25], 30);
Console.WriteLine("["+string.Join(", ", result)+"]"); // returns [25, 5]

A lot more daunting, but simple once you "get it":

• We store everything in arrays, where the index is the amount. I guess one could use dictionaries instead, but for small amounts - like the ones used in interview questions - the size of the array is less important than the efficiency of execution of the index in a static array.
• We fill the array with int.MaxValue, so that any other value is preferable
• We use the prev array to store the coin we last used for every calculation - smart solution to allow us to reconstruct the list of coins
• when we just calculate and store the number of coins for each amount up to the desired amount.

It's just like the Fibonacci thing, only more complicated.

Conclusion

Use Dynamic Programming when a problem can be split into smaller pieces that get executed multiple times, yielding the same result each time. The top down approach is more intuitive, but the bottom up approach is usually more efficient.

  The Bell Jar of the title is a metaphor for depression and societal pressure. Sylvia Plath writes this semi-autobiographical book about her breakdown and suicide attempt a decade earlier, then promptly commits suicide a bit later.

  The writing is very good, very introspective. The 1979 movie doesn't do justice to the book especially because it fails to convey the inner life of the main character, which the book excels at. It was a spooky read for me, as it describes in great detail how women - particularly in a social context, where outwardly they project something completely different - think inwardly, as well as how depression feels: the anhedonia, the mental dissociation with reality, the time distortion and incessant rumination. Depictions of early psychiatric practices from the time don't make the read any easier.

  I compare it with My Year of Rest and Relaxation, The Stranger and Almost Human. It's also an informative glimpse of '50s American society, with some feminist overtones that feel honest.

  Bottom line: a good book, but you have to have the mood and stomach for this kind of story. If you are studying psychology it's good material for depression.

  A Line in the World: A Year on the North Sea Coast is a sort of a literary travelogue, describing a very subjective experience of the Danish coast. It has little touristic information, though, mostly focusing on feelings, art, history, childhood memories, feminist musings and the like. It does bring everything into beautiful context, but in the end it felt like there was mostly context.

  There are stories about proud British ships brought down by the might of the sea, World War II stories from the German occupation, present stories from the German tourist occupation, stories about the stoic and taciturn Danes, former Vikings, now just disgruntled folk, but still doing the shield wall in front of any outsider people or ideas. There are stories about hallucinations, described beautifully as places remembering things if the right people are present. Also childhood memories and experiences. A lot of cool stuff.

  I liked the book, but if it weren't so mercifully short, I would probably not enjoyed the experience. Reading it it's not like you're there there, it's like you're in Dorthe Nors' head, who just happens to be in Denmark, travelling the coast. The writing is poetic, full of form and feeling.

  However, not everything was perfect. I don't feel like I learned anything useful about the Danish coast! In that regard, it was more a love (is it love? can't tell) letter to being Danish than a travel book. And it certainly didn't feel like a year, only fragmented anecdotes.

  Bottom line: Perhaps more fun to Dorthe Nors fans than random people like myself, but a bad book, but wondering who is it for.

  The book starts with a pretty cruel scene: some magical dude comes and kills the mother and father of a family of five and kidnaps the three female children to the land of the Fae. And then switches years later when the girls are in school, being tormented by bullies and being raised by the killer of their parents. Then stuff happens, where one of the girls takes initiative and changes the very workings of the realm after being trained for a few days and falling in love.

  Yes, The Cruel Prince is a silly YA novel and it should mostly appeal to girls. There are no logical reasons why people or fae would act the way they do once our heroine decides to take action other than to make the story go forward. But Holly Black's writing style is solid and it carries the story until the book ends. I've listened to the whole thing on an international flight and I have to say that, for that context, it was a perfect book.

  Bottom line: I won't continue to read the series or recommend the book, but I don't regret having read it.

  

Intro

So we've been on a two week vacation in Africa, starting with Kenya, doing safaris through Tanzania and then flying to Zanzibar for some relaxation. Overall it has been great, with small hiccups, and this is the post that resulted, so enjoy!

The region

Kenya and Tanzania share the same language and approximately the same culture. People from both have said that the people want a joining which is hindered by politics. Tanzania itself is a republic created by the unification of Tanganyika and Zanzibar. However, from my perspective, there are big differences between the three regions, even if the borders between them are pretty much random lines drawn by the British or other colonizers.

A tip driven culture, they expect tips for everything after volunteering to do things no one asked them to do, like carrying bags or doing random welcoming gestures of apparent kindness. We never knew how much to tip and who, so the reactions we got cycled between annoyance and reverent gracefulness, sometimes from the same people.

Tanzania has more food and less economic inequality, but a slower economy and a cheaper standard of living compared to Kenya. However, I've not seen the squalor and apparent lack of self esteem that I saw in Kenya. Tanzanian people are proud of their first president, who attempted to build the nation and keep it safe. An educated man, he came with a political ideology known as Ujamaa, a form of African socialism. For that reason, their houses are neat, no matter how cheap and they believe in the future of their nation. Conversely, in Kenya the poor are really poor and the rich are way richer, their houses are just hobbled together and the people sleeping on the side of the road are a lot more there than in Tanzania.

I won't get into the history or politics or whatever, though. The important part is that people are mostly similar and they speak Swahili in all three of these regions, written with Latin letters. Many African tribes live peacefully within these borders, with the largest being the Maasai.

Also, the climate is not that different from parts of Europe. We went there in January, so summer in the Southern hemisphere, but the temperature rarely went over 30 on the most heated days. Meanwhile, nights were often chilly. They never get negative temperatures at ground level and considering I was coming from a city where nights had -15C at that time and that can easily get to 40C during the summer, I felt it was quite comfortable.

For me, there were two separate legs of the journey, one was the Masai Mara/Serengeti safaris and the other was the Zanzibar island. In one we woke up before the sun rose to get something to eat and then be driven until evening in the natural reserve to see the landscape and animals and the other was pure lazing around and swim in the pool. Yet by far the most satisfying was the safari.

Getting there

In order to get from my home country of Romania to Kenya, we had to take two flights, one to Doha and another to Nairobi. Both were Qatar Airways which I have to say has not disappointed as an airline. Planes were comfortable even for my long legs and the flight attendants very professional. But it was about 500 Euros per person and it took a lot of time.

The Hamas International Airport is a huge place, including all kinds of shops, restaurants and even an Orchard with trees and flowers and places to lay down and sleep in the (artificial) sound of birds singing.

Once we got to Nairobi we found the first obstacle: language. I consider myself a pretty good English speaker, but apparently I am not very good at hearing it. Because when we went through customs there was a scary Black man there telling me "put right hand fofinga the'e", pointing towards a sensor. I've put my forefinger on the sensor and the guy got angry. "Fo fo fo!". I thought that "fo" must be "no" in Swahili and placed my forefinger on the sensor again. Guy got agitated and started Nazi-saluting in a frenzy shouting "Fo fo fo fo!". Jesus, what was I doing wrong? My wife comes from behind and says "Honey, he means four fingers".

And it wasn't the only time it happened. Later on we went to a restaurant and the waiter started to make conversation. I told him I am Romanian and this is how the dialogue continued:

• "Oh, I have a friend from Romahnia. He's pasta"
• "He's passed? I am so sorry!"
• "Ah, no, he's peachy! Cha-cha pasta"
• [me confused] "Oooh-kay. Glad he is well"

My wife comes and says "Honey, he means a church pastor, he is preaching".

I mean, even our safari driver/guide, when I asked him what a secretary bird eats, he told me "Snacks". Well, doesn't everybody?! He meant "snakes". OK, that's the end of the comedic monologue. I won't inflict much more of my dad humor on you further on, so keep reading.

From the airport we got picked up by our first driver/guide who got us to the Masai Mara park, where we were to go on safari. Driving in Kenya and Tanzania is insane! Most cars are Toyota or something similar, a lot of cheap Chinese motorcycles and big trucks that I didn't recognize the brand for, but they are all really old. The average citizen cannot afford a second hand car, and most can't even dream of a new one. If you see a new car on their roads it is usually a government official or some company car. Trucks spew smoke like they're on fire, especially if they have to go on a hill, and old cars also look like hazards, especially with the way people are driving there. Occasionally you may see a "bus" that has a lot of people inside and some hanging over the back of it, only part of their arms being "inside" the bus.

In Europe (and I expect in other developed places) driving is constrained by clear rules which are enforced by authorities. That gives one some consistency of expectations and the luxury of badmouthing or even honking at other drivers. Not there! Almost no one honks (and I expect no one bothers to complain on someone else's style) because there are absolutely no rules. Except, maybe, to never ever stop. What in Romania would be considered a two lane road with each one in a different sense, for them it's more like five virtual lanes. They drive the British way, on the left side of the road, with the steering wheel on the right. If a car is in front of them and moving too slow, they just overtake with little consideration. Meanwhile, someone might feel like you are not overtaking fast enough, so they overtake you while you are overtaking. And in all that time, there are small motorcycles that can come from either direction on any side of the road.

But guess what? I don't think they have that much more road accidents. People don't have the sheltered expectations that the other drivers will follow any rules and have the freedom to drive as they want as well. Their actions have very real and direct consequences that depend entirely on them assuming the responsibility of taking those actions. It feels free and adult. Until the first crash, obviously, but I am just telling you my impression. After fearing for our lives for an hour or so, we kind of got used to it.

It probably helped that our driver was very careful and considerate with the car - which was obviously not his - and with us, even while driving like this.

Oh, and they absolutely love speed bumps, even on the compacted dirt roads, which are probably most of them. Every school has a few of them in front. And there are a lot of schools in Kenya, run by various Christian organizations. Imagine the people that hang on to the outside of a bus, completely trusting the driver will not speed over any of them, throwing them off.

Anyway, the drive to Masai Mara and similar other drives in Tanzania were the only way we would see how most people lived. Houses are small, made of dry soil and wood branches, some times coruscated tin sheets, other times whatever people found to make their houses of. There is no pattern, no homogeneity and there is garbage everywhere. On the side of the road you see all kinds of small business, but also people laying down or sleeping on the grass. When I asked about them, the driver just said "they are waiting for a job".

The weird English they retained from their colonizers is also funny. A farmacist is a chemist, an Internet place is a cyber and apparently the name Ebenezer is very common. I was imagining a small Kenyan old grandma appearing next to me saying "Welcome to Mama Ebenezer's Cyba Chemist!" "The what?!" "Yees, we have free rooms!". I've seen a lot of "hotels" where were just random one story buildings with signs on them, with "star" being a popular motif in their naming. "The star hotel", for example. I thought it would be funny to name it the five star hotel and just a few hours later I've seen a "Five star hotel" which was just like any other star hotels I've seen that far.

A lot of people still live in the old ways, by raising goats, sheep, chicken and sometimes cows, and you can see those just eating around the garbage strewn on the sides of the road. That's the bonus road lane, I guess.

Masai Mara/Serengeti

The first things you notice when you get to the reservation are animals. You see some even before you get there, but inside the reservation there are trees and birds and open spaces that are completely protected from man.

It's worth saying that hunting or domesticating any wild animal, regarding on where it is found, is illegal in Kenya and Tanzania. You cannot just shoot an antelope and eat it or raise zebras in your back yard. There are exceptions where specific tribes have this as part of their tradition. And I do believe those exceptions are not part of the law, just people turn a blind eye to this kind of thing.

A notable exception is the Guinea fowl, colorful funny birds that are related to chickens and which I was told are allowed to be raised just like normal yard birds.

Back to the Masai Mara/Serengeti area, I have to say that to have such a huge place protected from human development and hunting is a great achievement! I know that it's probably something that was convenient at the moment and it will survive until some Trump hears it holds valuable resources underground, but as long as it lasts, it's so very nice. I wish we had stuff like that in Europe. Perhaps only in Russia can we get something similar and with the politics of the place, I doubt we'll get there. Also, while the areas you can go on a safari in are huge, they are just a very small portion of the Serengeti ecosystem.

The Masai Mara name comes from the name of the Maasai tribe and from the word for "spotted" in their language. It thus translates to "the spotted land of the Maasai", called so because of the vast flat plains speckled with the occasional tree, termite mound or shrub.

With the careful guidance of our driver, we saw a lot of animals. The plant life is pretty unimpressive, though. There are some cool trees, but few types and far between, while the small plants are mostly grass and shrubs, with just a few flowering plants.

My favorite animal was, of course, the lord of the savanna, the uncontested champion of smarts, beauty and grace: the warthog. Just like me, he avoided people and was constantly searching for Wi-Fi. Even if the Swahili name for it is ngiri, most people there called it pumba, which means silly, foolish or simple. Apparently, they are very forgetful (just like I am) and even if they spot a predator and run, five minutes later they forget and go back to the same place the predator never left and just got better hiding.

The big cats were beautiful: the lion, the leopard, the cheetah. Our guide told us that lions are considered kings not because they are smartest, most beautiful or more powerful, but because of their attitude, fearless and confident, like everything just naturally belongs to them. I felt like they really put the lion in "lying around".

We've also seen another cat that looked like a serval, but it wasn't according to our guide. He told us the name, but I forgot it. Really beautiful fur patterns, but the photo is not that good.

Hyenas are very smart. They hunt in packs, but then they tear their capture apart and eat separately. They are also considered very cruel, since they don't use suffocation to kill their prey, instead eating it alive until it dies of blood loss. I also considered them cute, but then you know I have a weird sense of aesthetics.

The only canine we've had the privilege to spot was the black-backed jackal, a fox sized and looking animal that always kept watch for something bigger trying to eat it.

Then there are the elephants, of course, which I've seen a lot of. They live up to 70 years old and move slowly and carefully, grabbing grass with their trunks and eating it. They have wise yellow eyes and every time we came near them, they were never afraid, but always moved just the right way in order to put themselves between us and their small ones.

We've seen rhinos as well, but only from afar. There are only black rhinos in the reserve. The white/black name stuck, but it's a mistake, since the defining difference between them is the snout and mouth, not the skin. The "black rhino" name comes from "the black-mouthed rhino". Because they are very solitary animals, their numbers are dwindling and you rarely can see one.

Hippos are there as well. They are considered extremely dangerous, since they are very territorial and very violent when attacking. They sit in the water all day long and go out to graze in the night. They are so efficient at eating grass that they leave these meandering narrow paths behind them where there is only dirt and absolutely no plant.

I don't know how dangerous they were, but for sure there were stinky as hell. They sit in the same stagnant water where they defecate continuously. People say that the defecation is to tell other hippos where their territory is and keep them away. I say they keep everything away with that awful stink.

And from far away we've also seen crocodiles. In the water you see maybe a small shadow under the surface, but on the ground they bask in the sun in all of their three meter length glory. I have the photograph of these two chatting very very very slowly with each other.

Then there are the giraffes, three species of them, but only two in the area: the Masai giraffe and the Rothschild's giraffe, and we've seen them both. Really graceful animals, until they get scared and start running, which felt like they were going to fall and break apart at any moment. It never happened, though.

Zebras are everywhere, as are African buffaloes. A lot of types of grazing antelopes/deer species as well. It would take too long to list them all. I liked the Dik-dik, which is really small and cute. You can imagine my confusion when the guide told us the name the first time and I heard it wrong.

We passed through a migrating group of hundred of thousands of wildebeest and zebras going through the Great Migration to the south. It was amazing to see. A lot of flies, though. When the migration is in full swing, there are millions of these animals in the same place. Buffaloes have good smell and zebras have good eyes, so they migrate together to detect predators better. You often see two zebras one next to each other, but oriented in different directions, resting their heads on the ass of the other. This way they rest and watch both directions for danger.

We saw baboons as well, they are somewhat silly and cute at the same time, until they yawn and they show long sharp canines. Apparently they are "cheeky bastards" and if you let them, they will come into your house and cause havoc. I've always seen them in relatively large families. Not aggressive by default, they can become dangerous if they feel threatened.

At one time I was trying to take a photo of some tribe of baboons hanging on an antenna when I noticed one that was sitting right next to me, a big male. I was on foot, since we were in a gas shop in the Serengeti. Didn't have the guts to look him in the eyes and take a photo, so I only got his butt.

Similarly, there were vervet monkeys, nicer fur but smaller in size. Usually in smaller groups or even just couples, they are beautiful, but apprehensive.

And last, but not least, the mongooses and the hyrax. Quite different animals, but we saw them at the same time. Banded mongooses are striped and always in large groups, the dwarf mongoose (or maybe some other) we've only seen when coming out of their burrow in an abandoned termite mound. The hyrax is a rodent-looking creature, but more related to elephants instead.

Also, birds. Since they were usually small and far away, I didn't catalog them, but they were many and beautiful, ranging from half finger length to huge eagles and vultures. We saw flamingoes. Ostriches, too.

More getting there

The safari car - a specially made Toyota Safari Land Cruiser - drove us from airport to Masai Mara, the lodge there, then on safari, then to the Tanzanian border. Another driver got us from there, because different drivers are licensed for different countries. The Masai Mara and Serengeti areas are basically the same thing, only the first is in Kenya while the other is in Tanzania.

At the border the officer there took a glance at our document and threw them back dismissively "no Visa!". We panicked a little, we learned we had to pay 50 USD on a Visa, filled out the form, only to the guy to take a second look and say "Ah, you're from Romania, no Visa needed".

Then we drove to the Serengeti, even faster and more insanely dangerous than before. The Serengeti name means "endless sea" because it's like a sea of grass. It's impressive to stop in places where any direction you look you only see grass (and occasional trees) to the horizon, then a blue sky with fluffy white clouds. It looks just like the Windows default desktop background, only better.

Again we were hosted in a lodge, spent the next days on full day safaris, went to Ngorongoro, which is an old volcanic crater where animals are a lot more calm and the weather more wet. The surface of the crater is 380 squared kilometers.

Finally we got to the Kilimanjaro International Airport in Arusha from where we were supposed to get a one hour flight to Zanzibar with Air Tanzania. Man, what a shit show!

First of all, the plane schedule had been changed just before we left Romania. We knew that and that it means we had to leave five hours later, but we had nowhere to wait except in the airport. When we got there, we had to remove all things from the pockets and our shoes (which were worn non stop through six days of safari) and put them on the scanner belt *before* we entered the airport. We would have to do the same when boarding the plane, too.

But when we got there, we realized we cannot check in. I had previously tried to check-in online, but the portal asked for a code I didn't have and it seemed like it was designed to be used by airport personnel rather than passengers. At the airport, the check-in process only started two hours before the plane was scheduled. Yet, at the same time, the restaurant and any snack or drink dispenser were after the security gate.

The solution? African way, of course, I had to bribe an airport officer to order us the food and bring it through the check in point. There was also a toilet there, but whenever we were getting close a "welcoming attendant" was shouting "Jambo jambo!" at you (which means hello) and inviting you in. It felt more like "welcome to my parlour, said the spider to the fly" than "go on and tip me" which is probably what he meant. Anyway, we chose to hold it in.

Another fun thing, the flight did not appear on the departures list on the airport monitor. After asking around some really uninformed people, I got to learn I could just ask in the Air Tanzania office which was outside the airport. Could I just exit and come back on? The security guard said that it was perfectly OK. So I went there, where three people were lazing around doing absolutely nothing, and asked them. They answered the plane was on time, that their colleagues in the airport missed updating the monitor and that they were going to tell them to do that immediately. Oh, good!

And of course I had to get out of my shoes, belt and empty my pockets when I got back in the airport, 3 minutes later. And of course that until the check-in opened, three hours later, the departures monitor was not updated with our Air Tanzania flight. It was updated with a similar Air Tanzania flight, though, which was leaving another six hours later, which of course, filled us with confidence. But I am not bitter, I take the higher road, hakuna matata and all that. Motherfuckers!

At the Zanzibar airport, at midnight, our transfer car did not arrive. Chat on the website designed to reach the driver did nothing, calls - from some guy outside the airport because I had no roaming in Zanzibar - to the dispatcher of the company went unanswered. In the end we just took a taxi from a helpful guy. The rideshare driver apologized the next day and promised to come and bring us the money we gave the taxi. But then asked for the voucher code, which we refused to give him until we got the money. Never heard from the guy again.

So the whole "getting to Zanzibar" thing was fun. Not bitter, though.

Zanzibar

Our hotel had small funny huts, a pool with a swim to bar, was next to the ocean, relatively good food - the safari lodges were better - so we got a well deserved relaxing rest.

I was there with the wife, so of course I had to drink less and visit stuff more. But I am not bitter. I take the higher road. It was the right thing to do.

We went to the sea immediately. Such fine white sand, almost like clay, and the tides were phenomenal, the way the waves were coming right close to the hotel and a few hours later you could walk were the water was deep before. But we could not enjoy it much because the beach was infested with jambo-jambos trying to make conversation and sell you things.

Then there were two things we wanted to visit: a Zanzibar spice plantation and Stone Town, where there was also the Freddy Mercury house. I am a big fan of Queen, so it had to be done. So we spoke with a tour agent right there in the hotel who offered us a drive to a spice plantation, a guide there, then a ride back for 75 USD. And my wife refused, but we talked to a guy there who recommended us another driver. I told him that we were offered 75 USD and he immediately called a guy and negotiated a driver, a guide, the spice plantation, Stone Town, all in 80 USD. I guess I could have said 50 USD and he would have sold me the same for 55 or something, but I didn't really mind the price.

The plantation was fun, it was more of a small orchard than a sprawling plantation as we imagined. We saw how they grow pepper, cardamom, ginger, turmeric, dragon fruit, jackfruit, durian, bread fruit, lychee, bananas, some stuff African women use as lipstick and Maasai put on their forehead like the Indians, mandarins, vanilla, cloves, cinnamon, aloe vera, chilly peppers, Zanzibar apples - which are not apples, coconuts and so on.

Stone City was a really hot narrow street place like you see in many a tourist place. Took some pictures, including the outside of the Mercury House. Apparently, since he was Indian-Iranian and he only stayed in Zanzibar when he was a child, people there don't feel Freddy was one of theirs and the "house" is just a place with some pictures, so we didn't get in. We went to a market there, which was pretty claustrophobic. A drunken guy came to us and started repeating he is "Aaaffffrican Aaarrtist". So just like home.

But there were a lot of cats! In Romania there are a lot of stray cats and people have a lot of dogs. Outside of Bucharest you see a lot of stray dogs, too. Not in Kenya and Tanzania until we got to Stone Town. They were laying around, sedated by the sun, you could just go to them and pet them and they wouldn't even move.

Also, we went to the *former* slave market, emphasis theirs, as if we wanted to get there to buy a little African child or a slave for home. Not much to see except a dark damp cellar where stone slabs held the role of beds and the space between them as toilet. The small holes in the walls served as "windows" and toilet flushers when the rains came and flooded the room.

There was a sculpture there that moved me. Four black silhouettes, same chain on their necks, and a fifth, also black, but unchained. The supervisor, also a slave, but "middle management".

I was reminded of so many movies decrying slavery that present some angry aggressive rapist as the master, when it would me much more impactful - and probably closer to the truth - to present them as some calm speaking polite gentleman who has only kind words to speak to slaves, except for when they misbehave, so they sorrowfully instruct the supervisor to administer punishment. And if the supervisor misbehaves, just as politely and following "the rules" they demote the supervisor to a mere slave and promote another, perhaps the one that was viciously punished the day before.

Not different from a modern corporation, I guess. But I am not bitter. I take the high road. At least until I find a job... As I was saying to one of the people I talked to there, rich people don't hurt poor people, they hire other poor people to do it.

We also went for snorkeling! I came back to the boat three minutes later. I heard it was a lot of fun for all the other people. Nuff said.

The food

We never went to eat with the locals, as we were always pampered in a lodge or hotel that was made for tourists. The food was also for tourists. I understand that the regional recipe to enjoy is Nyama Choma - basically grilled meat. They eat it from the bone, taken together with ugali - a white corn polenta specific to the region - and with kachumbari - tomato onion chilly salad - or a blanched spinach like plant (sukuma wiki). It was pretty good at the hotel restaurant, but I ate it with a fork, not with the hand as traditional.

Are the fruits amazing and so different from what you get from the supermarket at home? Sometimes. But mostly no. It's not like you can eat papaya daily or find nice pineapples in Romania, so in that sense it's great, but at least from the restaurant food we've had, fruits are fruits. Perhaps if you take them from the local markets, things are different, but how much can they be, really?

Health and hygiene

I purposefully left this at the end, because I know you would want to know, but since it's health advice, I can't really give it.

What I can tell you is that before going to Africa from Europe, you are being told all kinds of horror stories: malaria, diphtheria, typhoid, yellow fever, hepatitis, sleeping sickness, mosquitoes, tsetse flies, etc. And while some of this might be true, it's increasingly rare in Kenya and Tanzania.

It also depends on whether you are hosted in a "hotel" on the road to Nairobi or a safari lodge. Mosquitoes are there, but in order to infect you with something serious, they have to first sting an infected person then sting you. If you are in a luxury hotel made for foreign tourists that is rather unlikely.

However, we did get vaccinated against the yellow fever - it's mandatory in order to get into Tanzania - and sprayed ourselves with Deet whenever we thought it was required. We also bought - from outside the country - Malarone to preventively treat a possible malaria infection, pills that you have to take daily.

To my very pleasant surprize, there were not many insects in the places we've been to, including the safaris. I was expecting the same thing you get in European plains and forests: a lot of flies and mosquitoes. It was mostly free of them, at least in this period, which marks the end of the dry season. Perhaps during the wet times there are more insects.

On the other hand, in the lodge in Ngorongoro the first thing I asked the reception is what the mosquito situation was and they confidently told me the edge of the caldera is too high for mosquitoes. One minute later I was killing two of them in the bathroom. Mosquitoes, not receptionists.

As for the water, we were given bottled water to drink and to wash our teeth with, but I feel it was mostly to alleviate concerns than from a practical perspective. Maybe in the lodges it was warranted, but in the Zanzibar hotel where you had 3 showers a days and spent most of the time in the pool I doubt the water quality was any worse than at home. Of course, again, it depends where you are.

Conclusion

I recommend everyone to go on an African safari at least once. The animals, the wide plains, the experience of just sitting there (in the car) two meters from sleeping lions. Really great!

And take the lodges, not the camps, even if more expensive. It's worth it for your peace of mind at least.

The Zanzibar hotel experience you can safely skip. I would have probably regretted it if I didn't do it, but now, if I were to return, I would only do the safari, maybe just in the Masai Mara or in the Serengeti, not both, and come back.

Also, considering plane tickets are 2000 EUR for two people at least, it's worth spending enough time there to offset that cost with experience and enjoyment.

While I usually advocate going to a place and living with the locals to really understand it, I can't recommend this for Kenya and Tanzania. They have at least a few decades until they reach a reasonable development level that most Westerners or even East Europeans would consider safe, and that considering they don't have yet a stable region, an African Union or anyone to protect them from themselves and from predators while they grow.

In fact, the opposite is true, with instability and dependence actively being promoted by all major powers West or East. Most Africans dream of becoming protected by and integrated more with Europe. That won't shield them from explotation, but it's their best choice in this insane world.

I felt awkward when meeting with the local population, especially with the tribal people. They made me feel like a colonizer: poor, begging for a bottle of water or a piece of chocolate or a tip, some pushed by law from their lands into others. They are not in reservations, like Native Americans, but they are not free to move anywhere either, having no education that would allow them to blend in with what we call "civilization". Even the people that we interacted with: educated in hospitality schools, speaking English, they had no idea what's outside. They never left their country, rarely watched any movie or series or outside news. They speak the words, but don't understand the memes. In a way, this is good, staying away from the corrupting influence of other cultures, but at the same time it's pointless. I reminded a guy from Zanzibar who was saying that their cultural identity is important, that the same identity was created by a guy who was educated in the UK, went to university in Edinburgh. 

Overall a worthwhile experience that I am glad I had.