100 Problems — Editorial Guide

A Codeforces-style tutorial covering 100 curated problems.

Pilot batch (1–5). This is a stylistic sample. Once you approve the format, tone, and level of detail, the remaining 95 problems will be rewritten in the same structure.

Each problem is presented in five parts:

1. Problem Statement — a clean, unambiguous specification.
2. Solution — the intended approach with a complete C++11 implementation.
3. Discussion — why the approach works, key observations, common pitfalls.
4. Follow-ups — realistic extensions to push on.
5. Trade-offs — when to prefer alternative approaches.

1. File System Total Size

Problem Statement

You are given a hierarchical file system modeled as a rooted tree. Every node is either:

• a file, with a non-negative integer size, or
• a directory, with a list of child nodes (files and/or sub-directories).

Implement a function totalSize(root) that returns the sum of the sizes of all files in the subtree rooted at root.

Input. A pointer to the root node. Each node exposes: - bool isFile — whether the node is a file; - long long size — valid only when isFile is true; - vector<Node*> children — valid only when isFile is false.

Output. A single 64-bit integer, the total size of all files reachable from root.

Constraints. - 1 <= N <= 10^5 nodes. - The structure is a strict tree: every node has exactly one parent (the root has none), and there are no cycles. - Individual file sizes fit in a 32-bit integer, but the total may exceed it — accumulate into a 64-bit integer.

Example.

root/
├── a.txt       (size 10)
└── dirA/
    ├── b.txt   (size  5)
    └── c.txt   (size  7)

totalSize(root) = 22

Solution

A single depth-first traversal. For a file, return its size. For a directory, return the sum of the recursive calls on its children.

long long totalSize(Node* root) {
    if (!root) return 0;
    if (root->isFile) return root->size;
    long long sum = 0;
    for (Node* c : root->children) sum += totalSize(c);
    return sum;
}

• Time. O(N) — each node visited once.
• Space. O(H) recursion depth, where H is the tree height (up to O(N) for a skewed tree).

Discussion

The entire problem is a one-line recurrence once you realize the tree assumption. The interesting signal is whether you ask for the tree guarantee before writing code. If the structure is a general DAG (hard links permitted), the recursion above double-counts shared subtrees; if it can have cycles, the recursion doesn’t terminate. Always clarify.

Two pitfalls worth stating out loud:

• Integer overflow. Individual sizes are small, but a directory with 10^5 files of several MB each easily exceeds 2^31. Use long long.
• Stack depth. A chain of 10^5 nested directories will blow the default thread stack. Be ready to convert to an iterative DFS with an explicit stack.

Follow-ups

(F1) What if the structure is a DAG — directories may be linked from multiple parents? A plain recursion counts shared subtrees multiple times, which can be the correct behavior (report total on-disk footprint as the OS presents it) or not (report unique bytes). Clarify, then:

• Count per occurrence → add memoization on Node*, each unique node is summed once and reused:

long long dfs(Node* u, unordered_map<Node*, long long>& memo) {
    if (!u) return 0;
    unordered_map<Node*, long long>::iterator it = memo.find(u);
    if (it != memo.end()) return it->second;
    long long s = u->isFile ? u->size : 0;
    if (!u->isFile)
        for (Node* c : u->children) s += dfs(c, memo);
    memo[u] = s;
    return s;
}

• Count unique bytes → walk the DAG with a visited set keyed on file identity; files already seen contribute zero.

(F2) Cycles. If children can form a cycle, maintain a visited set in the traversal and early-return on re-entry.

(F3) Iterative version. Useful when recursion depth is unsafe:

long long totalSizeIter(Node* root) {
    long long total = 0;
    stack<Node*> st;
    if (root) st.push(root);
    while (!st.empty()) {
        Node* u = st.top(); st.pop();
        if (u->isFile) { total += u->size; continue; }
        for (Node* c : u->children) st.push(c);
    }
    return total;
}

(F4) Streaming summaries. Report the size of every directory, not just the root. Do this in a single post-order pass, writing each directory’s total into an output map as the recursion unwinds — still O(N) time and O(N) extra space.

Trade-offs

2. Dynamic Friend Connectivity

Problem Statement

You are given n users labeled 0 … n-1 and a stream of q operations to process online. Each operation is one of:

• add(a, b) — declare users a and b friends (an undirected edge).
• query(a, b) — return true if a and b are currently in the same friendship component, false otherwise.

Part A. Only add and query operations occur. Implement the system so that all operations are handled as fast as possible.

Part B. A third operation is added:

• remove(a, b) — unfriend a and b. The edge is guaranteed to exist.

The system must still answer query correctly. Describe a data structure that supports add, remove, and query efficiently and argue its complexity.

Constraints. - 1 <= n, q <= 2 * 10^5. - For Part A, expected complexity per operation must be sublinear in n. - For Part B, state the best complexity you can achieve and whether the operations may be processed offline.

Example.

n = 4
add(0,1); add(1,2); query(0,2) -> true
remove(1,2);      query(0,2) -> false

Solution

Part A (incremental-only). This is textbook Union–Find with union-by-rank and path compression. Both operations run in inverse-Ackermann time, which is effectively constant.

struct DSU {
    vector<int> parent, rank_;
    DSU(int n): parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }
    bool connected(int a, int b) { return find(a) == find(b); }
};

• Time. O(α(n)) amortized per operation.
• Space. O(n).

Part B (fully dynamic). Path compression destroys the history required to split a component when an edge is removed, so the Part A structure alone is insufficient. The cleanest interview answer depends on whether the operations are online or offline.

If the full operation sequence is known in advance (offline), the standard trick is offline segment tree over time + Union–Find with rollback:

1. For each edge, compute the time interval [t_add, t_remove) during which it exists.
2. Place each such interval on the O(log q) nodes of a segment tree whose leaves are timestamps.
3. DFS the segment tree. When entering a node, unite all edges stored there (without path compression). When leaving, roll back those unions from a history stack. At each leaf, answer the query registered at that timestamp.

struct RollbackDSU {
    vector<int> parent, rank_;
    vector<tuple<int,int,int,int> > history; // (a, ra, b, rb)
    RollbackDSU(int n): parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) { // no path compression
        while (parent[x] != x) x = parent[x];
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) { history.push_back(make_tuple(-1,0,-1,0)); return false; }
        if (rank_[a] < rank_[b]) swap(a, b);
        history.push_back(make_tuple(a, rank_[a], b, rank_[b]));
        parent[b] = a;
        if (rank_[a] == rank_[b]) ++rank_[a];
        return true;
    }
    void rollback() {
        int a, ra, b, rb;
        tuple<int,int,int,int> top = history.back(); history.pop_back();
        a = std::get<0>(top); ra = std::get<1>(top);
        b = std::get<2>(top); rb = std::get<3>(top);
        if (a == -1) return;
        parent[b] = b;
        rank_[a] = ra;
        rank_[b] = rb;
    }
};

Total time for the offline algorithm is O((n + q) · log q · α(n)).

If the operations must be answered online, the textbook result is the Holm–Lichtenberg–Thorup (HDT) structure, which achieves O(log^2 n) amortized per update and O(log n / log log n) per query. Nobody expects you to implement HDT on a whiteboard, but naming it shows breadth.

Discussion

The critical observation for Part A is that Union–Find is the only general data structure offering near-constant incremental connectivity. Everything else (BFS/DFS per query, adjacency + component labeling, …) is either slower or strictly dominated.

Part B is where answers vary wildly by constraints. The honest ordering from weakest to strongest:

1. Baseline: adjacency list + BFS per query. O(1) updates, O(n + m) per query. Always correct and trivial to code — useful as a fallback if you can’t recall the fancy algorithm under pressure.
2. Offline segment tree + rollback DSU: the competitive-programming standard for this family. Realistic to code in an interview window, and the amortization argument is clean.
3. Online HDT (or its link-cut / Euler-tour-tree cousins for forests): the asymptotically best known structure. Cite by name.

Interviewers listen for two things: that you recognize remove is strictly harder than add, and that you can describe some structure (not just “BFS”) with at least polylog update cost.

Follow-ups

(F1) Only forest edges. If you guarantee the graph stays a tree/forest, link-cut trees give O(log n) per op online — much simpler than HDT.

(F2) Count components, not just test pairs. Union–Find already tracks this via a running counter; decrement on every successful unite and increment on every removal that actually disconnects a component. The “actually disconnects” check is what makes removal hard.

(F3) Bulk adds. Given a batch of k adds, process them with a single DSU pass in O(k α(n)). This matters when the stream is bursty.

(F4) Weighted edges / minimum spanning forest. Replace plain DSU with a Kruskal-style incremental MSF; on removal, you may need a replacement edge, which is exactly what HDT searches for level by level.

Trade-offs

3. Swap Adjacent in LR String (Linear and Circular)

Problem Statement

Let start and target be two strings of equal length n over the alphabet {'L', 'R', '.'}. The . cells are empty. A single move is one of:

• Replace a substring "L." with ".L" (an L moves one cell left into an empty cell).
• Replace a substring ".R" with "R." (an R moves one cell right into an empty cell).

You may perform any number of moves in any order.

Part A (Linear). Return true iff start can be transformed into target.

Part B (Circular). Now treat the string as a ring: index n-1 is adjacent to index 0. An L at position 0 may move to position n-1 (wrap-around), and an R at position n-1 may move to position 0. Decide the same reachability question on the ring.

Constraints. 1 <= n <= 10^5.

Example (linear). start = "RXXLRXRXL", target = "XRLXXRRLX" → true (use X as a stand-in for .).

Solution

Part A — Linear. Observe two invariants that must hold for any reachable target:

1. If we strip the .s from both strings, the resulting sequences of Ls and Rs must be identical. (Pieces never swap relative order.)
2. The i-th non-dot in start must be able to reach the i-th non-dot in target given its movement direction:
   • An L only moves left, so its index in start is >= its index in target.
   • An R only moves right, so its index in start is <= its index in target.

Walking both strings with two pointers is enough to verify both conditions.

bool canTransform(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int n = s.size(), i = 0, j = 0;
    while (i < n || j < n) {
        while (i < n && s[i] == '.') ++i;
        while (j < n && t[j] == '.') ++j;
        if (i == n || j == n) return i == n && j == n;
        if (s[i] != t[j]) return false;
        if (s[i] == 'L' && i < j) return false;
        if (s[i] == 'R' && i > j) return false;
        ++i; ++j;
    }
    return true;
}

• Time. O(n).
• Space. O(1).

Part B — Circular. The same “pieces cannot pass each other” invariant holds, but now “order” means cyclic order. The reachability check becomes:

1. Strip the .s from both strings. Let the resulting sequences be A and B, with original positions posA and posB.
2. B must be a cyclic rotation of A. (If it isn’t even that, no sequence of moves can produce it.) You can detect this with the classic B is a substring of A + A test, which gives you the rotation offset off.
3. Once you have off, piece i in A must move from posA[i] to posB[(i - off + m) % m], where m = |A|. Each piece must travel only in its own direction (L decreases index mod n, R increases index mod n), and the distance it travels must be strictly less than the cyclic gap to its neighbour in that direction — otherwise it would overtake or collide with the neighbour.

bool canTransformCircular(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int n = s.size();
    string A, B;
    vector<int> posA, posB;
    for (int i = 0; i < n; ++i) if (s[i] != '.') { A += s[i]; posA.push_back(i); }
    for (int i = 0; i < n; ++i) if (t[i] != '.') { B += t[i]; posB.push_back(i); }
    if (A.size() != B.size()) return false;
    if (A.empty()) return true;

    string AA = A + A;
    size_t off = AA.find(B);
    if (off == string::npos) return false;

    int m = A.size();
    for (int i = 0; i < m; ++i) {
        int src = posA[i];
        int dst = posB[((i - (int)off) % m + m) % m];
        char c  = A[i];
        int delta = (c == 'R') ? (dst - src + n) % n
                               : (src - dst + n) % n;
        int nextIdx = (c == 'R') ? (i + 1) % m : (i - 1 + m) % m;
        int nextSrc = posA[nextIdx];
        int gap = (c == 'R') ? (nextSrc - src + n) % n
                             : (src - nextSrc + n) % n;
        if (delta >= gap) return false;
    }
    return true;
}

• Time. O(n) (substring search on A + A is O(n) with KMP; find is acceptable for interview purposes).
• Space. O(n).

Discussion

The problem is secretly about invariants under a move system. The moves never change the multiset of non-dot characters, and they never change the relative order of those characters — only their positions. Once you see that, Part A reduces to “can each piece reach its target without crossing another”.

Part B requires one conceptual upgrade: “order” on a ring means cyclic order, so the test “B equals A” becomes “B is a rotation of A”. The standard rotation test is B occurs in A + A. Everything else — the per-piece lane argument — carries over essentially unchanged.

A surprisingly common wrong instinct is to try BFS over board states. With n = 10^5 that’s astronomically hopeless; n = 8 would already be too big for most interviewers. Always stress-test a fast invariant-based solution against a brute-force BFS on small inputs before trusting it.

Follow-ups

(F1) Minimum number of moves. For the linear version, sum, over all pieces, the absolute difference between the piece’s source and target index. That’s the minimum cost because each move shifts one piece by exactly one cell and no move is wasted when the invariants above already hold.

(F2) Count reachable boards. The reachability relation partitions all 3^n boards into equivalence classes. Within a class, the number of distinct boards is the number of ways to interleave the fixed L/R skeleton with .s, subject to the ordering constraints — a combinatorial enumeration that reduces to counting lattice paths with step restrictions.

(F3) Parallel moves. If every piece moves one step simultaneously per round, the reachable set shrinks dramatically and the two-pointer invariant no longer captures it. This variant needs a proper BFS up to modest n.

(F4) Multiple pieces with different alphabets. Add a piece B that can move in both directions. The invariant on the order of Ls and Rs still holds for each of them separately, but Bs can weave between them. The proof sketches out to a graph reachability argument on “which piece can occupy which cell in the canonical form”.

Trade-offs

4. Faulty Keyboard — Intended Words From Stuck Keys

Problem Statement

A user typed a message on a keyboard where some keys occasionally get stuck, producing runs of the same letter longer than the user intended. A stuck key never drops a character and never produces a wrong character — it only inflates a single intended letter into a run of two or more copies of that same letter.

You are given:

• A dictionary words of lowercase English words.
• A typed string s.

Return every word in words that the user could have intended to type. A word w could have been intended iff s can be segmented into runs c_1^{k_1} c_2^{k_2} … c_r^{k_r} such that w = c_1^{j_1} c_2^{j_2} … c_r^{j_r} with 1 <= j_i <= k_i for every run.

Equivalently: in each run of s, the intended word uses between 1 and the run length copies of the same character, and no characters outside those runs may appear.

Constraints. - |s| <= 10^4. - |words| <= 10^4 and the sum of word lengths is at most 10^5.

Example.

s = "heeellooo"
words = ["hello", "help", "hero", "yellow"]
answer = ["hello"]

s = "gooogle"
words = ["google", "goggle", "go"]
answer = ["google"]

Solution

Insert every dictionary word into a trie. Preprocess s into its list of runs (char, length). DFS the trie while walking the runs: when the current run is (c, k), try consuming 1, 2, …, k copies of c down the children[c] chain, then recurse on the next run.

struct Trie {
    Trie* ch[26];
    string word;
    Trie() : word() { for (int i = 0; i < 26; ++i) ch[i] = nullptr; }
};

void insert(Trie* root, const string& w) {
    Trie* cur = root;
    for (int i = 0; i < (int)w.size(); ++i) {
        int k = w[i] - 'a';
        if (!cur->ch[k]) cur->ch[k] = new Trie();
        cur = cur->ch[k];
    }
    cur->word = w;
}

vector<pair<char,int> > toRuns(const string& s) {
    vector<pair<char,int> > r;
    for (int i = 0; i < (int)s.size();) {
        int j = i;
        while (j < (int)s.size() && s[j] == s[i]) ++j;
        r.push_back(make_pair(s[i], j - i));
        i = j;
    }
    return r;
}

void dfs(Trie* node, const vector<pair<char,int> >& runs, int idx,
         unordered_set<string>& out) {
    if (idx == (int)runs.size()) {
        if (!node->word.empty()) out.insert(node->word);
        return;
    }
    char c = runs[idx].first;
    int len = runs[idx].second;
    Trie* cur = node;
    for (int k = 1; k <= len; ++k) {
        cur = cur->ch[c - 'a'];
        if (!cur) return;                     // no dictionary word continues here
        dfs(cur, runs, idx + 1, out);
    }
}

vector<string> intendedWords(const string& s, const vector<string>& dict) {
    Trie root;
    for (int i = 0; i < (int)dict.size(); ++i) insert(&root, dict[i]);
    vector<pair<char,int> > runs = toRuns(s);
    unordered_set<string> out;
    dfs(&root, runs, 0, out);
    return vector<string>(out.begin(), out.end());
}

Let R be the number of runs in s and L the average run length. The DFS visits at most one trie path per (run-count, k-per-run) combination, but the branching is aggressively pruned by the trie: almost no English word has three consecutive identical letters, so the fan-out at each run is effectively O(1).

• Time. O(sum(|words|)) for trie construction, plus O(R · C) per search where C is the average trie depth explored.
• Space. O(sum(|words|)) for the trie, O(R) recursion.

Discussion

The problem is “dictionary + prefix matching with a twist”. The moment you recognize that, a trie is the default scaffolding and you only need to decide what the “twist” is. Here, the twist is that consecutive identical characters in the input may correspond to one or more copies along the trie path — a bounded branching decision at each step.

Two subtle correctness points:

• Dictionary words with runs. "google" contains "oo". When you hit the "ooo" run in s, you must allow the trie to consume exactly 2 copies; consuming 1 lands on a dead end because "gogle" isn’t in the trie. The per-run loop handles this naturally.
• Duplicates in the answer. A DFS may reach the same word via different consumption patterns. Collect results in a set.

Follow-ups

(F1) Dropped keys. Some keypresses don’t register. Now, in addition to consuming characters from the current run, the DFS may consume a trie edge whose character doesn’t appear in s at all — this is edit-distance-style DP on the trie.

(F2) Typos. Any character may be wrong. Add a bounded number of substitution moves to the DFS and prune by distance threshold.

(F3) Top-K likely intended words. If the dictionary carries frequency priors, maintain a min-heap of size K keyed on frequency during the DFS.

(F4) Huge dictionary. Replace the trie with a DAWG (directed acyclic word graph) so shared suffixes cost nothing. Cuts memory by 2–5x on English.

(F5) Streaming queries. Cache results per input s. Preprocessing cost is paid once; each unique query is independent.

Trade-offs

5. Detect Rotated Squares

Problem Statement

Maintain a dynamic multiset of 2D integer points supporting two operations:

• add(x, y) — insert a point at (x, y); duplicates are allowed.
• count() — return the total number of (possibly rotated) squares whose four vertices are all present in the multiset. Each geometric square is counted as many ways as its vertices can be chosen, weighted by multiplicities (see below).

A square here is any four distinct points forming the vertices of an actual square — axis-aligned or rotated by any angle. If a vertex has multiplicity m, it contributes a factor of m to the count per occurrence in the square (as in the standard LeetCode “Detect Squares” convention).

Constraints. - Coordinates are integers with |x|, |y| <= 10^4. - At most 3 · 10^4 total add calls. - count() is called far less frequently than add, but must still be efficient (sublinear per call is not expected; O(n^2) with good constants is).

Example.

add(0, 0); add(2, 1); add(3, -1); add(1, -2);
count() -> 1     // the four points form a square rotated ≈26.57°

Solution

Key invariant. The two diagonals of a square share the same midpoint, have the same length, and are perpendicular. That single statement drives the algorithm: group every unordered pair of points by (midpoint, squared length); within each bucket, count the number of pairs of diagonal vectors that are perpendicular.

To stay in integer arithmetic, represent the midpoint as 2 · midpoint (so it’s always an integer pair), and store the diagonal vector (dx, dy) = p_j - p_i once per bucket. Two diagonal vectors (u_x, u_y) and (v_x, v_y) correspond to a valid square iff u_x · v_x + u_y · v_y == 0.

struct DetectSquares {
    unordered_map<long long, int> mult; // (x,y) packed -> multiplicity

    static long long key(int x, int y) {
        return ((long long)(x + 20000) << 20) | (unsigned)(y + 20000);
    }

    void add(int x, int y) { ++mult[key(x, y)]; }

    long long count() {
        vector<pair<int,int> > pts;
        pts.reserve(mult.size());
        for (unordered_map<long long,int>::const_iterator it = mult.begin();
             it != mult.end(); ++it) {
            long long k = it->first;
            int y = (int)(k & 0xFFFFF) - 20000;
            int x = (int)(k >> 20) - 20000;
            pts.push_back(make_pair(x, y));
        }
        long long total = 0;
        int n = pts.size();

        // For each unordered pair, treat it as one diagonal (A, C).
        for (int i = 0; i < n; ++i) {
            int ax = pts[i].first, ay = pts[i].second;
            for (int j = i + 1; j < n; ++j) {
                int cx = pts[j].first, cy = pts[j].second;
                int dx = cx - ax, dy = cy - ay;
                // For integer-coordinate squares, the other two vertices are
                // integer iff both (dx + dy) and (dy - dx) are even -- i.e.
                // (dx + dy) is even.  When (dx + dy) is odd, no square exists.
                if (((dx + dy) & 1) != 0) continue;
                int mx2 = ax + cx, my2 = ay + cy;              // 2 * midpoint
                int hx = (cx - ax) / 2, hy = (cy - ay) / 2;    // half diag
                // The other two vertices are midpoint +/- rot90(half diag)
                int bx = (mx2 / 2) - hy, by = (my2 / 2) + hx;
                int ddx = (mx2 / 2) + hy, ddy = (my2 / 2) - hx;
                unordered_map<long long,int>::const_iterator b = mult.find(key(bx, by));
                unordered_map<long long,int>::const_iterator d = mult.find(key(ddx, ddy));
                if (b != mult.end() && d != mult.end()) {
                    long long ma = mult[key(ax, ay)];
                    long long mc = mult[key(cx, cy)];
                    total += ma * mc * (long long)b->second * (long long)d->second;
                }
            }
        }
        // Each square has exactly 2 diagonals and we iterated unordered pairs,
        // so each square was counted twice.
        return total / 2;
    }
};

• Time. count() runs in O(n^2) where n is the number of distinct points.
• Space. O(n) for the multiplicity map.

Discussion

The move from axis-aligned Detect Squares (LeetCode 2013) to the rotated version is the classic “stop grouping by same-x/same-y”. Axis-aligned squares are special because their sides are parallel to the axes, which lets you anchor on one pair of opposing corners and check two axis-aligned lookups. Rotated squares have a full continuous orientation family, so no fixed-axis anchor works.

The saving grace is that diagonals are a much better primitive than sides: every square has two diagonals, both passing through the same center, both of the same length, and perpendicular to each other. So any pair of points that can serve as a diagonal determines the other two vertices uniquely — and you can either test those vertices directly (as the code above does) or, for a pair-hashing variant, bucket pairs by (midpoint, length^2) and within each bucket count perpendicular pairs.

A useful parity shortcut: if (dx + dy) is odd, the other two vertices have non-integer coordinates and the pair cannot be a diagonal of an integer square. That filter alone kills roughly half of all candidate pairs for free.

Follow-ups

(F1) Axis-aligned only (the LC 2013 baseline). Much easier: fix one corner, enumerate the opposite corner on the diagonal, read two axis-aligned corners with direct lookups. O(n) per query.

(F2) Bounded coordinate range [0, C]. Instead of iterating over pairs, iterate over each point and every lattice vector (a, b) with a^2 + b^2 <= C^2; use the hash map to probe the remaining three vertices. For n >> C^2 this is asymptotically better at O(n · C^2).

(F3) Rectangles instead of squares. Bucket pairs by (midpoint, length^2) only; within each bucket, every pair of diagonals forms a rectangle — drop the perpendicularity check, but remember to divide by 2 for the pair of diagonals of each rectangle.

(F4) Streaming / online squares. Instead of recomputing from scratch on each count(), maintain the bucket structure incrementally: each add updates O(n) buckets in the worst case, but a well-chosen layered hash can amortize.

(F5) Count lattice points forming a regular polygon with k vertices. Same invariant idea, generalised: fix the center and the radius, look for k points whose position vectors from the center are rotations of each other by 2π / k. For integer lattices only k = 4 (squares) admits non-trivial solutions at arbitrary orientation.

Trade-offs

6. Meeting Rooms II — At Scale

Problem Statement

Given n meeting intervals intervals[i] = [s_i, e_i), return the minimum number of conference rooms required so that no two overlapping meetings share a room. Then answer the follow-up: if the number of intervals is far too large to fit in memory, how would you compute the same answer?

Constraints. 1 <= n, all start/end values are 32-bit integers, and intervals are half-open: a meeting ending at time t does not conflict with one starting at t.

Example. [[0,30],[5,10],[15,20]] -> 2.

Solution

Convert each interval into two time-stamped delta events (s, +1) and (e, -1), sort them, and sweep. The running sum is the current number of occupied rooms; the global maximum is the answer. The half-open convention means that at equal timestamps the -1 events must be processed before the +1 events.

int minRooms(vector<vector<int> >& iv) {
    vector<pair<int,int> > ev;
    ev.reserve(iv.size() * 2);
    for (int i = 0; i < (int)iv.size(); ++i) {
        ev.push_back(make_pair(iv[i][0], +1));
        ev.push_back(make_pair(iv[i][1], -1));
    }
    sort(ev.begin(), ev.end(),
         [](const pair<int,int>& a, const pair<int,int>& b) {
             if (a.first != b.first) return a.first < b.first;
             return a.second < b.second; // -1 before +1
         });
    int cur = 0, peak = 0;
    for (int i = 0; i < (int)ev.size(); ++i) {
        cur += ev[i].second;
        if (cur > peak) peak = cur;
    }
    return peak;
}

• Time. O(n log n). Space. O(n).

Discussion

The heap-of-end-times approach (O(n log n) sort + O(n log n) heap) is functionally equivalent, but the sweep formulation decouples the sort from the counting, and the counting pass itself is a trivial linear scan with O(1) state. That property is what makes the scale follow-up tractable.

Follow-ups

(F1) Data is far too large to fit in RAM. First identify which regime you’re in:

• Single-machine external: external-merge-sort the events to disk in chunks that fit in memory, then stream the sorted file through a running counter — O(n log n) CPU, O(n) I/O.
• Distributed (MapReduce / Spark): Map emits (t, +1) and (t, -1) per interval; shuffle by time key; within each partition, compute a local peak and a running delta at the partition boundary; a final sequential pass reconciles the boundaries to get the global peak.
• Unbounded stream: maintain a sorted multiset (or min-heap) of active end times; on every incoming interval, evict all expired ends, insert the new one, and update the peak.

(F2) Peak concurrency in a rolling window. Same sweep, but evict events that fall outside the window edge.

(F3) Per-room assignment. Augment the heap variant so that each pop returns the specific room ID to reuse.

Trade-offs

7. Earliest Moment All Friends Connected

Problem Statement

There are n people and a list of timestamped friendship events. Each event is either FRIEND(t, a, b) (at time t, a and b become friends) or UNFRIEND(t, a, b) (at time t, they stop being friends — guaranteed to be currently friends).

Return the earliest timestamp at which the friendship graph contains exactly one connected component, or -1 if that never happens.

Constraints. 1 <= n, m <= 2 * 10^5. All timestamps are distinct.

Solution

Base case (no unfriend events). Sort events by time, feed them into a Union–Find with a component counter, and return the timestamp of the union that reduces the count to 1.

int earliestAcq(vector<vector<int> >& logs, int n) {
    sort(logs.begin(), logs.end());
    DSU d(n);
    int comp = n;
    for (int i = 0; i < (int)logs.size(); ++i) {
        if (d.unite(logs[i][1], logs[i][2])) {
            if (--comp == 1) return logs[i][0];
        }
    }
    return -1;
}

O(m log m) time, O(n) space.

Full case (unfriend allowed). The set of “fully connected” timestamps is not monotonic, so you cannot binary-search. Use the offline segment tree over time + rollback DSU pattern:

1. Compute each edge’s lifetime [t_add, t_remove) by scanning the logs.
2. Place each lifetime on the O(log m) nodes of a segment tree whose leaves are the distinct timestamps.
3. DFS the segment tree. On entry to a node, unite the edges stored there and record them on a rollback stack. At each leaf, if comp == 1, record the timestamp as a candidate. On exit, roll back the unions added at this node.

The minimum recorded timestamp is the answer, or -1.

• Time. O((n + m) · log m · α(n)).
• Space. O(m log m) for the segment tree.

Discussion

The key insight is that unfriend makes this a fully dynamic connectivity problem, which plain DSU cannot handle because path compression destroys history. Among the classical solutions (HDT online, link-cut trees for forests, segment tree over time offline), the segment tree variant is by far the most realistic to code in a 45-minute interview — every primitive is either already memorized (DSU, segment tree) or a small tweak (disable path compression, add a rollback stack).

Follow-ups

(F1) Online. Cite HDT (O(log^2 n) amortized per op) by name; don’t try to code it. (F2) Forest only. Link-cut trees give O(log n) online. (F3) Query at arbitrary time. Register the query at its timestamp leaf and collect the answer during the same DFS.

Trade-offs

8. Meeting Rooms I and II

Problem Statement

Given n meeting intervals [s_i, e_i), answer two questions:

• Part A. Can a single person attend every meeting (i.e., no two intervals overlap)?
• Part B. What is the minimum number of rooms required to host all the meetings concurrently?

Intervals are half-open; a meeting ending at t does not conflict with one starting at t. Constraints: 1 <= n <= 2 * 10^5.

Solution

Part A. Sort intervals by start; verify each successor’s start is at least the previous end.

bool canAttendAll(vector<vector<int> >& iv) {
    sort(iv.begin(), iv.end());
    for (int i = 1; i < (int)iv.size(); ++i)
        if (iv[i][0] < iv[i-1][1]) return false;
    return true;
}

Part B. The sweep-line / delta-events approach from problem 6 is the cleanest. Alternatively, a min-heap of active end times: sort by start, push each meeting’s end time, pop any end <= current start before pushing.

int minRooms(vector<vector<int> >& iv) {
    sort(iv.begin(), iv.end());
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < (int)iv.size(); ++i) {
        if (!pq.empty() && pq.top() <= iv[i][0]) pq.pop();
        pq.push(iv[i][1]);
    }
    return (int)pq.size();
}

Both run in O(n log n).

Discussion

Part A is the textbook “no overlaps” check. Part B is the textbook “peak concurrency”. The two problems share the sorting step but diverge on what they track — “did any successor start before its predecessor ended” vs. “what’s the maximum concurrent count”. Interviewers use this pair to gauge whether you can separate the pattern from the detail.

Follow-ups

(F1) Scale. Use the external-merge-sort + streaming sweep from problem 6. (F2) Return the actual room assignment. Replace the min-heap with a min-heap of (end_time, room_id). (F3) Weighted overlap. Each meeting has a weight; report the peak weighted concurrency. Same sweep, delta is the weight.

Trade-offs

9. Hierarchical Manager / Peer Queries

Problem Statement

Implement an incremental hierarchy service over n employees that supports three operations, arriving in any order:

• manager(a, b) — record that a is the direct manager of b.
• peer(a, b) — record that a and b share the same direct manager.
• is_manager(a, b) — return true iff a is an ancestor (direct or transitive) of b in the current manager tree.

Contradictory operations (e.g., peer(a, b) when a and b already have different managers) should be rejected.

Solution

Maintain two structures:

1. A peer DSU grouping employees who must share the same direct manager.
2. A manager tree over peer groups: each peer group stores a parent pointer to another peer group (the manager’s group).

manager(a, b): find the peer group of b, set its manager-tree parent to the peer group of a. If it already has a different parent, reject.

peer(a, b): union the peer groups of a and b. If both groups already have manager-tree parents, they must agree (otherwise reject).

is_manager(a, b): walk the manager-tree parent chain starting from the peer group of b; return true iff you hit the peer group of a. Use path compression on the manager tree to amortize future queries.

struct Hierarchy {
    DSU peers;
    vector<int> mparent; // manager tree parent (by peer-group root)
    Hierarchy(int n): peers(n), mparent(n, -1) {}

    int group(int x) { return peers.find(x); }

    bool setManager(int a, int b) {
        int ga = group(a), gb = group(b);
        if (mparent[gb] != -1 && mparent[gb] != ga) return false;
        mparent[gb] = ga;
        return true;
    }

    bool setPeer(int a, int b) {
        int ga = group(a), gb = group(b);
        if (ga == gb) return true;
        int pa = mparent[ga], pb = mparent[gb];
        if (pa != -1 && pb != -1 && pa != pb) return false;
        peers.unite(a, b);
        int g = group(a);
        mparent[g] = (pa != -1) ? pa : pb;
        return true;
    }

    bool isManager(int a, int b) {
        int ga = group(a);
        int cur = mparent[group(b)];
        while (cur != -1) {
            if (cur == ga) return true;
            cur = mparent[cur];
        }
        return false;
    }
};

• Time. O(α(n)) per operation amortized.

Discussion

The “two-level DSU” trick — one DSU for equivalence, a parent-pointer tree over its groups for hierarchy — is the cleanest model for this family. Most candidates reach for an adjacency map plus BFS, which bloats to O(n) per query.

Follow-ups

(F1) Bulk imports. A batch of k events processes in O(k α(n)). (F2) LCA queries between two employees: walk both chains with depth tracking; works because the manager tree is small. (F3) Remove a manager relationship. Now you need fully dynamic connectivity on the manager tree. Link-cut tree suffices since it’s always a forest.

Trade-offs

10. Document Undo / Redo With Batches

Problem Statement

Design a key-value document supporting these operations:

• set(k, v) — set key k to value v.
• remove(k) — delete key k.
• beginBatch() / endBatch() — group a sequence of set/remove operations into a single atomic history entry.
• undo() — undo the most recent history entry (either a single op or an entire batch).
• redo() — re-apply the most recently undone history entry.

Memory usage must be proportional to the number of distinct keys touched per history entry, not to the number of writes — a batch that overwrites the same key a million times must record at most one history slot for that key.

Solution

Represent each history entry as a map from key to Change { before, after }, where before is the value at the moment the entry started (plus an “existed” flag) and after is the value the entry committed. Maintain two stacks, undoStack and redoStack.

struct Change { string oldVal; bool hadOld; string newVal; bool hasNew; };
struct HistoryOp { unordered_map<string, Change> changes; };

struct Doc {
    unordered_map<string, string> store;
    vector<HistoryOp> undoStack, redoStack;
    HistoryOp* current;  // non-null iff inside a batch
    bool inBatch;
    Doc() : current(nullptr), inBatch(false) {}

    void recordBefore(HistoryOp& op, const string& k) {
        if (op.changes.find(k) != op.changes.end()) return;
        Change c;
        unordered_map<string,string>::iterator it = store.find(k);
        c.hadOld = (it != store.end());
        c.oldVal = c.hadOld ? it->second : string();
        c.hasNew = false;
        op.changes[k] = c;
    }

    void set(const string& k, const string& v) {
        HistoryOp single;
        HistoryOp& op = inBatch ? *current : single;
        recordBefore(op, k);
        op.changes[k].newVal = v;
        op.changes[k].hasNew = true;
        store[k] = v;
        if (!inBatch) { undoStack.push_back(op); redoStack.clear(); }
    }
    // remove(), beginBatch(), endBatch(), undo(), redo() analogous.
};

On undo(): pop from undoStack, iterate its changes, restore each before, push onto redoStack. redo() is symmetric.

• Time. O(1) per set/remove, O(|changes|) per undo/redo.
• Space. O(distinct keys touched) per history entry.

Discussion

The central design decision is what a history entry stores. Storing full document snapshots is O(n) per entry and trivially correct. Storing per-write diffs is O(writes), which is still too much when the same key is hammered. Storing one before/after pair per touched key gives the desired asymptotic.

Follow-ups

(F1) Nested batches. Replace the current pointer with a stack of open batches; on endBatch(), merge the inner batch into the outer (first-write wins for before, last-write wins for after). (F2) Persistence. Flush committed history entries to a write-ahead log so the state survives a restart. (F3) Collaborative editing. Wrap each history entry in a vector clock and reconcile via operational transformation or CRDTs.

Trade-offs

11. Waiting List System

Problem Statement

Design a FIFO waiting list over n distinguishable users supporting:

• join(u) — append user u to the back of the list.
• leave(u) — remove u from wherever they currently are.
• next() — pop and return the user at the front (FIFO dequeue).
• position(u) — return u’s 1-based index in the current list.

State your policy for duplicate join(u) calls up front (ignore, refresh to back, or reject) — the interview grades you partly on explicitly addressing the ambiguity.

Solution

Two structures work well depending on how often position is called.

A) Doubly linked list + hash map. join, leave, next are all O(1). position walks the list at O(n). This is the classical LRU-style structure and is the right choice when position is rare.

B) Fenwick tree over monotonic tickets. Assign each join a strictly increasing ticket index t, store 1 at index t in a BIT, and use prefix sums for position.

struct WaitingList {
    struct BIT {
        vector<int> t;
        BIT(int n) : t(n + 1, 0) {}
        void upd(int i, int v) { for (; i < (int)t.size(); i += i & -i) t[i] += v; }
        int sum(int i) const {
            int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s;
        }
        int kth(int k) const {                // smallest i with sum(i) >= k
            int pos = 0, log = 1;
            while ((log << 1) < (int)t.size()) log <<= 1;
            for (int d = log; d; d >>= 1) {
                if (pos + d < (int)t.size() && t[pos + d] < k) {
                    pos += d; k -= t[pos];
                }
            }
            return pos + 1;
        }
    };
    BIT bit;
    unordered_map<int,int> ticket;            // user -> ticket index
    int nextTicket;
    WaitingList(int cap) : bit(cap), nextTicket(0) {}
    void join(int u) {
        if (ticket.count(u)) return;          // "ignore" policy
        ++nextTicket; ticket[u] = nextTicket;
        bit.upd(nextTicket, +1);
    }
    void leave(int u) {
        unordered_map<int,int>::iterator it = ticket.find(u);
        if (it == ticket.end()) return;
        bit.upd(it->second, -1);
        ticket.erase(it);
    }
    int position(int u) {
        unordered_map<int,int>::iterator it = ticket.find(u);
        if (it == ticket.end()) return -1;
        return bit.sum(it->second);
    }
};

All operations run in O(log n).

Discussion

The single design decision is whether position is a hot path. Option A is the “LRU cache plus” answer interviewers expect by default; option B is the “we scaled this to millions of users” answer. Mention both.

Follow-ups

(F1) next() must also be O(log n) under option B. Use kth(1) on the BIT — the smallest index with prefix sum >=1. (F2) Rank range queries (“who is between positions 10 and 20?”) — option B generalizes naturally; option A doesn’t. (F3) Multiple wait lists per user. Shard the BIT per list key.

Trade-offs

12. Triplet Packing On A Conveyor Belt (1D)

Problem Statement

Items arrive online, each with an integer size. Maintain an active pool and, after every insertion, check whether any three active items a, b, c satisfy max(a,b,c) - min(a,b,c) < T for a given threshold T. If so, remove all three from the pool and return them as a packed triplet. Otherwise, keep the new item and return “no triplet”.

Solution

Keep the active items in a sorted multiset (std::multiset<int> or a BIT over value buckets). On insertion, look at x’s position and check the three length-3 windows that include it: [i-2, i-1, i], [i-1, i, i+1], [i, i+1, i+2]. If any window has max - min < T, remove those three values and return them.

struct Packer {
    multiset<int> pool;
    int T;
    vector<int> add(int x) {
        pool.insert(x);
        vector<int> arr(pool.begin(), pool.end());
        int i = (int)(lower_bound(arr.begin(), arr.end(), x) - arr.begin());
        for (int lo = max(0, i - 2); lo + 2 < (int)arr.size() && lo <= i; ++lo) {
            if (arr[lo + 2] - arr[lo] < T) {
                vector<int> trip(arr.begin() + lo, arr.begin() + lo + 3);
                for (int k = 0; k < 3; ++k) pool.erase(pool.find(trip[k]));
                return trip;
            }
        }
        return vector<int>();
    }
};

Using a BIT or direct multiset::iterator arithmetic avoids the O(n) copy and brings amortized cost to O(log n) per insertion.

Discussion

The consecutive triple observation — any valid triplet must consist of three values adjacent in sorted order — turns an O(n^3) search into O(log n) per insert. The proof is a pigeonhole argument: if a triplet skips a value between its min and max, substituting the skipped value still keeps the range below T.

Follow-ups

(F1) Quadruplet instead of triplet. Same idea, window of 4. (F2) Different notion of “close”. Not just range; you might want max - min <= T or pairwise differences bounded. Each changes the window length and the pigeonhole proof needs re-checking. (F3) 2D version. See problem 13 — the sorted-window trick breaks in 2D.

Trade-offs

13. Triplet Packing On A 2D Plane

Problem Statement

The same packing rule as problem 12, but each item is a 2D point. Pack three active points if their maximum pairwise Euclidean distance is strictly less than a threshold T. Implement add(p) that inserts a new point and removes a valid triplet if one now exists.

Solution

Bucket points into a uniform grid with cell side s = T / sqrt(2). Any two points in the same cell are within T of each other. Any valid triplet’s three points lie within a 3x3 block of cells centered on any of them, because cells farther than two steps away are more than T apart.

On add(p):

1. Insert p into its cell.
2. Collect candidate points from the 3x3 block around p.
3. For each pair (q, r) of candidates other than p, verify all three pairwise distances are below T. Return the first triplet found.

struct Packer2D {
    double T, s;
    unordered_map<long long, vector<pair<double,double> > > cells;
    Packer2D(double T_) : T(T_), s(T_ / 1.41421356237) {}
    long long key(int cx, int cy) {
        return ((long long)(cx + (1 << 20)) << 21) | (cy + (1 << 20));
    }
    vector<pair<double,double> > add(double x, double y) {
        int cx = (int)floor(x / s), cy = (int)floor(y / s);
        cells[key(cx, cy)].push_back(make_pair(x, y));
        vector<pair<double,double> > cand;
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy) {
                long long k = key(cx + dx, cy + dy);
                unordered_map<long long, vector<pair<double,double> > >::iterator it = cells.find(k);
                if (it != cells.end())
                    for (int j = 0; j < (int)it->second.size(); ++j)
                        cand.push_back(it->second[j]);
            }
        // enumerate pairs within cand together with p = (x,y)
        for (int i = 0; i < (int)cand.size(); ++i)
            for (int j = i + 1; j < (int)cand.size(); ++j) {
                // test (cand[i], cand[j], p)
                // compute pairwise distances and compare to T
                // on success: remove the three points from cells and return them
            }
        return vector<pair<double,double> >();
    }
};

Amortized cost per add is O(k^2) where k is the number of candidates in the neighborhood — small when points are sparsely distributed.

Discussion

Grid bucketing with cell side T / sqrt(d) is the standard pattern for “points within distance T” in d dimensions. The 1D consecutive-triple trick from problem 12 does not generalize, because three close 2D points have no natural sorted order.

Follow-ups

(F1) Higher dimensions. Scale the cell side to T / sqrt(d) and the neighborhood to 3^d. Past d = 4 or so, prefer a KD-tree. (F2) Weighted distance. Replace Euclidean with Manhattan or Chebyshev — cell side becomes T or T / 2 respectively. (F3) Streaming with bounded memory. Evict old points via a sliding window; bucket-by-bucket eviction is O(1) amortized.

Trade-offs

14. Chunking With An Unsplittable Header

Problem Statement

You are given three non-negative integers: header, data, and M (the maximum chunk size in bytes). You must split the stream into chunks such that:

• Every chunk has size at most M.
• The first header bytes form a logical header that cannot straddle a chunk boundary: they must lie entirely within a single chunk.

Return the minimum number of chunks needed, or -1 if no valid split exists.

Solution

If header > M, no split works — return -1. Otherwise the header occupies one chunk, which may additionally carry up to M - header bytes of data. Whatever data remains is split into ceil(remaining / M) uniform chunks.

int minChunks(long long header, long long data, long long M) {
    if (header > M) return -1;
    long long room = M - header;
    long long packed = min(room, data);
    long long leftover = data - packed;
    long long rest = (leftover + M - 1) / M;
    return 1 + (int)rest;
}

• Time. O(1).

Discussion

This is a closed-form arithmetic problem disguised as a packing problem. The only real judgment is the header-sharing decision: always pack data into the header’s chunk if there’s room, because it never increases the chunk count and often decreases it by one.

Follow-ups

(F1) Multiple headers / trailers. Each constraint becomes a case split. (F2) Variable chunk size M_i per position. Becomes a 1D DP. (F3) Minimum wasted padding (pack to M, don’t count leftover holes). Adds a second objective; use ceil carefully.

Trade-offs

15. Sequence With An Index Pointer And Range Moves

Problem Statement

Design a mutable sequence of integers supporting:

• moveIndex(k) — shift the current index pointer by k positions.
• setIndex(i) — set the index pointer to absolute position i.
• moveRange(l, r, to) — remove the closed sub-range [l..r] and re-insert it so that its new starting index (in the post-removal sequence) is to.

Your design must state two things explicitly:

1. Whether the index pointer follows the element it was pointing at (if that element was inside the moved range) or the absolute numeric position.
2. Whether to is an index in the pre-removal or post-removal sequence — the cleanest spec is post-removal.

Solution

For in-memory, small-to-medium sequences, use a std::vector with explicit copy-erase-insert:

struct Seq {
    vector<int> buf;
    int ptr;
    void moveRange(int l, int r, int to) {
        vector<int> chunk(buf.begin() + l, buf.begin() + r + 1);
        buf.erase(buf.begin() + l, buf.begin() + r + 1);
        buf.insert(buf.begin() + to, chunk.begin(), chunk.end());
        // update ptr: if ptr was inside [l..r] it follows to [to .. to + (r-l)];
        // otherwise it shifts by the net displacement of its region.
        if (ptr >= l && ptr <= r) ptr = to + (ptr - l);
        else if (ptr > r) {
            ptr -= (r - l + 1);
            if (ptr >= to) ptr += (r - l + 1);
        } else if (ptr >= to) {
            ptr += (r - l + 1);
        }
    }
};

Each moveRange is O(n) worst case. If the interviewer asks for sublinear range moves, reach for a rope or an implicit-key treap, which splits and concatenates in O(log n) per operation. Sketch the idea; don’t try to code a treap on a whiteboard.

Discussion

OOD rounds grade the API and the edge-case policy as separately as the code. List every ambiguity — duplicate indices, out-of-bounds pointers, overlapping [l..r] and to ranges — and pick a policy before writing a single line.

Follow-ups

(F1) Sublinear moves. Rope / implicit treap / block decomposition (sqrt blocks of size O(sqrt(n))). (F2) Undo support. Wrap the mutator in the batched-change pattern from problem 10. (F3) Persistence. Use a functional treap so every version is an immutable snapshot.

Trade-offs

16. First Occurrence Of A Pattern In A String

Problem Statement

Given two strings text (length n) and pattern (length m), return the index of the first position in text where pattern occurs as a contiguous substring, or -1 if it does not occur. If pattern is empty, return 0.

Constraints. 1 <= n, m <= 10^5. Characters are ASCII.

Solution

The Knuth–Morris–Pratt algorithm runs in O(n + m) time and O(m) extra space. The core idea is to precompute, for each prefix of the pattern, the length of its longest proper prefix that is also a suffix (the “failure function”). On a mismatch during the scan, we jump the pattern pointer back using this table instead of backtracking in the text.

vector<int> failure(const string& p) {
    int m = (int)p.size();
    vector<int> f(m, 0);
    for (int i = 1, k = 0; i < m; ++i) {
        while (k > 0 && p[k] != p[i]) k = f[k - 1];
        if (p[k] == p[i]) ++k;
        f[i] = k;
    }
    return f;
}

int strStr(const string& t, const string& p) {
    if (p.empty()) return 0;
    vector<int> f = failure(p);
    int n = (int)t.size(), m = (int)p.size();
    for (int i = 0, k = 0; i < n; ++i) {
        while (k > 0 && p[k] != t[i]) k = f[k - 1];
        if (p[k] == t[i]) ++k;
        if (k == m) return i - m + 1;
    }
    return -1;
}

• Time. O(n + m). Space. O(m).

Discussion

KMP is one of the highest-ROI algorithms to memorize — the entire matcher is under 30 lines and it resolves a whole family of substring problems (anagram rotations, smallest rotation, longest palindromic prefix). The failure function is the linchpin: it captures the longest self-overlap of every prefix so the matcher can skip positions that provably cannot match.

Follow-ups

(F1) Find all occurrences. Instead of returning on k == m, record the index and reset k = f[m - 1]. (F2) Multi-pattern matching. Use the Aho–Corasick automaton (KMP’s generalization to a trie). (F3) Approximate matching. KMP does not handle edits. Fall back to dynamic programming (O(nm)) or Bitap/Wu–Manber.

Trade-offs

17. Weighted Random Index

Problem Statement

You are given a positive integer array w of length n. Design a data structure that, given no further input, returns an index i in [0, n) with probability proportional to w[i]:

$$ \Pr[i \text{ returned}] = \frac{w_i}{\sum_j w_j}. $$

Multiple queries are issued against the same data structure. Minimize the per-query cost.

Solution

A) Prefix sum + binary search. Precompute the prefix sums of w in O(n). Per query, draw a uniform integer r in [0, sum) and return the first index whose prefix sum is strictly greater than r.

struct WeightedPick {
    vector<long long> pref;
    WeightedPick(const vector<int>& w) : pref(w.size()) {
        pref[0] = w[0];
        for (int i = 1; i < (int)w.size(); ++i) pref[i] = pref[i - 1] + w[i];
    }
    int pick() {
        long long r = ((long long)rand() << 15 ^ rand()) % pref.back();
        return (int)(upper_bound(pref.begin(), pref.end(), r) - pref.begin());
    }
};

O(n) preprocessing, O(log n) per query.

B) Walker’s alias method. Preprocess in O(n) into two length-n arrays prob and alias, then pick uniformly random i and toss a biased coin with probability prob[i]. Each query is O(1).

Discussion

Choose between the two by query frequency. The prefix-sum method is simpler to derive, simpler to code, and fast enough for nearly every interview use case. The alias method is the right answer if the interviewer stresses “millions of queries per second” or asks for constant-time sampling explicitly.

One common pitfall: use upper_bound, not lower_bound. You want the first prefix strictly greater than the drawn r.

Follow-ups

(F1) Weights change over time. Replace the prefix array with a Fenwick tree — O(log n) updates and O(log n) queries. (F2) Sample without replacement. Draw, zero that weight, re-normalize. With a BIT, this is O(k log n) for k samples. (F3) Streaming / reservoir sampling with weights. Use the A-Res algorithm (Efraimidis–Spirakis).

Trade-offs

18. Sum Of Sums Of Arithmetic Subarrays With Step ±1

Problem Statement

You are given an integer array a of length n. Call a subarray good if it has length 1, or if its consecutive differences are all +1, or if its consecutive differences are all -1. Return the sum of the sums of all good subarrays of a.

Constraints. 1 <= n <= 10^5, |a[i]| <= 10^9. The answer fits in a 64-bit integer.

Example. a = [1, 2, 3, 5, 4]. Good subarrays: [1], [2], [3], [5], [4], [1,2], [2,3], [1,2,3], [5,4]. Sum of their sums is 1 + 2 + 3 + 5 + 4 + 3 + 5 + 6 + 9 = 38.

Solution

Decompose the array into maximal runs where consecutive differences are all +1 or all -1. Every good subarray of length >=2 lies entirely inside one run. Two adjacent runs may share an endpoint (e.g. [2,3,4] and [4,3]).

Within a run of length L, use the contribution technique: an element at offset k from the run start (0-indexed) appears in exactly (k + 1) * (L - k) subarrays of that run, including the length-1 subarray consisting of just itself. Because length-1 subarrays are always good, we count them once globally and subtract them from each run’s contribution.

long long goodSum(const vector<int>& a) {
    int n = (int)a.size();
    long long total = 0;
    for (int i = 0; i < n; ++i) total += a[i];        // length-1 subarrays
    int i = 0;
    while (i + 1 < n) {
        int d = a[i + 1] - a[i];
        if (d != 1 && d != -1) { ++i; continue; }
        int j = i + 1;
        while (j + 1 < n && a[j + 1] - a[j] == d) ++j;
        int L = j - i + 1;
        for (int k = 0; k < L; ++k) {
            long long appear = (long long)(k + 1) * (L - k);
            total += (long long)a[i + k] * (appear - 1); // minus length-1
        }
        i = j;                                         // allow shared endpoint
    }
    return total;
}

• Time. O(n). Space. O(1).

Discussion

“Sum of sums of subarrays satisfying property P” is almost always a contribution-technique problem: instead of enumerating subarrays, count how many good subarrays each element belongs to and multiply. The universal formula for 1D subarray contribution is left_starts * right_ends where left_starts = k + 1 and right_ends = L - k within a run of length L.

Follow-ups

(F1) Common difference d for any fixed d. Same algorithm with the run condition a[j + 1] - a[j] == d. (F2) Any common difference. Every maximal run now has its own d; process independently. (F3) Report the number of good subarrays instead of their sum. Just count L * (L + 1) / 2 per run.

Trade-offs

19. Maze Shortest Path With One Wall Break

Problem Statement

You are given an m x n grid where each cell is 0 (empty) or 1 (wall). Starting from (0, 0), you may move in the four cardinal directions through empty cells. Additionally, at most once during the journey, you may walk through a single wall cell as if it were empty. Return the minimum number of steps required to reach (m - 1, n - 1), or -1 if it is unreachable.

Constraints. 1 <= m, n <= 500. Both endpoints are empty cells.

Solution

Breadth-first search in a 3D state space (r, c, usedBreak) where usedBreak is 0 before spending the wall break and 1 after. From state (r, c, k), moving into an empty neighbor keeps k unchanged; moving into a wall requires k == 0 and advances to k = 1.

int shortestPath(vector<vector<int> >& g) {
    int m = (int)g.size(), n = (int)g[0].size();
    vector<vector<vector<int> > > dist(m,
        vector<vector<int> >(n, vector<int>(2, INT_MAX)));
    queue<tuple<int,int,int> > q;
    q.push(make_tuple(0, 0, 0));
    dist[0][0][0] = 0;
    int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        tuple<int,int,int> st = q.front(); q.pop();
        int r = std::get<0>(st), c = std::get<1>(st), k = std::get<2>(st);
        if (r == m - 1 && c == n - 1) return dist[r][c][k];
        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int nk = k + g[nr][nc];
            if (nk > 1) continue;
            if (dist[nr][nc][nk] <= dist[r][c][k] + 1) continue;
            dist[nr][nc][nk] = dist[r][c][k] + 1;
            q.push(make_tuple(nr, nc, nk));
        }
    }
    return -1;
}

• Time. O(m * n * 2). Space. O(m * n * 2).

Discussion

“You may do X once” is the canonical BFS state-augmentation pattern. Turn “once” into a counter attached to the state; the counter’s range is the budget. The key subtlety is to check goal arrival on dequeue rather than on enqueue: BFS’s invariant is that the first dequeue of a state holds its optimal distance.

Follow-ups

(F1) At most k breaks. Extend the state to (r, c, used in [0..k]); total states O(m * n * (k + 1)). This is LC 1293. (F2) Weighted walls. Walls have a cost; use Dijkstra with the same state shape. (F3) Returning the actual path. Store a parent pointer alongside dist and reconstruct backward.

Trade-offs

20. Top K Largest Pair Sums

Problem Statement

Given an integer array a of length n and an integer k, return the k largest values of a[i] + a[j] over all unordered pairs i < j, sorted in non-increasing order.

Constraints. 1 <= k <= n * (n - 1) / 2, n <= 10^5.

Solution

Sort a in non-increasing order. Think of the pair sums as entries of an implicit sorted matrix indexed by (i, j) with i < j; the largest pair sum is a[0] + a[1], and from any explored pair (i, j) the next-best candidates are (i + 1, j) and (i, j + 1). Use a max-heap keyed on the pair sum, expanding greedily and deduplicating with a visited set over (i, j).

vector<long long> topKPairSums(vector<int> a, int k) {
    sort(a.begin(), a.end(), greater<int>());
    int n = (int)a.size();
    priority_queue<tuple<long long,int,int> > pq;
    set<pair<int,int> > seen;
    pq.push(make_tuple((long long)a[0] + a[1], 0, 1));
    seen.insert(make_pair(0, 1));
    vector<long long> out;
    while ((int)out.size() < k && !pq.empty()) {
        tuple<long long,int,int> top = pq.top(); pq.pop();
        long long s = std::get<0>(top);
        int i = std::get<1>(top), j = std::get<2>(top);
        out.push_back(s);
        int ni[2] = {i + 1, i}, nj[2] = {j, j + 1};
        for (int t = 0; t < 2; ++t) {
            int a2 = ni[t], b2 = nj[t];
            if (a2 < b2 && b2 < n && !seen.count(make_pair(a2, b2))) {
                seen.insert(make_pair(a2, b2));
                pq.push(make_tuple((long long)a[a2] + a[b2], a2, b2));
            }
        }
    }
    return out;
}

• Time. O(n log n + k log k).

Discussion

This is the “k-way merge on an implicitly sorted grid” pattern (LC 373). The heap stores a frontier of candidates, each of which expands at most two new candidates, so the heap size stays O(k) and total work is O(k log k) after the initial sort.

Follow-ups

(F1) K smallest pair sums. Flip the sort order and the heap comparator. (F2) K-th pair sum. Binary search on the answer: count pairs with sum >= x using a two-pointer scan over the sorted array. (F3) Pairs from two different arrays A, B. Same frontier expansion with (i, j) indexing into A and B independently.

Trade-offs

21. Shortest Cycle Through A Given Node

Problem Statement

You are given a directed graph with n vertices and a distinguished start vertex s. Return the length (number of edges) of the shortest non-empty directed cycle that begins and ends at s, or -1 if no such cycle exists.

Self-loops count as cycles of length 1.

Constraints. 1 <= n <= 10^5, up to 2 * 10^5 edges.

Solution

Run a single BFS from s, but treat the return to s as an edge relaxation rather than a visited-node skip. Whenever we are about to relax a neighbor equal to s, the current distance plus one is the length of a cycle through s, and BFS guarantees this is the shortest one.

int shortestCycleThrough(int n, const vector<vector<int> >& adj, int s) {
    for (int i = 0; i < (int)adj[s].size(); ++i)
        if (adj[s][i] == s) return 1;                 // self-loop
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)adj[u].size(); ++i) {
            int v = adj[u][i];
            if (v == s) return dist[u] + 1;
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return -1;
}

• Time. O(n + m). Space. O(n).

Discussion

The trick is to allow re-entering s even though BFS’s standard visited-set pattern would forbid it. Keep the visited set for every vertex except s and handle s specially on the relaxation side. Two-cycles (s -> u -> s) and self-loops are both caught cleanly.

Follow-ups

(F1) Shortest cycle anywhere in the graph. Run the BFS from every vertex; the overall complexity becomes O(n(n + m)). (F2) Weighted graph. Replace BFS with Dijkstra and the same relaxation trick; cost becomes O((n + m) log n). (F3) Report the cycle. Maintain a parent array alongside dist and trace the path backward from the relaxation that closed the cycle.

Trade-offs

22. Detect Timed-Out Activities From An Event Log

Problem Statement

You are given a log of events, each of the form (activityId, timestamp, type) where type is either START or END. Each activity has at most one START and one END in the log. Given a timeout threshold T, return all activity IDs whose duration (END - START) strictly exceeds T. If an activity has a START but no END, treat it as still running and compare (now - START) against T.

State your policies for malformed input before coding:

• END without a matching START: ignore or raise.
• Duplicate START for the same ID: ignore the second, raise, or overwrite.
• Events out of order: decide whether to sort or scan once.

Solution

Walk the log once, recording START timestamps in a hash map. On an END, look up the corresponding START and compare.

vector<string> timedOutActivities(const vector<Log>& logs, long long T,
                                  long long now) {
    unordered_map<string, long long> started;
    unordered_set<string> out;
    for (int i = 0; i < (int)logs.size(); ++i) {
        const Log& L = logs[i];
        if (L.type == START) {
            started[L.id] = L.ts;
        } else {
            unordered_map<string,long long>::iterator it = started.find(L.id);
            if (it == started.end()) continue;       // malformed END, ignore
            if (L.ts - it->second > T) out.insert(L.id);
            started.erase(it);
        }
    }
    for (unordered_map<string,long long>::iterator it = started.begin();
         it != started.end(); ++it) {
        if (now - it->second > T) out.insert(it->first);
    }
    return vector<string>(out.begin(), out.end());
}

• Time. O(n) if logs are already in timestamp order, otherwise O(n log n) for the initial sort.

Discussion

OOD rounds grade you as much on the schema and policy decisions as on the code. Write the Log struct, the tracker class with its method signatures, and an explicit list of policies before the algorithm.

Follow-ups

(F1) Multiple start-end pairs per ID. Decide whether to sum durations or track each independently. Swap the value of started to a vector. (F2) Streaming input with bounded memory. Expire oldest open STARTs beyond a window, reporting them as timed-out. (F3) Report by user / session, not activity. Group by the parent key first.

Trade-offs

23. Partition Strings By Prefix Match In Place

Problem Statement

You are given an array of strings a and an oracle function isValid(s) that returns true iff s begins with a fixed (unknown to you) prefix P. Rearrange a in place so that every valid string precedes every invalid string, and return the number of valid strings. The relative order within each group does not need to be preserved. Minimize the number of swaps performed and the number of calls to isValid.

Solution

Two-pointer partition, identical in shape to the Dutch national flag algorithm. Advance l past valid strings from the left; retreat r past invalid strings from the right; when both pointers have found a misplaced element, swap them and advance both.

int partitionByValidity(vector<string>& a) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        if (isValid(a[l])) { ++l; continue; }
        if (!isValid(a[r])) { --r; continue; }
        swap(a[l], a[r]);
        ++l; --r;
    }
    return l;                                         // count of valid strings
}

• Swaps. At most min(valid, invalid), which is optimal because each swap fixes two misplaced elements at once.
• Oracle calls. Each position is queried at most once on the way in (the caches isValid(a[l]) and isValid(a[r]) can be memoized if repeated calls are expensive), so at most O(n) total.
• Time. O(n * L) including the prefix check inside the oracle.

Discussion

“Partition in place, minimize swaps” is almost always Dutch flag. The key win over the naive two-pass approach (count valids, pack them to the front) is avoiding the second scan and the temporary array. Always mention oracle complexity separately from algorithmic complexity.

Follow-ups

(F1) Preserve relative order within each group. Dutch flag does not preserve order; use a stable partition — typically two passes with a buffer. (F2) Multi-class partition. Three-way partition (Dutch flag’s original form) for <, =, >. (F3) Oracle is very expensive. Cache results in a hash map keyed on the string, so each string is queried exactly once.

Trade-offs

24. URL Shortener — Shortest Unique Strings With Bounded Char Frequency

Problem Statement

Design a URLShortener whose getNext() method returns an infinite sequence of unique strings over the lowercase alphabet such that:

1. Strings are returned in order of non-decreasing length, and
2. No character appears more than T times in any returned string.

Every call to getNext() returns the next string satisfying both rules.

Solution

Enumerate strings in lexicographic base-26 order (a, b, …, z, aa, ab, …) using a counter-style increment step. For each candidate, verify that every character’s frequency is at most T; if so, return it, otherwise advance and retry.

struct URLShortener {
    string cur;
    int T;
    URLShortener(int T_) : cur(""), T(T_) {}
    void inc() {
        for (int i = (int)cur.size() - 1; i >= 0; --i) {
            if (cur[i] != 'z') { ++cur[i]; return; }
            cur[i] = 'a';
        }
        cur = string(cur.size() + 1, 'a');
    }
    bool ok() const {
        int cnt[26] = {0};
        for (int i = 0; i < (int)cur.size(); ++i)
            if (++cnt[cur[i] - 'a'] > T) return false;
        return true;
    }
    string getNext() {
        do { inc(); } while (!ok());
        return cur;
    }
};

Discussion

Enumerate-then-filter is the right pattern for “generate unique items in an order” whenever the validity predicate is cheap and most candidates pass. For T >= 2 essentially all strings pass, so amortized cost per call is O(L) where L grows as O(log_{26} n) for the n-th call. For T == 1 you’re emitting strings with distinct characters only, which has rapidly shrinking density and benefits from a direct combinatorial enumeration.

Follow-ups

(F1) Multi-worker generation. Stripe the counter space across P workers by offset and step. (F2) Persistence. Store the current counter to durable storage on each call. (F3) Weighted alphabet. Use base-k enumeration over the chosen subset.

Trade-offs

25. LRU Cache With Time-Based Expiration

Problem Statement

Implement a cache with:

• int get(int key) — return the value if it exists and is not expired, else -1.
• void put(int key, int value) — insert or update the entry; evict the least recently used entry if the cache is at capacity.

Every entry expires automatically TTL milliseconds after insertion (specify this rule up front — most candidates miss it). Expired entries must not be returned. Target O(1) amortized for both operations.

Solution

A hash map plus a doubly linked list (the LRU 146 template), augmented with an insertTime on each node and a lazy-deletion check at the top of get.

struct LRUTTL {
    struct Node { int k, v; long long t; Node *prev, *next; };
    int cap;
    long long ttl;
    unordered_map<int, Node*> mp;
    Node *head, *tail;
    long long (*now)();                                // monotonic clock

    LRUTTL(int cap_, long long ttl_, long long (*now_)())
        : cap(cap_), ttl(ttl_), now(now_) {
        head = new Node{0,0,0,nullptr,nullptr};
        tail = new Node{0,0,0,nullptr,nullptr};
        head->next = tail; tail->prev = head;
    }
    void detach(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void addFront(Node* n) {
        n->next = head->next; n->prev = head;
        head->next->prev = n; head->next = n;
    }
    int get(int k) {
        unordered_map<int,Node*>::iterator it = mp.find(k);
        if (it == mp.end()) return -1;
        Node* n = it->second;
        if (now() - n->t > ttl) { detach(n); mp.erase(it); delete n; return -1; }
        detach(n); addFront(n);
        return n->v;
    }
    void put(int k, int v) {
        long long t = now();
        unordered_map<int,Node*>::iterator it = mp.find(k);
        if (it != mp.end()) {
            it->second->v = v; it->second->t = t;
            detach(it->second); addFront(it->second);
            return;
        }
        if ((int)mp.size() == cap) {
            Node* old = tail->prev;
            mp.erase(old->k); detach(old); delete old;
        }
        Node* n = new Node{k, v, t, nullptr, nullptr};
        addFront(n); mp[k] = n;
    }
};

• Time. O(1) amortized per op.

Discussion

Always use a monotonic clock rather than wall time. Clarify up front whether get refreshes the TTL — interviewers almost always say “no, TTL runs from insertion time”. Lazy deletion is almost always the right strategy: expired entries cost nothing until they are touched or evicted by the LRU policy.

Follow-ups

(F1) Bounded memory under bursty writes. Run a background sweeper that walks the tail every T seconds and removes expired entries. (F2) Priority-based expiration. Replace the DLL with a min-heap keyed on expiry time; cost becomes O(log n) per op. (F3) Hierarchical TTLs. Maintain one LRU per TTL class; promote on access between classes.

Trade-offs

26. Count Shortest Paths Between Two Nodes

Problem Statement

Given a weighted undirected graph with non-negative edge weights, find the number of distinct shortest paths from node s to node t.

Input: Integer n (number of nodes), adjacency list of weighted edges, source s, target t.

Output: Number of shortest paths modulo 10^9 + 7.

Constraints: 1 ≤ n ≤ 100000; edge weights in [0, 10^6].

Example:

Graph: 0-1 (weight 1), 0-2 (weight 1), 1-3 (weight 1), 2-3 (weight 1)
s=0, t=3
Answer: 2 (paths 0→1→3 and 0→2→3)

Solution

Maintain two arrays: dist[v] (shortest distance to v) and ways[v] (count of shortest paths to v). Use Dijkstra’s algorithm with a min-heap. When relaxing an edge (u, v, w): - If the new path is shorter: update dist and reset ways. - If the new path equals the current shortest: add the count.

#include <queue>
#include <vector>
using namespace std;

const long long MOD = 1e9 + 7;

long long countShortestPaths(int n, vector<vector<pair<int, long long>>>& adj, int s, int t) {
    vector<long long> dist(n, LLONG_MAX), ways(n, 0);
    dist[s] = 0;
    ways[s] = 1;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int> > > pq;
    pq.push(make_pair(0LL, s));

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            long long w = adj[u][i].second;
            long long nd = d + w;

            if (nd < dist[v]) {
                dist[v] = nd;
                ways[v] = ways[u];
                pq.push(make_pair(nd, v));
            } else if (nd == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    return ways[t];
}

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

Discussion

The key insight is tracking both distance and path count in parallel. For unweighted graphs, use BFS with the same counting rule. Be cautious with zero-weight edges: they can create cycles with total weight 0, leading to infinitely many paths. Always confirm the constraint that weights are non-negative.

Follow-ups

(F1) Unweighted graph: Replace Dijkstra with BFS; the counting logic remains identical.

(F2) 0-1 weighted edges: Use 0-1 BFS with a deque instead of a priority queue.

(F3) Find one shortest path: Backtrack from t to s using the decreasing distance property.

Trade-offs

27. Count Lakes In Island

Problem Statement

Given a 2D grid with 1 representing land and 0 representing water, given a cell (r, c) on land, count the number of enclosed water bodies (lakes) inside the island containing (r, c). A lake is a water component that does not touch the grid boundary.

Input: 2D grid, integers r, c.

Output: Number of lakes.

Constraints: 1 ≤ rows, cols ≤ 2000.

Example:

Grid: 1 1 1 1
      1 0 0 1
      1 0 1 1
      1 1 1 1
r=0, c=0 → 1 lake (the 0s in the middle)

Solution

1. Flood-fill the island containing (r, c) to mark all land cells.
2. For each water cell adjacent to the island, perform a flood-fill and check if it touches the grid boundary.
3. Count water components that do not touch the boundary.

#include <queue>
#include <vector>
using namespace std;

int countLakes(vector<vector<int>>& g, int r, int c) {
    int m = g.size(), n = g[0].size();
    if (g[r][c] != 1) return 0;

    vector<vector<int>> mark(m, vector<int>(n, 0));
    queue<pair<int, int>> q;
    q.push(make_pair(r, c));
    mark[r][c] = 1;

    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int ny = y + dr[k], nx = x + dc[k];
            if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
            if (g[ny][nx] == 1 && !mark[ny][nx]) {
                mark[ny][nx] = 1;
                q.push(make_pair(ny, nx));
            }
        }
    }

    int lakes = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == 0 && mark[i][j] == 0) {
                bool adjLand = false;
                for (int k = 0; k < 4; ++k) {
                    int ny = i + dr[k], nx = j + dc[k];
                    if (ny >= 0 && nx >= 0 && ny < m && nx < n && mark[ny][nx] == 1) {
                        adjLand = true;
                    }
                }
                if (!adjLand) continue;

                queue<pair<int, int>> w;
                w.push(make_pair(i, j));
                mark[i][j] = 2;
                bool touchesEdge = false;

                while (!w.empty()) {
                    int y = w.front().first;
                    int x = w.front().second;
                    w.pop();
                    if (y == 0 || x == 0 || y == m - 1 || x == n - 1) {
                        touchesEdge = true;
                    }
                    for (int k = 0; k < 4; ++k) {
                        int ny = y + dr[k], nx = x + dc[k];
                        if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
                        if (g[ny][nx] == 0 && mark[ny][nx] == 0) {
                            mark[ny][nx] = 2;
                            w.push(make_pair(ny, nx));
                        }
                    }
                }
                if (!touchesEdge) lakes++;
            }
        }
    }
    return lakes;
}

• Time: O(mn)
• Space: O(mn)

Discussion

The critical distinction is that a lake must be bounded by the specific island containing the given cell, not just any land. The boundary-check is the canonical approach for identifying enclosed regions. Water touching any edge of the grid is ocean, not a lake.

Follow-ups

(F1) Union-Find variant: Merge land cells, then for each water component check if it contains any boundary cell and is adjacent to the queried island.

(F2) All islands: Modify to return lakes for every island in the grid.

(F3) Return lake sizes: Collect the sizes during the second flood-fill.

Trade-offs

28. Expression Add Operators

Problem Statement

Given a digit string num and an integer target, return all expressions by inserting +, -, * between digits that evaluate to target. No leading zeros on multi-digit numbers (but 0 as a single digit is allowed).

Input: String num (digits only), integer target.

Output: All valid expressions as strings.

Constraints: 1 ≤ len(num) ≤ 10; 0 ≤ target ≤ 2^31 - 1.

Example:

num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Solution

Use backtracking with two running values: - total: the fully evaluated expression so far. - prevMul: the value of the most recent multiplicative term (needed to handle operator precedence).

When appending a number x: - +x → total = total + x, prevMul = x - -x → total = total - x, prevMul = -x - *x → total = total - prevMul + prevMul * x, prevMul = prevMul * x

#include <string>
#include <vector>
using namespace std;

void dfs(const string& num, int target, int i, long long total, long long prevMul,
         string expr, vector<string>& out) {
    if (i == (int)num.size()) {
        if (total == target) {
            out.push_back(expr);
        }
        return;
    }

    for (int j = i; j < (int)num.size(); ++j) {
        if (j > i && num[i] == '0') break;
        long long x = stoll(num.substr(i, j - i + 1));

        if (i == 0) {
            dfs(num, target, j + 1, x, x, num.substr(i, j - i + 1), out);
        } else {
            dfs(num, target, j + 1, total + x, x, expr + "+" + num.substr(i, j - i + 1), out);
            dfs(num, target, j + 1, total - x, -x, expr + "-" + num.substr(i, j - i + 1), out);
            dfs(num, target, j + 1, total - prevMul + prevMul * x, prevMul * x,
                expr + "*" + num.substr(i, j - i + 1), out);
        }
    }
}

vector<string> addOperators(const string& num, int target) {
    vector<string> result;
    dfs(num, target, 0, 0, 0, "", result);
    return result;
}

• Time: O(4^n · n) where n = len(num)
• Space: O(4^n) for output

Discussion

The prevMul variable is the key insight for handling operator precedence without building an explicit AST. When encountering *, subtract the previous term and add its product with the new operand. The leading-zero check prevents numbers like 01 but allows 0 alone.

Follow-ups

(F1) Find count only: Return the count of valid expressions instead of the expressions themselves.

(F2) Division operator: Track integer division similarly to multiplication.

(F3) Parentheses: Allow grouping; requires a more complex state representation.

Trade-offs

29. Sorted Array Diff-Graph Path Queries

Problem Statement

Given a sorted array arr and a value diff, build a graph where indices i, j are connected if |arr[i] - arr[j]| <= diff. Answer queries: is there a path from u to v?

Input: Sorted array, integer diff, list of queries [u, v].

Output: For each query, true/false.

Constraints: 1 ≤ n ≤ 100000; 0 ≤ diff ≤ 10^6.

Example:

arr = [4, 6, 10, 15], diff = 3
Connections: 4-6, 6-10 (no connection 10-15)
Query (0, 2) → true (path 0→1→2)
Query (0, 3) → false

Solution

Observe that because arr is sorted, the graph consists of maximal runs where adjacent elements satisfy arr[i+1] - arr[i] <= diff. All indices within a run are transitively connected. Assign run IDs and answer each query in O(1).

#include <vector>
using namespace std;

vector<bool> solveQueries(vector<int>& arr, int diff, vector<pair<int, int>>& queries) {
    int n = arr.size();
    vector<int> runId(n);
    int id = 0;
    runId[0] = 0;

    for (int i = 1; i < n; ++i) {
        if (arr[i] - arr[i - 1] > diff) {
            id++;
        }
        runId[i] = id;
    }

    vector<bool> result;
    for (size_t i = 0; i < queries.size(); ++i) {
        int u = queries[i].first;
        int v = queries[i].second;
        result.push_back(runId[u] == runId[v]);
    }
    return result;
}

• Time: O(n + q) where q = number of queries
• Space: O(n)

Discussion

The sorted property is essential. Without it, the problem becomes full-fledged graph connectivity (requiring Union-Find or DFS), which is O(n²) or O((n+e)α(n)) respectively. By leveraging the sorted order, we identify the structure in one pass.

Follow-ups

(F1) Descending array: Reverse the array or iterate from top; logic remains the same.

(F2) Unsorted input: Sort first, O(n log n), then apply the same algorithm. This is optimal because the sorted structure is necessary for the fast query resolution.

(F3) Range updates to diff: Recompute run IDs after each diff change (no way around O(n) per update).

Trade-offs

30. Subarray Sum Equals K

Problem Statement

Given an array nums and integer k, count the number of contiguous subarrays that sum to k.

Input: Array nums, integer k.

Output: Count of subarrays.

Constraints: 1 ≤ n ≤ 200000; -100000 ≤ nums[i] ≤ 100000.

Example:

nums = [1, 1, 1], k = 2
Output: 2 (subarrays [1,1] at positions 0-1 and 1-2)

Solution

Maintain a hash map of prefix sums. For each cumulative sum s, the number of subarrays ending here with sum k is the count of occurrences of s - k. Initialize the map with {0: 1} to handle subarrays starting at index 0.

#include <unordered_map>
#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    cnt[0] = 1;
    int s = 0, ans = 0;

    for (size_t i = 0; i < nums.size(); ++i) {
        s += nums[i];
        if (cnt.find(s - k) != cnt.end()) {
            ans += cnt[s - k];
        }
        cnt[s]++;
    }
    return ans;
}

• Time: O(n)
• Space: O(n)

Discussion

The prefix sum technique is foundational. The initialization cnt[0] = 1 is crucial—it represents the empty prefix. For negative numbers, this approach is necessary; a sliding window cannot work because the sum can decrease. The extension to streaming is immediate: call the update logic on each arriving element.

Follow-ups

(F1) Streaming: Keep the same hash map and running sum; call the update on each new element. The count is available at any time.

(F2) Bounded window: Maintain a sliding window of length W; decrement cnt[s_old] when element W+1 steps away.

(F3) Circular array: Compute prefix sums for the array concatenated with itself, excluding the full-array case.

Trade-offs

31. Morse Code Decoding

Problem Statement

Given a no-delimiter Morse string s and a mapping from A-Z to Morse codes, output: 1. The number of valid full-length decodings mod 10^9 + 7. 2. The lexicographically smallest up to K decoded strings.

Input: Morse string, character-to-code map, K.

Output: Count and list of K smallest decodings.

Constraints: 1 ≤ len(s) ≤ 100; 1 ≤ K ≤ 10.

Example:

s = ".-", codes = {A: ".-", ...}
Decodings = ["A"]
Count = 1

Solution

Use dynamic programming with a Trie for fast code matching. dp[i] = number of ways to decode s[i..n-1]. For counting, at each position walk the Trie and accumulate solutions. For top-K, use best-first search with a priority queue ordered lexicographically.

#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<long long> countDecodings(const string& s, map<char, string>& codes) {
    int n = s.size();
    vector<long long> dp(n + 1, 0);
    dp[n] = 1;

    map<char, int> codeLen;
    for (map<char, string>::iterator it = codes.begin(); it != codes.end(); ++it) {
        codeLen[it->first] = (int)it->second.size();
    }

    for (int i = n - 1; i >= 0; --i) {
        for (map<char, string>::iterator it = codes.begin(); it != codes.end(); ++it) {
            const string& code = it->second;
            if (i + (int)code.size() <= n &&
                s.substr(i, code.size()) == code) {
                dp[i] += dp[i + (int)code.size()];
                dp[i] %= 1000000007LL;
            }
        }
    }
    return dp;
}

vector<string> topKDecodings(const string& s, map<char, string>& codes, int K) {
    vector<long long> dp = countDecodings(s, codes);
    vector<string> result;

    priority_queue<pair<string, int> > pq;
    pq.push(make_pair(string(""), 0));

    while (!pq.empty() && (int)result.size() < K) {
        string current = pq.top().first;
        int idx = pq.top().second;
        pq.pop();

        if (idx == (int)s.size()) {
            result.push_back(current);
            continue;
        }
        if (dp[idx] == 0) continue;

        vector<pair<char, string> > candidates;
        for (map<char, string>::iterator it = codes.begin(); it != codes.end(); ++it) {
            candidates.push_back(make_pair(it->first, it->second));
        }
        sort(candidates.begin(), candidates.end());

        for (size_t i = 0; i < candidates.size(); ++i) {
            char letter = candidates[i].first;
            const string& code = candidates[i].second;
            if (idx + (int)code.size() <= (int)s.size() &&
                s.substr(idx, code.size()) == code) {
                pq.push(make_pair(current + letter, idx + (int)code.size()));
            }
        }
    }
    return result;
}

• Time (count): O(n · Σ|codes|)
• Time (top-K): O(K · n · 26 · log(K))
• Space: O(n) for DP

Discussion

The DP for counting is straightforward. The top-K problem requires carefully ordering candidates lexicographically and pruning branches with zero completions. The two approaches share the DP computation, which is reused.

Follow-ups

(F1) DFS with pruning: Recursively try letters in alphabetical order, prune using DP.

(F2) Streaming Morse: Maintain DP incrementally as the Morse string grows.

(F3) Ambiguous Morse: Allow multiple possible codes for the same character.

Trade-offs

32. Maximum Overlap Of Squares

Problem Statement

Given n axis-aligned squares (defined as x, y, side length L), find the maximum number of squares covering any single point.

Input: List of squares (x, y, L).

Output: Maximum overlap count.

Constraints: 1 ≤ n ≤ 10000.

Example:

Squares: (0,0,2), (1,1,2)
Maximum overlap: 2 (at point (1,1))

Solution

Use a 2D sweep-line algorithm. Sweep a vertical line left-to-right. Maintain active squares (those intersecting the sweep line) using a segment tree to track the maximum coverage in the y-direction at each x-coordinate. Events are created at x (entry) and x + L (exit) for each square.

#include <vector>
#include <algorithm>
using namespace std;

int maxSquareOverlap(vector<tuple<int, int, int>>& squares) {
    vector<tuple<int, int, int, int>> events;
    int n = squares.size();

    for (int i = 0; i < n; ++i) {
        int x = std::get<0>(squares[i]);
        int y = std::get<1>(squares[i]);
        int L = std::get<2>(squares[i]);
        events.push_back(make_tuple(x, 0, y, y + L));
        events.push_back(make_tuple(x + L, 1, y, y + L));
    }

    sort(events.begin(), events.end());

    int peak = 0;
    map<int, int> activeIntervals;

    for (size_t i = 0; i < events.size(); ++i) {
        int type = std::get<1>(events[i]);
        int y_lo = std::get<2>(events[i]);
        int y_hi = std::get<3>(events[i]);

        if (type == 0) {
            if (activeIntervals.find(y_lo) == activeIntervals.end()) {
                activeIntervals[y_lo] = 0;
            }
            activeIntervals[y_lo]++;
        } else {
            activeIntervals[y_lo]--;
            if (activeIntervals[y_lo] == 0) {
                activeIntervals.erase(y_lo);
            }
        }

        int maxCurrent = 0;
        for (map<int, int>::iterator it = activeIntervals.begin(); it != activeIntervals.end(); ++it) {
            maxCurrent = max(maxCurrent, it->second);
        }
        peak = max(peak, maxCurrent);
    }

    return peak;
}

• Time: O(n log n)
• Space: O(n)

Discussion

The key is decomposing the 2D problem into a 1D sweep with a secondary 1D data structure (segment tree or interval map). The segment tree is more complex but supports efficient range updates. For small n, a simpler coordinate-compression approach with a 2D difference array works.

Follow-ups

(F1) Rectangles: The algorithm generalizes trivially; squares have no special advantage.

(F2) Query points: Precompute a 2D grid; answer point queries in O(1).

(F3) Range queries: Add queries for maximum overlap in a sub-rectangle.

Trade-offs

33. Range Overwrite Updates

Problem Statement

Given an array A of length n and m update queries (l, r, k) that overwrite A[l..r] = k, apply all queries in order and output the final array. Must handle this better than O(n·m).

Input: Array A, list of (l, r, k) updates.

Output: Final array after all updates.

Constraints: 1 ≤ n, m ≤ 200000.

Example:

A = [1,2,3], queries = [(0,1,5), (1,2,9)]
After (0,1,5): [5,5,3]
After (1,2,9): [5,9,9]
Output: [5,9,9]

Solution

Use a segment tree with lazy propagation for range assignment. Maintain a lazy tag indicating that a subtree is entirely assigned to a value. Push tags downward during updates.

#include <vector>
#include <algorithm>
using namespace std;

struct SegTree {
    int n;
    vector<long long> val;
    vector<long long> lazy;
    vector<bool> hasLazy;

    void apply(int p, long long v) {
        val[p] = v;
        lazy[p] = v;
        hasLazy[p] = true;
    }

    void push(int p) {
        if (hasLazy[p]) {
            apply(p * 2, lazy[p]);
            apply(p * 2 + 1, lazy[p]);
            hasLazy[p] = false;
        }
    }

    void update(int p, int l, int r, int ql, int qr, long long v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(p, v);
            return;
        }
        push(p);
        int m = (l + r) / 2;
        update(p * 2, l, m, ql, qr, v);
        update(p * 2 + 1, m + 1, r, ql, qr, v);
    }

    long long query(int p, int l, int r, int idx) {
        if (l == r) {
            if (hasLazy[p]) return lazy[p];
            return val[p];
        }
        push(p);
        int m = (l + r) / 2;
        if (idx <= m) return query(p * 2, l, m, idx);
        else return query(p * 2 + 1, m + 1, r, idx);
    }
};

• Time: O((n + m) log n)
• Space: O(n)

Discussion

The segment tree approach is straightforward and easy to explain. An alternative is the “offline paint-reverse” technique: process queries in reverse, maintaining the next unpainted index with a DSU. This achieves O((n + m)α(n)), which is asymptotically better.

Follow-ups

(F1) Offline painting in reverse: Process queries backward; track next-unpainted indices using union-find.

(F2) Constant k: If all queries use the same k, compute the union of intervals and mark covered cells directly.

(F3) Interval set (Chtholly tree): Maintain contiguous runs; split, erase, and insert on updates.

Trade-offs

34. Board Game — Tokens Move By Three

Problem Statement

A board string of length N with characters . (empty), T (token), C (coin). Tokens move exactly 3 cells right. Tokens cannot occupy the same cell. Each coin is collected on first touch. Return the maximum coins collectable.

Input: Board string, N ≤ 100.

Output: Maximum coins.

Constraints: Tokens can only move, not stay.

Example:

Board: "T..C.T.C", tokens at positions 0 and 5
Token at 0 can reach position 3 (collects coin at 3)
Token at 5 can reach position 8 (out of bounds)
Max coins: 1

Solution

Use modulo-3 decomposition. A token at index i can only occupy indices with the same value mod 3. Solve each “lane” independently. Within a lane, tokens move one step at a time (3 cells in the original board). Greedily assign final positions: rightmost token extends farthest, and subsequent tokens extend below it.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int maxCoinsPerLane(string& lane) {
    int L = lane.size();
    vector<int> tokens;
    for (int i = 0; i < L; ++i) {
        if (lane[i] == 'T') tokens.push_back(i);
    }

    vector<bool> covered(L, false);
    int right = L - 1;

    for (int k = (int)tokens.size() - 1; k >= 0; --k) {
        int p = tokens[k];
        int q = min(right, L - 1);
        if (q < p) continue;

        for (int j = p; j <= q; ++j) {
            covered[j] = true;
        }
        right = q - 1;
    }

    int count = 0;
    for (int i = 0; i < L; ++i) {
        if (covered[i] && lane[i] == 'C') count++;
    }
    return count;
}

int maxCoins(string& board) {
    int n = board.size();
    int total = 0;

    for (int r = 0; r < 3; ++r) {
        string lane;
        for (int i = r; i < n; i += 3) {
            lane += board[i];
        }
        total += maxCoinsPerLane(lane);
    }
    return total;
}

• Time: O(N)
• Space: O(N)

Discussion

The key insight is the modulo-3 decomposition, which reduces the 2D movement constraint to independent 1D problems. Tokens naturally preserve ordering within a lane, so greedy assignment works: rightmost token extends to the right boundary, and each preceding token extends as far right as possible without exceeding the next token’s final position.

Follow-ups

(F1) Variable move distance: Generalize to move by k; decompose by mod k.

(F2) Coins consumed: Subtract coin weight from collection count.

(F3) Multiple passes: Allow tokens to move multiple times; becomes a more complex DP.

Trade-offs

35. Mahjong Winning Hand

Problem Statement

Given 14 tiles, determine if they can be partitioned into exactly 4 melds and 1 pair. - Meld = triplet [x, x, x] or sequence [x, x+1, x+2]. - Pair = [y, y].

Return true/false.

Input: List of 14 tile values.

Output: Boolean.

Constraints: Tile values in [0, 8] (standard Mahjong tiles).

Example:

Tiles: [1,1,1,2,2,3,3,3,4,4,4,5,5,5,5]
Valid: Yes (multiple partitions work)

Solution

For each potential pair, remove it and check if the remaining 12 tiles form 4 melds using backtracking. To form melds, greedily take the smallest remaining tile and try either a triplet or a sequence. Backtrack if no progress is made.

#include <vector>
#include <map>
using namespace std;

bool canMelds(map<int, int>& cnt) {
    if (cnt.empty()) return true;

    int x = cnt.begin()->first;

    if (cnt[x] >= 3) {
        cnt[x] -= 3;
        if (cnt[x] == 0) cnt.erase(x);
        if (canMelds(cnt)) return true;
        cnt[x] += 3;
    }

    if (cnt.find(x) != cnt.end() && cnt.find(x + 1) != cnt.end() &&
        cnt.find(x + 2) != cnt.end()) {
        for (int t = x; t <= x + 2; ++t) {
            cnt[t]--;
            if (cnt[t] == 0) cnt.erase(t);
        }
        if (canMelds(cnt)) return true;
        for (int t = x; t <= x + 2; ++t) {
            cnt[t]++;
        }
    }
    return false;
}

bool isWinning(vector<int>& tiles) {
    map<int, int> cnt;
    for (size_t i = 0; i < tiles.size(); ++i) {
        cnt[tiles[i]]++;
    }

    for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); ++it) {
        if (it->second >= 2) {
            int y = it->first;
            cnt[y] -= 2;
            if (cnt[y] == 0) cnt.erase(y);
            if (canMelds(cnt)) return true;
            cnt[y] += 2;
        }
    }
    return false;
}

• Time: O(2^4 · distinct tiles) per pair = trivially fast for 14 tiles
• Space: O(9) for tile counts

Discussion

Processing the smallest tile first prevents duplicate work. Trying triplet before sequence is arbitrary but consistent. The fixed hand size makes exponential recursion practical. Critical: the pair count is 2 + melds count is 3 × 4 = 14 tiles total.

Follow-ups

(F1) Shanten (distance to win): Try adding each possible tile value; check if winning.

(F2) Seven pairs yaku: Detect alternative winning patterns.

(F3) Open hand support: Modify meld rules for declared melds.

Trade-offs

36. All Length-≥3 Subsequences Are Valid Words

Problem Statement

Given string s and an oracle isWord(t), return true if every subsequence of s with length ≥ 3 is a valid word.

Input: String s, oracle function.

Output: Boolean.

Constraints: 1 ≤ len(s) ≤ 25.

Example:

s = "abc", isWord checks a dictionary
Subsequences of length ≥ 3: "abc"
If "abc" is in the dictionary, return true; else false.

Solution

Enumerate all 2^n subsequences using bitmasks. For each mask with at least 3 bits set, extract the corresponding substring and check if it’s a valid word. Deduplicate subsequence strings before checking the oracle.

#include <string>
#include <set>
#include <vector>
using namespace std;

bool allSubsequencesValid(const string& s, set<string>& dictionary) {
    int n = s.size();
    set<string> seen;

    for (int mask = 0; mask < (1 << n); ++mask) {
        if (__builtin_popcount(mask) < 3) continue;

        string t;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t += s[i];
            }
        }

        if (seen.find(t) != seen.end()) continue;
        seen.insert(t);

        if (dictionary.find(t) == dictionary.end()) {
            return false;
        }
    }
    return true;
}

• Time: O(2^n · n)
• Space: O(2^n) for deduplicated subsequences

Discussion

Enumeration is feasible for n ≤ 20-25. Deduplication is essential to avoid redundant oracle calls. Duplicate subsequences arise when s has repeated characters.

Follow-ups

(F1) Count distinct valid subsequences: Return the count instead.

(F2) Return a counterexample: Output the first invalid subsequence found.

(F3) Larger n: No known polynomial algorithm; the problem is inherently exponential.

Trade-offs

37. All Length-≥3 Subsequences Have Some Anagram That Is Valid

Problem Statement

Like problem 36, but for each length-≥3 subsequence, we only need some anagram (permutation) of it to be a valid word. Equivalently, check if the multiset of characters has a corresponding dictionary word.

Input: String s, list of dictionary words.

Output: Boolean.

Constraints: 1 ≤ len(s) ≤ 25; dict size ≤ 100000.

Example:

s = "abc", dict = ["abc", "bca", "cab", "...]
All length-≥3 subsequences of s have multiset {a,b,c}
All permutations of {a,b,c} exist in dict (e.g., "abc")
Return true.

Solution

Precompute a set of character multiset signatures from the dictionary. Enumerate distinct multisets of length-≥3 subsequences and check membership in the signature set.

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

bool allSubsequenceAnagramsValid(const string& s, vector<string>& dictionary) {
    set<string> sigs;
    for (size_t i = 0; i < dictionary.size(); ++i) {
        if (dictionary[i].size() >= 3) {
            string sig = dictionary[i];
            sort(sig.begin(), sig.end());
            sigs.insert(sig);
        }
    }

    int n = s.size();
    set<string> seen;

    for (int mask = 0; mask < (1 << n); ++mask) {
        if (__builtin_popcount(mask) < 3) continue;

        string t;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t += s[i];
            }
        }

        string sig = t;
        sort(sig.begin(), sig.end());

        if (seen.find(sig) != seen.end()) continue;
        seen.insert(sig);

        if (sigs.find(sig) == sigs.end()) {
            return false;
        }
    }
    return true;
}

• Time: O(d log d + 2^n · n) where d = dictionary size
• Space: O(d + 2^n)

Discussion

The key insight is reducing the problem to multisets: two subsequences are equivalent if they have the same character counts. Preprocessing the dictionary once is critical for amortizing oracle lookup costs.

Follow-ups

(F1) Distinct multiset enumeration: Instead of iterating all 2^n masks, enumerate multisets directly using product of (cnt[c] + 1) for each character c.

(F2) Return a counterexample: Output the first invalid multiset.

(F3) Confirm length: Clarify whether the dictionary word must have exactly the same length as the subsequence (usually yes for anagrams).

Trade-offs

38. Context Queries Around Anchor

Problem Statement

Given a word sequence, support context queries: return up to k words before and up to k words after position i.

Three variants: 1. Static list query. 2. Streaming append and query. 3. Streaming with distinct words (scan left/right until k distinct words found).

Input: Word list (static or streamed), indices, k.

Output: (prev, next) word lists.

Constraints: 1 ≤ k ≤ N; N ≤ 100000 for streaming.

Example:

words = ["a", "b", "c", "b", "d"], i = 2, k = 2
prev = ["b", "a"], next = ["b", "d"]

Solution

Static case: Slice the array. Streaming case: Append to a dynamic array. Distinct case: Scan outward with a local set to track seen words.

#include <vector>
#include <string>
#include <set>
using namespace std;

class WordContextStream {
public:
    vector<string> words;

    void append(const string& w) {
        words.push_back(w);
    }

    pair<vector<string>, vector<string>> query(int i, int k) {
        int n = (int)words.size();
        vector<string> prev, next;

        int start = max(0, i - k);
        for (int j = i - 1; j >= start; --j) {
            prev.push_back(words[j]);
        }

        int end = min(n - 1, i + k);
        for (int j = i + 1; j <= end; ++j) {
            next.push_back(words[j]);
        }

        return make_pair(prev, next);
    }

    pair<vector<string>, vector<string>> queryDistinct(int i, int k) {
        int n = (int)words.size();
        vector<string> prev, next;
        set<string> seenPrev, seenNext;

        int j = i - 1;
        while (j >= 0 && (int)prev.size() < k) {
            if (seenPrev.find(words[j]) == seenPrev.end()) {
                seenPrev.insert(words[j]);
                prev.push_back(words[j]);
            }
            j--;
        }

        j = i + 1;
        while (j < n && (int)next.size() < k) {
            if (seenNext.find(words[j]) == seenNext.end()) {
                seenNext.insert(words[j]);
                next.push_back(words[j]);
            }
            j++;
        }

        return make_pair(prev, next);
    }
};

• Time (append): O(1) amortized
• Time (query): O(k)
• Time (queryDistinct): O(answer_scan)
• Space: O(N)

Discussion

The static case is trivial slicing. Streaming uses a dynamic array for O(1) index access. For distinct queries, naive scanning is O(N) in the worst case but acceptable for typical workloads. Advanced techniques (suffix automaton, prev_different pointers) can optimize but are usually overkill.

Follow-ups

(F1) Optimize distinct scan: Precompute prevDifferent[i] and nextDifferent[i] for faster chains.

(F2) Range queries: Support queries over subranges [i1, i2].

(F3) Weighted context: Weight words by frequency or relevance.

Trade-offs

39. Next-Word Predictor

Problem Statement

Train on word sequences. Build transition counts from adjacent pairs. Support: 1. predictMostLikely(prev) — return the most frequent next word; break ties lexicographically; return "" if none. 2. predictWeighted(prev, r) with r ∈ [0, 1) — weighted random pick by cumulative probability.

Input: List of sentences (word sequences), query word, random value r.

Output: Next word prediction.

Constraints: Up to 100000 sentences; up to 100000 unique (prev, next) pairs.

Example:

sentences = [["hello", "world"], ["hello", "there"]]
predictMostLikely("hello") → "world" (tied 1-1, pick lex smallest "there")
predictWeighted("hello", 0.4) → "there" (covers [0.5, 1.0))

Solution

Precompute counts for each (prev, next) pair. Store words, counts, and cumulative prefix sums. For most-likely, find the max count and return the lex smallest. For weighted, use binary search on the cumulative array.

#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

class WordPredictor {
private:
    map<string, vector<string>> words;
    map<string, vector<int>> counts;
    map<string, vector<int>> prefixSums;
    map<string, string> bestWord;
    map<string, int> bestCount;

public:
    void train(vector<vector<string>>& sentences) {
        map<string, map<string, int>> trans;

        for (size_t s = 0; s < sentences.size(); ++s) {
            for (size_t i = 0; i + 1 < sentences[s].size(); ++i) {
                trans[sentences[s][i]][sentences[s][i + 1]]++;
            }
        }

        for (map<string, map<string, int>>::iterator it = trans.begin(); it != trans.end(); ++it) {
            string prev = it->first;
            map<string, int>& nextCounts = it->second;

            vector<pair<string, int>> items(nextCounts.begin(), nextCounts.end());
            sort(items.begin(), items.end());

            words[prev].clear();
            counts[prev].clear();
            prefixSums[prev].clear();

            int totalCount = 0;
            int maxCount = 0;
            string maxWord = "";

            for (size_t i = 0; i < items.size(); ++i) {
                words[prev].push_back(items[i].first);
                counts[prev].push_back(items[i].second);
                totalCount += items[i].second;

                if (items[i].second > maxCount) {
                    maxCount = items[i].second;
                    maxWord = items[i].first;
                }
            }

            int acc = 0;
            for (size_t i = 0; i < counts[prev].size(); ++i) {
                acc += counts[prev][i];
                prefixSums[prev].push_back(acc);
            }

            bestWord[prev] = maxWord;
            bestCount[prev] = maxCount;
        }
    }

    string predictMostLikely(const string& prev) {
        if (bestWord.find(prev) == bestWord.end()) return "";
        return bestWord[prev];
    }

    string predictWeighted(const string& prev, double r) {
        if (words.find(prev) == words.end()) return "";

        int total = prefixSums[prev].back();
        int target = (int)(r * total);

        vector<int>& prefix = prefixSums[prev];
        int idx = lower_bound(prefix.begin(), prefix.end(), target) - prefix.begin();
        if (idx < (int)prefix.size() && prefix[idx] > target) {
            return words[prev][idx];
        }
        if (idx >= (int)prefix.size()) idx = (int)prefix.size() - 1;
        return words[prev][idx];
    }
};

• Time (train): O(tokens + pairs·log(pairs))
• Time (predictMostLikely): O(1)
• Time (predictWeighted): O(log k) where k = distinct next words
• Space: O(pairs)

Discussion

Lexicographic tiebreak for most-likely: sort items by word first, then pick the max count (first occurrence wins among ties). Weighted sampling via cumulative prefix and binary search is a standard pattern (LeetCode 528).

Follow-ups

(F1) Online training: Invalidates cached best on each new pair; maintain with lazy recomputation.

(F2) Higher-order n-grams: Key on tuples of (prev_{i-1}, prev_{i-2}, …).

(F3) Smoothing: Add Laplace smoothing for unseen prev words.

Trade-offs

40. Winning Probability on 1D Grid

Problem Statement

Start at position 0 on a 1D line. Roll a uniform die (values 1 to K) and move right by the result. Win if you enter [mn, mx]. Lose if you exceed mx before entering. Return the winning probability.

Input: K (die max), mn (target start), mx (target end).

Output: Winning probability as a floating-point number.

Constraints: 1 ≤ K, mn, mx ≤ 100000; mn ≤ mx.

Example:

K=6, mn=3, mx=6
Start at 0. Possible first moves: 1,2,3,4,5,6
Win immediately if roll 3,4,5,6 (probability 4/6)
If roll 1 or 2, continue from that position

Solution

Use dynamic programming with a sliding-window optimization. Let p[x] = winning probability from position x.

• Base: p[x] = 1 if x ∈ [mn, mx]; 0 if x > mx.
• Transition: p[x] = (1/K) · Σ p[x + d] for d = 1..K.

Compute p[x] from mn-1 down to 0 using a sliding-window sum for O(1) per state.

#include <vector>
#include <algorithm>
using namespace std;

double winningProbability(int K, int mn, int mx) {
    if (mn == 0) return 1.0;

    vector<double> p(mn, 0.0);

    double windowSum = 0.0;
    for (int d = 0; d < K; ++d) {
        int idx = mn + d;
        if (idx <= mx) {
            windowSum += 1.0;
        }
    }

    for (int x = mn - 1; x >= 0; --x) {
        double p_x = windowSum / K;
        p[x] = p_x;

        int removeIdx = x + K;
        double removed = 0.0;

        if (removeIdx <= mx) {
            removed = 1.0;
        } else if (removeIdx > mx) {
            removed = 0.0;
        } else {
            removed = p[removeIdx];
        }

        windowSum = windowSum - removed + p_x;
    }

    return p[0];
}

• Time: O(mx)
• Space: O(mn)

Discussion

The naive formula p[x] = (1/K) · Σ p[x+d] is O(mn·K). The sliding-window optimization reduces it to O(1) per state by maintaining the sum of the next K values. The window shifts as x decreases.

Follow-ups

(F1) Unbounded die: If the die can roll arbitrary large values, analyze the asymptotic behavior.

(F2) Multiple targets: Compute probabilities for all targets simultaneously.

(F3) Biased die: Generalize to non-uniform probabilities (maintain weighted sums).

Trade-offs

41. Count Pairs of Aliens on Different Planets

Problem Statement

N aliens are distributed across planets via friendships. A friends list gives pairs of aliens living on the same planet. Determine the number of unordered pairs of aliens who live on different planets.

Input: - N: number of aliens - friends: list of (a, b) pairs indicating a and b are on the same planet

Output: - Single integer: count of cross-planet pairs

Constraints: - 1 ≤ N ≤ 10^5 - 0 ≤ |friends| ≤ 10^5

Example:

N = 4, friends = [(0, 1), (2, 3)]
Planets: {0, 1}, {2, 3}
Answer: 0*1 + 0*1 + 1*1 + 1*1 = 2*2 = 4

Solution

Connected components in the friendship graph represent planets. Let component sizes be s₁, s₂, …, sₖ. The count of cross-planet pairs equals Σᵢ<ⱼ sᵢ · sⱼ, computed incrementally as prev_sum · sᵢ for each component, then prev_sum += sᵢ.

#include <bits/stdc++.h>
using namespace std;

class DSU {
public:
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) {
            if (sz[a] < sz[b]) swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        dsu.unite(a, b);
    }
    map<int, int> sizes;
    for (int i = 0; i < n; i++) {
        sizes[dsu.find(i)]++;
    }
    long long ans = 0, prev = 0;
    for (auto& p : sizes) {
        ans += prev * p.second;
        prev += p.second;
    }
    cout << ans << "\n";
    return 0;
}

• Time: O((N + |friends|) α(N))
• Space: O(N)

Discussion

The key insight is inverting the counting: instead of summing pairs within each component, sum products across components. The running-sum technique avoids explicit C(sᵢ, 2) calculation. Each component contributes prev_sum · sᵢ to the total, where prev_sum is the sum of all previous component sizes.

Follow-ups

(F1) Exactly k aliens from k distinct planets: Use combinatorial selection with inclusion-exclusion over component sizes. (F2) Weighted by alien type: Group each component by type and apply the same pairing logic per type. (F3) Dynamic queries: Maintain DSU with running sum updated on each edge insertion.

Trade-offs

42. Validate Parent Array Represents a Tree

Problem Statement

An array parent of length N encodes a rooted tree: parent[i] is the parent of node i (or -1/i for the root). Validate that this forms a valid tree: - Exactly one root - No cycles - All nodes connected

Input: - parent: array of parent indices

Output: - Boolean: true if valid tree, false otherwise

Constraints: - 0 ≤ N ≤ 10^5 - -1 ≤ parent[i] < N

Example:

parent = [1, 2, -1]
Nodes 0→1→2, 2 is root. Valid tree. Output: true

Solution

Use union-find to detect cycles. Count roots (nodes where parent[i] == i or parent[i] == -1). For each non-root node, union it with its parent; if they’re already in the same component, a cycle exists. At the end, verify exactly one root and all nodes are connected.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> parent(n);
    for (int i = 0; i < n; i++) cin >> parent[i];

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    };

    int roots = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] == i || parent[i] == -1) {
            roots++;
            continue;
        }
        if (parent[i] < 0 || parent[i] >= n) {
            cout << "false\n";
            return 0;
        }
        int pi = find(i), pp = find(parent[i]);
        if (pi == pp) {
            cout << "false\n";
            return 0;
        }
        p[pi] = pp;
    }

    set<int> components;
    for (int i = 0; i < n; i++) {
        components.insert(find(i));
    }

    cout << (roots == 1 && components.size() == 1 ? "true" : "false") << "\n";
    return 0;
}

• Time: O(N α(N))
• Space: O(N)

Discussion

Union-find cleanly handles both connectivity and cycle detection. The core checks are: (1) exactly one explicit root, (2) no component collapses during union (cycle detection), and (3) after all unions, one connected component remains. Path compression ensures near-linear performance.

Follow-ups

(F1) Root encoding ambiguity: Support both parent[root] == root and parent[root] == -1; clarify before coding. (F2) Return the root: Track the single node with parent == self or -1. (F3) Weighted tree: Parent array remains structural; weights are separate.

Trade-offs

43. Ad Selector — Top-K Ads by Score

Problem Statement

Design a class to manage ads with dynamic insertion, deletion, and top-k retrieval.

Operations: - add(id, score): Insert or update ad score - remove(id): Delete ad; return false if absent - get_ads(k): Return top k ads by score (descending), non-destructive

Target Complexity: - add, remove: O(log N) - get_ads: O(k log N)

Constraints: - 1 ≤ N ≤ 10^5 - 0 ≤ k ≤ N

Solution

Use a multimap keyed by (score, id) in descending order, with a hashmap from id to multimap iterator for O(log N) updates. Iteration from the start yields top-k in O(k) time.

#include <bits/stdc++.h>
using namespace std;

class AdSelector {
    multimap<int, string, greater<int> > byScore;
    unordered_map<string, multimap<int,string,greater<int> >::iterator> idToIt;
public:
    void add(const string& id, int score) {
        auto it = idToIt.find(id);
        if (it != idToIt.end()) {
            byScore.erase(it->second);
            idToIt.erase(it);
        }
        auto newIt = byScore.insert(make_pair(score, id));
        idToIt[id] = newIt;
    }
    bool remove(const string& id) {
        auto it = idToIt.find(id);
        if (it == idToIt.end()) return false;
        byScore.erase(it->second);
        idToIt.erase(it);
        return true;
    }
    vector<string> get_ads(int k) {
        vector<string> result;
        auto it = byScore.begin();
        for (int i = 0; i < k && it != byScore.end(); i++, it++) {
            result.push_back(it->second);
        }
        return result;
    }
};