Algorithmic Thinking and Complexity

Sometimes you do not binary-search an array index at all. Instead you binary-search an **answer space** such as a capacity, time limit, or threshold, using a feasibility check that flips from false to true exactly once.

Asymptotic notation compares growth rates. **Big-O** gives an eventual upper bound, **Omega** gives a lower bound, and **Theta** means the growth is tightly sandwiched between both.

Mixed runtime questions combine scans, sorts, hash-table operations, and nested loops. Write each phase separately, then simplify to the dominant term.

Backtracking explores a **state space of partial decisions**. The key idea is to build a candidate step by step, detect impossible or completed states early, and undo choices cleanly when a branch cannot lead to a valid answer.

Breadth-first search works on **unweighted** graphs because it explores states in layers of equal edge distance. That layer structure is the interview reason BFS gives shortest-path lengths when every move costs the same.

Binary lifting preprocesses jump pointers so ancestor movement can be decomposed into **powers of two**. The main trick is the same as binary representation: any jump length can be written as a sum of power-of-two jumps.

Binary search works because the search interval maintains an **invariant**: the desired answer is still inside the remaining range. Each comparison must eliminate only the half that is provably impossible, and the boundary update must match the exact question being asked.

Bipartite matching pairs vertices from two sides without reuse. The central progress idea is an **augmenting path**: alternating matched and unmatched edges that increases the matching size by one.

Many classic bit problems rely on what happens to the **lowest set bit**. That viewpoint explains power-of-two checks, efficient bit counting, and several constant-time transformations that show up repeatedly in interviews.

This tranche pushes bit reasoning one step further, then mixes it with asymptotics, graphs, and invariants the way interview questions often do.

A bitmask can represent membership in a small universe using one integer. This lets interviews compress sets, feature flags, visited states, and eligibility rules into fast bitwise operations.

Bitwise operators treat integers as compact boolean vectors. Interview problems use this to test parity, flip flags, cancel duplicates with XOR, and update one bit at a time in constant space.

Developers constantly reason about boolean conditions, feature flags, masks, and low-level binary properties. Discrete math logic becomes practical when you simplify conditions and interpret bitwise operations correctly.

Bridges and articulation points identify where an undirected graph is **fragile**. A bridge is an edge whose removal disconnects the graph; an articulation point is a vertex whose removal does the same.

Binary-search-tree reasoning is about **global range constraints**, not just comparing a node to its direct children. Inorder traversal is sorted precisely because every left subtree stays below the node and every right subtree stays above it.

If each SCC is contracted to one node, the resulting graph is a **DAG**. This condensation DAG captures the one-way flow between strongly connected regions and is often the right object for topological reasoning after SCC decomposition.

Coordinate compression replaces sparse or huge values with a dense rank order while preserving **relative order comparisons**. It is a preprocessing bridge between messy input values and array-based data structures.

A **topological order** lists the vertices of a directed acyclic graph so every edge points forward in the list. DAG thinking shows up in build systems, prerequisite planning, dependency graphs, and many workflow pipelines.

A deque supports insertion and removal at both ends, so it can imitate either a stack or a queue and can also handle patterns that need both. Interview questions use deques when a single-end structure would be too restrictive.

Difference arrays invert the prefix-sum idea: instead of storing cumulative totals directly, they store **where changes begin and end**. After marking update boundaries, one prefix sweep reconstructs the final values.

Memoization and tabulation solve the same recurrence in different directions. Interview questions often ask when one is simpler, when one avoids wasted work, and how iteration order reflects dependencies.

Interview DP questions rarely ask only for a recurrence. They mix state design, dependency order, asymptotics, and correctness traps like double counting or forgetting part of the state.

Dynamic programming starts by choosing a state that remembers exactly the information a smaller subproblem needs. Good state design is usually the difference between a clean recurrence and a confused one.

A recurrence defines a directed graph of dependencies between states. Thinking of DP as a DAG clarifies overlapping subproblems, iteration order, and why cycles are a warning sign.

An Euler-tour-style entry order can flatten a rooted tree so each subtree becomes a **contiguous interval** in an array. That converts many subtree problems into familiar range-query problems.

Fast and slow pointers turn repeated traversal into relative-motion reasoning. The same idea explains finding middle nodes, detecting linked-list cycles, and locating the entry point after a cycle is found.

Point updates in a Fenwick tree climb upward through the indices whose stored partial sums include the changed position. This makes the structure especially useful for dynamic frequency tables and coordinate-compressed counting problems.

Fenwick trees support prefix-sum queries and point updates in `O(log n)` by storing carefully chosen partial sums. The key bit trick is the low bit, which tells how large a range each index is responsible for.

Cycle detection depends on graph type. In undirected graphs, you must ignore the edge back to the parent. In directed graphs, the key signal is whether DFS re-enters a node that is still on the current recursion path.

Many interview problems become easier once you name the **state** and the **moves**. When states become vertices and legal moves become edges, familiar tools like BFS and DFS suddenly apply.

**Breadth-first search** explores layer by layer, while **depth-first search** follows one path deeply before backtracking. Both are core graph tools, and both can be used to discover reachability and connected components.

Greedy algorithms succeed when a **locally optimal step** can be justified as part of some globally optimal solution. Exchange arguments and staying-ahead arguments explain why taking a certain next move never makes the final answer worse.

Many interview grid problems are just implicit graph traversal: each cell is a node, legal moves define edges, and BFS or DFS visits connected components or shortest paths. The main implementation risk is careful neighbor and boundary handling.

Heaps are useful when many sorted or partially ordered sources expose only a few promising next candidates. The heap stores the current **frontier** so you can pop the next best item without materializing every unseen option.

A heap stores items so the **root is always the minimum or maximum** according to a priority rule. It does not fully sort everything, but it lets you update the frontier quickly when you repeatedly need the next best element.

Some interval problems are not about choosing one compatible subset. Instead they ask for the **maximum number of overlapping intervals** at any moment, or equivalently the minimum number of rooms needed to host them all. A min-heap of end times tracks how many intervals are active right now.

For maximizing how many non-overlapping intervals you can keep, the standard greedy rule is to sort by **earliest finishing time** and repeatedly accept the next compatible interval. The reason is that earlier finishes preserve more room for future choices.

Loop invariants explain why iterative algorithms stay correct after every update. Structural induction is the matching proof idea for recursive data structures such as lists and trees.

The lowest common ancestor of two nodes is the **deepest node lying on both root-to-node paths**. LCA problems become easy once you think in terms of path overlap rather than arbitrary tree geometry.

A dummy node is a fake node placed before the real head so that insertion and deletion at the front look like ordinary middle-of-list operations. Interviews love dummy nodes because they remove special-case branching and make stitched-together outputs easier to reason about.

Linked-list problems are about **preserving access while changing arrows**. Because each node only knows its next pointer, interviews reward students who save the next node before rewiring and who reason locally about what each pointer update does to the rest of the list.

Linked-list reversal is the interview archetype for pointer discipline: keep track of what was before, what you are on, and what comes next. The core invariant is that one prefix has already been reversed while the remaining suffix is still untouched.

Sorted linked-list merge is a classic interview pattern because the lists are already ordered, so you can advance exactly one front pointer at a time. The algorithm is linear in the total number of nodes and is often implemented cleanly with a dummy head.

For loop analysis, count how many times the body executes and multiply by the work per execution. Nested loops often multiply counts, while doubling or halving patterns often lead to logarithms.

Modular arithmetic tracks remainders. That matters in parity, clock arithmetic, hashing buckets, wrap-around indexing, and many programming tasks involving periodic behavior.

Deeper modular reasoning shows up when you compare residue classes, predict collisions, combine congruences, and reason about how bucket counts interact with patterned inputs.

Some subarray problems use prefix sums plus a monotonic deque over prefix indices. The deque keeps promising earlier prefixes in increasing order so the current prefix can quickly detect the shortest earlier start that already makes the sum large enough.

A monotonic deque keeps the current window's best candidates in order, so the front always holds the maximum or minimum. It is the standard pattern for sliding-window extrema because it supports both expiration from the left and dominance cleanup from the right.

Monotonic stacks do more than next-greater queries: they also expose the nearest smaller or larger boundary on each side. That boundary view powers classic problems like largest rectangle in a histogram and contribution counting.

A monotonic stack keeps elements in sorted stack order so that a new value can resolve many waiting positions at once. This turns repeated scanning into a single left-to-right pass for next-greater and waiting-time style problems.

Offline processing sorts updates, queries, or events by a key so work can be done in one monotone sweep. The key insight is to answer many questions by **maintaining a moving frontier** rather than restarting from scratch for each query.

Palindrome reasoning starts from centers and symmetry. Manacher's algorithm pushes that idea further by reusing information from the current rightmost palindrome to compute all palindrome radii in linear time.

Partition algorithms maintain region invariants while scanning an unknown middle segment. This is the interview core behind quickselect-style partitioning, Dutch-flag sorting, and in-place grouping by a pivot or category.

Permutation search cares about **order**, so each recursive level chooses the next position from items not yet used. Constraint checks can often be applied to the growing prefix to reject bad permutations early.

The **prefix function** tracks how much of a pattern already matches itself. That self-overlap information is what lets KMP avoid restarting from scratch after mismatches in pattern matching problems.

Prefix sums precompute cumulative totals so a range sum becomes **one subtraction of two histories**. This is one of the highest-leverage preprocessing tricks in algorithmic problem solving.

A priority queue turns a heap into an algorithmic tool: keep many candidates, then repeatedly extract the **currently best** one. This pattern appears in scheduling, event simulation, shortest-path style relaxations, and systems that reinsert improved priorities over time.

Queues model situations where the earliest discovered or earliest arrived item should be processed first. That makes queues the natural frontier structure for breadth-first search and many step-by-step simulations.

Recurrences describe recursive runtime by combining the cost of smaller subproblems with the non-recursive work done at each step. Recursion trees help you see branching, depth, and total work level by level.

Interview-style recurrence questions usually reduce to a few recognizable patterns. Ask whether the size shrinks by division or subtraction, how many branches appear, and what each level costs.

A recursion tree shows the search branches a backtracking algorithm may explore. **Pruning** means cutting off branches as soon as a partial state can no longer lead to a valid or useful solution.

A **rolling hash** gives a compact fingerprint for a substring so adjacent windows can be compared or updated quickly. Interview prompts use it for repeated-substring checks, duplicate-window detection, and fast candidate comparison.

A strongly connected component in a directed graph is a maximal set of vertices that can all reach one another. SCCs reveal the graph's cyclic cores and compress repeated mutual-reachability structure into components.

Lazy propagation lets a segment tree postpone pushing range updates into children until that detail is actually needed. The main idea is to keep a pending tag that says, in effect, 'this whole interval has already been updated even if the children are not individually refreshed yet.'

Segment trees recursively partition an array into intervals so that range aggregates can be answered in `O(log n)` by combining a small number of stored interval results. The key interview idea is to reason about **no overlap**, **partial overlap**, and **complete overlap**.

Many interview string problems are not about deep string theory. They are about keeping a **contiguous window** consistent while scanning left to right. The key question is what summary of the current window lets you expand, shrink, and answer the prompt in overall linear time.

Sparse tables preprocess answers for intervals of length power of two. They shine on **static arrays** and especially on idempotent operations like minimum, where overlapping power-of-two blocks can answer a query in `O(1)`.

Balanced-parentheses problems are stack problems because each closing bracket must match the **most recent unmatched opening**. That last-opened, first-closed behavior is exactly LIFO order.

Stacks evaluate postfix expressions because operands arrive before the operator that combines them. When the operator appears, the most recent operands are popped, combined, and the result is pushed back for later use.

Enumerating masks from `0` to `2^n - 1` gives every subset of an `n`-element set. Interviews use this for subset generation, used-element state, and small-state dynamic programming where each bit records a chosen item.

Subset and combination search usually depends on a **choose/skip** structure. The important distinction is that order does not matter, so the recursion should move forward through candidates instead of revisiting earlier positions.

Suffix-based reasoning sorts all suffixes of a string lexicographically. Even without implementing a full suffix array from scratch, it helps to know how lexicographic suffix order exposes repeated-substring structure and longest-common-prefix reasoning.

Topological sorting gives an order that respects directed dependencies: every edge points from something that must come earlier to something that may come later. It only works when the graph is a **DAG**.

Tree dynamic programming works because each node can summarize its subtree from its children. Rerooting extends that idea by reusing previously computed information when the root perspective shifts from one node to another.

Bottom-up tree questions ask each subtree to return a small summary such as its height, whether it is balanced, or the best path seen so far. The key interview move is to decide what summary the parent needs from each child.

Tree interview questions often hinge on **when** work happens relative to the recursive calls. Preorder acts before the children, inorder acts between them, and postorder acts after the children return.

String problems often hinge on the right representation. Tries help with many shared prefixes, hashing helps with fast average-case lookup or substring fingerprints, and KMP helps with exact pattern matching without backtracking in the text.

A **trie** stores strings by characters along root-to-node paths. It is useful when many words share prefixes and the interview task asks about prefix lookup, autocomplete, or word-search branching.

A read pointer examines every element while a write pointer marks where the next kept element belongs. This is the core interview pattern for in-place filtering, removing duplicates, and compacting arrays without extra output storage.

When data order lets you predict how a sum or comparison changes, **two pointers** can eliminate large parts of the search space without backtracking. This is the interview reason sorted-pair, palindrome, and container-style problems collapse from quadratic scanning to linear passes.

Union-find, also called **disjoint set union (DSU)**, tracks which items currently belong to the same connected component. It is especially useful when edges are added over time and you need fast connectivity or redundant-edge reasoning.

The Z-function at position `i` stores the length of the longest substring starting at `i` that matches the whole string prefix. This lets you reason about repeated prefix structure and perform pattern search via concatenation.