Algorithms

Heights of left and right subtrees differ by at most 1 at every node. The optimal O(n) DFS returns the subtree height, or −1 as a sentinel for 'unbalanced', so height computation and balance check happen in one pass.

Binary search works on a sorted range by repeatedly halving the search space. Maintain low and high bounds; compare the middle element with the target; move the bound toward the target side. Time O(log n), space O(1).

In a BST a node's left subtree holds smaller values and the right subtree larger values. Recursively: empty → nullptr; equal → return; target less → go left; otherwise go right. Time O(h): O(log n) when balanced, O(n) worst case.

Big-O describes how worst-case running time or memory grows with input size n, ignoring constant factors. Common classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ); the same notation applies to space complexity.

Use Kernighan's trick: n &= n - 1 clears the lowest set bit, repeat until n is 0 — runs in O(k) where k is the number of set bits. In C++20 prefer std::popcount, which compiles to a single instruction.

Naive recursion is O(2ⁿ) — catastrophically slow. Bottom-up iteration uses two variables and runs in O(n) time and O(1) space. Top-down memoisation (cache of results) is also O(n) but O(n) space. Matrix exponentiation achieves O(log n).

XOR all elements together. Pairs cancel out (a XOR a = 0), so the result is the single element that has no pair. Time O(n), space O(1), single pass.

Insertion at head is O(1): create a new node, set its next to the current head, update the head. Insertion at position k is O(k): traverse to the predecessor, splice in the new node. Insertion at tail without a tail pointer is O(n).

Slide a window with a left pointer and a map of each character's last index. For each right, if the character was seen at or after left, jump left to one past that index. The current window length is right - left + 1; track its maximum. One pass, O(n) time.

Use two pointers starting at both ends, advancing toward the center. Compare characters; if they differ the string is not a palindrome. Time O(n), space O(1).

Use three pointers: prev (initially nullptr), curr, and next. Iterate: save next, point curr->next to prev, advance prev to curr, advance curr to saved next. When curr is null, prev is the new head. Time O(n), space O(1).

Use two indices (or iterators) from both ends and swap characters toward the centre. O(n) time, O(1) space in-place. std::reverse from <algorithm> does this in one line.

Quicksort: average O(n log n), in-place, not stable, degrades to O(n²) on bad pivots — use median-of-three or random pivot. Merge sort: guaranteed O(n log n), stable, requires O(n) extra space.

Sorting algorithms rearrange a collection in order. Key ones: bubble/selection/insertion sort O(n²), merge sort O(n log n) stable, quicksort O(n log n) avg / O(n²) worst, heap sort O(n log n). std::sort uses introsort — a quicksort + heapsort + insertion-sort hybrid — for guaranteed O(n log n).

A stack is a LIFO (last-in, first-out) structure: push adds to the top, pop removes from the top. A queue is FIFO (first-in, first-out): enqueue adds to the back, dequeue removes from the front. In C++ the standard library provides std::stack and std::queue as container adaptors, both typically backed by std::deque.

Symmetry is a mirror property of the two subtrees, not of a single node. Recurse comparing left against right: two nodes mirror iff their values match and left.l mirrors right.r and left.r mirrors right.l. Both null is symmetric; one null is not. An empty tree is symmetric. O(n) time.

Pre-order (root, left, right): copy or serialise a tree. In-order (left, root, right): yields sorted output on a BST. Post-order (left, right, root): delete a tree or evaluate an expression tree. Level-order (BFS): queue-based, prints by levels.

BFS (queue) explores level-by-level — best for shortest path in unweighted graphs. DFS (stack/recursion) goes deep along each branch — natural for topological sort, cycle detection and SCCs. Both are O(V+E); BFS uses O(V) memory, DFS uses O(h).

Big-O describes the asymptotic upper bound of growth. Count dominant operations in terms of n, drop lower-order terms and constants; multiply for nested loops, add for independent ones; for recursion use the Master Theorem.

Floyd's tortoise and hare uses two pointers from the head moving at different speeds: slow advances by 1, fast by 2; if they ever meet inside the list a cycle exists, and if fast reaches nullptr the list is acyclic. Time O(n), space O(1).

Use a hash map from value to index. For each element check whether target - nums[i] is already in the map; if so, return both indices. Otherwise insert nums[i] → i. One pass, O(n) time and O(n) space — versus the O(n²) brute-force double loop.

Skip leading whitespace, handle optional sign, then accumulate digits: result = result * 10 + digit. Handle overflow (clamp to INT_MIN/INT_MAX per the standard) and stop at the first non-digit character.

The left-leaf property cannot be decided from a node alone — it depends on the parent. Recurse passing an isLeft flag: a node counts when it is a leaf (no children) and isLeft is true. Recurse into left with isLeft = true and into right with isLeft = false. The root is passed isLeft = false. O(n) time.

First compute the total sum. Then sweep once keeping a running left sum; at index i the right sum is total - left - a[i]. When left == total - left - a[i], return i. One pass after the total, O(n) time and O(1) extra space. Return -1 if none matches.

First pass: count the occurrences of each character in a hash table (or fixed array for a known alphabet). Second pass: walk the string left to right and return the index of the first character whose count is 1. Return -1 if none. O(n) time.

Loop i from 1 to n, build an empty string, append Foo when i % 2 == 0, Bar when i % 3 == 0, Buzz when i % 6 == 0. If the string is still empty print i, otherwise print the string. Because the rules append, a multiple of 6 yields FooBarBuzz.

Core graph algorithms: BFS (shortest path in unweighted graphs, O(V+E)), DFS (cycle detection, topological sort, O(V+E)), Dijkstra (shortest path with non-negative weights, O((V+E) log V)), Bellman-Ford (handles negative edges, O(VE)), Floyd-Warshall (all pairs, O(V³)), Kruskal/Prim for MST.

A year is a leap year if: divisible by 4, EXCEPT centuries (divisible by 100), UNLESS also divisible by 400. So 2000 is a leap year, 1900 is not, 2024 is. Implement with the standard three-condition check.

You cannot erase from a container while iterating with a range-for loop — this invalidates the iterator. Safe approaches: collect keys to erase, then erase in a separate pass; or use the C++20 std::erase_if helper which handles this cleanly.

Walk the string tracking the current character and its run length. When the character changes, update that character's recorded maximum in a map if the just-ended run is longer, then start a new run of length 1. Flush the last run after the loop. One pass, O(n) time.

best is updated only in the else (zero) branch, so a trailing run of 1s that never hits a zero is never compared. Fix it by updating best = max(best, cur) on every 1 (inside the if), or once more after the loop. O(n).

Track the two smallest and two largest values in one pass. The minimum product is the smaller of min1*min2 (both small/negative) and max1*max2 (two large negatives give a small product), but the overall minimum is min1 * max1 when signs are mixed — compare all relevant candidates. O(n) time, O(1) space; watch for overflow with long long.

Split the path on /. Push each component onto a stack; skip empty components (from //) and .; on .. pop the stack if it is non-empty (above-root is ignored). Finally join the stack with /, prefixed by a leading /. One pass, O(n) time.

Use a read and a write index. Copy each character to the write position, but write a space only when the previously written character was not a space. After the pass, resize the string to the write index. One pass, O(n) time, O(1) extra space; leading and trailing single spaces are preserved.

If the lengths differ by more than 1, return false. If equal, count character mismatches and accept at most one. If they differ by 1, scan with two pointers allowing exactly one skip in the longer string; any second mismatch fails. One pass, O(n) time, O(1) space.

Use a write index. Walk the vector with a read index; for each non-zero element, copy it to the write position and advance the write index. After the pass, resize the vector to the write index. One pass, O(n) time, O(1) extra space. The idiomatic form is the erase-remove idiom: v.erase(std::remove(v.begin(), v.end(), 0), v.end()).

Walk the string; at the start of each maximal non-space run, find its end, then reverse that run in place with two pointers swapping inward. Spaces are skipped and left untouched, so all spacing is preserved. One pass, O(n) time, O(1) extra space.

Extract the word tokens in order. Then walk the original string: copy spaces unchanged, and for each maximal non-space run pour in the next word taken from the END of the token list. The space gaps stay fixed; only the words are reversed. O(n).

Walk the string once tracking the current character and its run length. When the next character differs, emit the character, append the count only if the run exceeds one, then reset. After the loop, flush the last group. Validate each character is A-Z and throw otherwise. O(n) time.

Sort both arrays, then use std::set_symmetric_difference to get elements that appear in exactly one of the two arrays. Alternatively, insert one array into an unordered_set and check the other — O(n+m) average with O(n) extra space.

Sweep once keeping the last seen index of X and of Y. On an X, if a Y was seen, update the minimum with i - lastY; on a Y, symmetrically with i - lastX. If either letter never appears, return 0. One pass, O(n) time, O(1) space.

Use two pointers at both ends: the largest square is at one of the ends because the input is sorted. Compare abs(nums[left]) and abs(nums[right]), write the larger square into the output from the back, and move that pointer inward. One pass, O(n) time and O(n) space.

Common: std::sort, find/find_if, transform, for_each, accumulate, copy, remove_if, unique, lower_bound/upper_bound, count_if. Wins over hand-written loops: intent is in the name, the implementation is tested and optimised, and many support parallel execution policies since C++17.

The STL has four main components: containers (sequence, associative, unordered, adapters), iterators (the glue between containers and algorithms), algorithms (sort, find, transform, accumulate, etc.), and function objects/lambdas that customise algorithm behaviour.

Key string algorithms: naive substring search O(n·m), KMP (Knuth-Morris-Pratt) O(n+m), Boyer-Moore O(n/m) average, Rabin-Karp (rolling hash) for multiple pattern search, and Z-algorithm for prefix matching. For edit distance: Levenshtein (dynamic programming O(n·m)).

Keep two variables, max1 and max2, both initialised to the smallest possible value (not 0). For each element: if it exceeds max1, shift max1 into max2 and update max1; else if it exceeds max2, update max2. The crucial else if keeps the old max from being lost. One pass, O(n).

Two passes. First count the spaces to compute the final length. Then write from the back: copy each character to its final slot, and for each space write '0', '2', '%' (reverse order). Writing right-to-left means you never overwrite unprocessed input. O(n) time, O(1) extra space.

A vector owns a heap-allocated array, a size (used elements), and a capacity (allocated slots). push_back amortises O(1) by doubling capacity when full. push_front is O(n) as it must shift all elements. Proper copy/move semantics and destructor are required for correctness (Rule of Five).

Scan the string tracking whether the previous character was whitespace. Each transition from whitespace to non-whitespace increments the word count. Handle multiple consecutive spaces and leading/trailing spaces correctly.

Walk denominations from largest to smallest, taking min(amount / denom, stock[denom]) of each. Greedy is optimal only because the denominations are mutually divisible. Compute the plan into a temporary and apply it only if the remainder is zero — so a failure leaves stock untouched.

Scan every cell. On an unvisited land cell, increment the island count and flood-fill its whole connected component with DFS or BFS, marking each reached land cell as visited (e.g. set it to 0). The fill stops at water and borders; each cell is visited a constant number of times.

Sliding window: keep left as the start of the current repeat-free window and lastSeen[c] as each character's last index. For each right end j, set left = max(left, lastSeen[c]+1), then add j - left + 1 (the valid left ends) to the total. One pass, O(n).

Dijkstra finds shortest paths from a source on graphs with non-negative weights. Pop the minimum-distance vertex from a priority queue, relax its neighbours, push updates. Binary heap — O((V+E) log V); negative weights need Bellman-Ford.

DP exploits overlapping subproblems and optimal substructure by caching subproblem solutions. Memoisation (top-down) is recursion with on-demand caching; tabulation (bottom-up) iteratively fills a table from base cases and often allows space reduction.

Give every word a canonical key shared by all its anagrams, then bucket words by key in a hash map. The key is either the word's sorted characters or a 26-entry character-count signature. Words with the same key are anagrams. Collect the map's values as the groups.

A circular buffer queue uses a fixed array with head and tail indices wrapping around modulo capacity. enqueue writes to tail and advances it; dequeue reads from head and advances it. Full condition: (tail + 1) % cap == head. This gives O(1) enqueue/dequeue with no dynamic allocation.

Quicksort: average O(n log n), worst O(n²) on bad pivots, in-place (O(log n) stack), not stable; usually fastest in practice. Merge sort: guaranteed O(n log n), O(n) extra memory, stable. Use quicksort (introsort) by default; pick merge sort when stability is required or for external sorting.

Two-pointer merge: when a[i] < b[j], a[i] is absent from b, so emit it and advance i. When a[i] == b[j], skip a[i] (it is present). When a[i] > b[j], advance j. After b is exhausted, emit the rest of a. O(n + m), O(1).

Walk the array accumulating a prefix sum P, with a hash map from prefix value to earliest index seeded 0 → -1. At each j, if P - X is in the map, the subarray after that index up to j sums to X. Negatives rule out a window, so the map gives O(n).

Run a DFS carrying the remaining sum and the current path. At each node subtract its value; at a leaf, accept the path iff the remaining sum is now zero. Recurse into children, pushing the node before and popping after (backtracking). Return the first accepted path. O(n) time.

Sweep once with a current run length. While the next character equals the current one, extend the run; on a change, reset to 1. Track the maximum run length across the pass. One pass, O(n) time, O(1) space; the empty string yields 0.

Fix the first two points as a reference direction (dx, dy). A point p is on that line iff the cross product dx*(p.y-y0) - dy*(p.x-x0) is zero. Check it for every point. Use long long for the products to avoid overflow; no division means vertical lines work too. O(n).

Sort the array. For each i, binary-search the first index whose value is at least a[i]+K; every element from there to the end forms a valid pair, so add their count. When K = 0 this counts all i <= j pairs. Total O(n log n) — far better than the O(n²) double loop.

Sort by from, then sweep tracking the running maximum to of all earlier-starting meetings. A meeting overlaps an earlier one when its from < maxEnd; when so, mark both it and the meeting that set maxEnd. Use a flag per meeting so each is reported once. O(n log n).

For integers where each duplicate appears exactly twice, XOR all values: a^a=0 leaves only the unique one — O(n) time, O(1) space. In the general case, build an unordered_map<T,int> of counts in one pass, then return the entry with count==1.

Use two pointers. Walk haystack; whenever the current haystack char equals the current needle char, advance the needle pointer. The needle is a subsequence iff its pointer reaches the end. One linear pass over the haystack, O(|haystack|), constant extra space.

Use DFS with three-colour marking: white (unvisited), grey (in current path), black (fully processed). A back edge (grey→grey) indicates a cycle. Unreachable nodes remain white after a full DFS from all source nodes. A deadlock state is a cycle in a dependency/wait-for graph.

Walk both strings from the last character toward the first, converting each hex digit to 0–15, summing with a carry. Store sum % 16 as the next output digit and keep sum / 16 as carry. After both ends, emit any remaining carry, then reverse the built string. O(max length).

Start two pointers at index-1 and index+1, taking a[index] itself first. Each step compare the left and right candidates' distance to a[index] and take the closer side, until k elements are collected. Guard both ends. O(k) since the array is sorted.

Binary-search the position of x, then grow a size-k window. Each step compare the boundaries' distance to x; if x - arr[left-1] <= arr[right] - x move left, else right. The <= favours the smaller value on a tie. The window stays sorted. O(log n + k).

Walk from the least-significant digit. At each position compute product = digit * n + carry, store product % 10 back, set carry = product / 10. After the loop, while carry > 0 append carry % 10 as new high digits. Little-endian storage lets the carry flow forward naturally.

Scan once, tracking the current run's start and direction. When the next pair flips direction, start a new run at the previous index; when it is equal, start at the current index. Keep the longest run seen. Equality always breaks a strict run. O(n) time, O(1) space.

Sort both arrays, then walk them with two pointers. At each step record abs(a[i] - b[j]) and advance the pointer at the smaller value — moving the larger one could only widen the gap. The minimum over this merge is the global minimum. Subtract in 64-bit to avoid overflow. O(n log n).

The first part always starts at index 0, so its cost is fixed as nums[0]. The other two parts start at any two indices > 0, so their costs are the two smallest values among nums[1..]. The answer is nums[0] plus those two minima, in one O(n) pass.

Use a sliding window with a count of required characters still missing, kept in a hash map. Expand right, decrementing the count when a needed char is first covered. While the window covers all required chars, record it if shorter and shrink from left. Run to the end so a window ending at the last char counts.

Walk both lists with two pointers, tracking the remaining count of the current run on each side. At each step consume min(remaining) positions, adding value_l * value_r * min to the accumulator, then advance whichever run is exhausted. O(|l|+|r|), no expansion, 64-bit sum.

Advance both prefixes in lockstep with two hash sets seenA, seenB and a running common. When a new value from a is already in seenB, increment common; same for a new b value in seenA. Add it to its set. Record common after each step. One pass, O(N).

Walk the moves tracking the current (x, y) coordinate and a hash map of each visited coordinate to its output-path position. When a coordinate repeats, the moves since its first visit form a closed loop: truncate the output back to that position and drop the coordinates added in between.

Treat files as graph nodes and references as edges; traverse with DFS keeping a visited set of file paths so a cycle never reopens a file. Keep a running sum and count; for each numeric line add it and print sum / count. A reference follows the named file only if unvisited.

Keep a min-heap of size at most k + 1. On each get, refill it from the source until it holds k + 1 items or the source ends, then pop the smallest. Every value is within k of its slot, so the smallest of any k + 1-window is the next in order. Return -1 when it drains.

Use backtracking: find the first empty cell, try digits 1–9, check row/column/box constraints, recurse. If no digit works, backtrack. Time complexity is bounded by O(9^m) where m is the number of empty cells, but constraint propagation pruning makes it fast in practice.

Sort the array. Walk it tracking the start of the current consecutive run; when the next value is not prev + 1, flush the run as start or start-end and begin a new one. Flush the last run after the loop. O(n log n) for the sort, O(n) to build.

Two pointers from both ends. On the first mismatch, try skipping either the left or the right character and check whether the remaining span is a palindrome. If the string is already a palindrome, removing a central char keeps it one, so return true. O(n), O(1).

The only candidate axis is (minX + maxX) / 2, so the doubled axis is minX + maxX. Put every point in a hash set; for each point (x, y) its mirror is (minX + maxX - x, y). If every mirror is present the axis is valid. Use the doubled value to avoid fractions. O(n).

Build the cumulative distribution: walk the weights accumulating a running sum and return the first index where the sum exceeds r. This maps the uniform draw onto buckets sized by weight, so each server's chance equals its weight. O(k), or O(log k) with a prefix-sum array and binary search.

Slide a window of length |S| over T and keep one counter of how many character-counts still mismatch the pattern. On each slide add the entering char and drop the leaving char, updating that counter in O(1). When it hits zero the window is an anagram. O(|T|), alphabet-independent.

Keep a stack of partial strings. On ( push the current string and start a fresh one; on ) parse the bracketed N, pop the saved string and append the just-built string repeated N times; otherwise append the letter. Multi-digit N parses digit by digit, N == 0 appends nothing.

Compute each node's depth by walking up via parent to the root. Advance the deeper node upward by the depth difference so both are level, then walk both up in lockstep until the pointers meet — that node is the LCA. O(h) time, O(1) space, no extra structures.

Scan once as a small state machine. At each position check for : then - then a run of ) or (; if found, skip the whole token and continue past it, else copy the current character out. No backtracking into emitted text, so nesting is not collapsed. O(n).

Two-pointer merge of the sorted lists: at equal indices add the values, otherwise emit the smaller index and advance that pointer. Skip any result whose summed value is zero (it is no longer sparse-nonzero). Linear in the combined length, O(|l|+|r|).

Stable sort preserves the relative order of equal-key elements. std::stable_sort is stable (merge-sort, O(n log n) with O(n) extra memory); std::sort is not stable (introsort, O(n log n) average, in-place). For multi-criteria sorting, apply stable sorts from the least to the most significant key.

Ranges accept a single range instead of iterator pairs (std::ranges::sort(v)), reducing iterator mismatch bugs. Views (v | filter | transform) compose lazy transformations; compile times rise.

Keep a queue of windowed events, a map userId → count, and a running robotCount of users at or above the threshold. On each op evict events older than the window, add the new one, and adjust robotCount on a threshold crossing. Each event is enqueued and dequeued once, so amortized O(1).

Post-order recursion: a node's letter set is (1 << (Value-'A')) OR-ed with the masks of its children. Store each computed mask in a hash map from mask to node; the first time a mask repeats you have two equivalent subtrees. One traversal, O(N) time and O(N) space.

C++17 added execution policies to many STL algorithms: std::execution::seq (sequential), par (parallel), par_unseq (parallel + vectorised). The policy is a hint — the implementation decides how to exploit it.

A good hash function distributes keys uniformly and is fast to compute. FNV-1a and djb2 are classic non-cryptographic hashes. Collision resolution: separate chaining (linked list per bucket) or open addressing (linear/quadratic probing, double hashing). std::unordered_map uses separate chaining in most implementations.

Use a sweep line: split each stay into a +1 check-in and a −1 check-out event, sort by time, and sweep keeping a running count whose maximum is the answer. At a shared time process check-outs before check-ins. O(N log N) for the sort.

Sliding window allowing at most one zero inside it; the answer is the largest window size minus one (one element is always removed). When there are no zeros, that minus-one still applies, giving L-1 for an all-ones array. One pass, O(n), O(1).

Backtrack: place three dots splitting the string into four octets. At each step try a 1-, 2-, or 3-digit octet, accepting it only if its value is 0–255 with no leading zero (unless exactly "0"). When all four octets consume the whole string, record the address.

C++17 added a searcher-based overload std::search(first, last, searcher) with three standard searchers: default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher. The searcher preprocesses the pattern once in its constructor.

Merge sort guarantees O(n log n) and is stable, making it suitable for linked lists and external sorting. Introsort (quicksort + heapsort fallback + insertion sort for small ranges) is what std::sort uses: O(n log n) guaranteed, in-place, but not stable.