🧠 DSA Thoughts

1 · 🧱 Grid Basics — Blocked Start/End First, Directions Clockwise

🚧 Blocked check first: the problem mentions a wall, thorn, obstacle or -1? Check the start and the end before any BFS/DFS. Blocked → return the answer right away. Don't go down the search.

if (isWall(start) || isWall(end)) return -1   // before BFS/DFS

🧭 Directions: always Top → Right → Down → Left (clockwise):

const dirs = [
  [-1,  0],   // top
  [ 0,  1],   // right
  [ 1,  0],   // down
  [ 0, -1],   // left
]

2 · 🔢 Nodes Labeled 1..n → -1 on Edges AND on Source/Target

Arrays are 0..n-1, so every label from the input gets -1, in two places:

1. 🔗 Building the graph: graph[u - 1].push([v - 1, w])
2. 🎯 Source / target given as 1..n: dist[k - 1] = 0, pq.enqueue([0, k - 1]). This is the one people forget, because it sits outside the edge loop.

3 · 🎯 Mark the Start Before the Loop — BFS visited, Dijkstra dist

• 🟢 BFS: put the start in the queue AND mark it in visited (array or set).
• 🔵 Dijkstra: dist = Infinity everywhere, then dist[src] = 0 and push the start.

// BFS
queue = [start]; visited.add(start)   // mark when you push, not when you pop
// Dijkstra
dist.fill(Infinity); dist[src] = 0; pq.enqueue([0, src])

4 · 🗺️ When Do I Need visited vs parent?

💎 DAG diamond: 0→1→3 and 0→2→3, so 3 is reached twice. Chain 20 diamonds → 4,194,301 DFS calls without visited, 61 with it (checked in Node).

5 · 🔦 BFS or Backtracking? — Fewest Steps vs Choices That Change the Next Move

6 · 🪣 BFS Jumps by a Shared Key → Bucket Once, Delete After Use

🎯 When: in a BFS, one node can jump to MANY nodes that share a key (same value, same prime factor). Re-scanning the whole array from each such node is O(n²).

📐 LC 3629 (Prime Teleportation): jump i±1, or, when nums[i] is a prime p, to any j with nums[j] % p === 0.

✅ Fix: build the buckets once, and delete a bucket the first time you use it:

// prime -> [indices whose value has this prime factor], built once before BFS
const nextIdxs = primeToIdx.get(currVal)
for (const idx of nextIdxs ?? []) { /* visit */ }
primeToIdx.delete(currVal)   // every index in it is already queued

📊 Why O(n log maxVal): each bucket is read once in the whole BFS, so total work = sum of bucket sizes. A number with k distinct primes is ≥ 2^k, so k ≤ log₂(maxVal) buckets per number.

7 · 🗂️ Many Queries, Same Graph → Precompute Once

📐 LC 1462 Course Schedule IV: many "is u a prerequisite of v?" queries on one graph.

• 1️⃣ BFS per query → Q × (V+E)
• 2️⃣ Precompute: BFS from every node once and fill reach[u][v] (a reachability table, not the adjacency matrix). After that, each query is O(1).

8 · 🚦 Which Shortest-Path Tool?

Why BFS breaks with weights: BFS trusts "visited first = shortest". 📐 start→A costs 10, start→B→A costs 1+1 = 2. BFS reaches A first by the direct edge, locks in 10, and the cheaper path via B is blocked.

9 · 🎯 Dijkstra — TC & SC, and Skipping Stale Entries

1️⃣ ⏱️ TC = O(E log E) · 💾 SC = O(V + E)

TC, counted from edges:

• 🔁 A node can enter the heap many times, once per cheaper path found. The extra copies are popped and skipped as stale (2️⃣ below).
• ➡️ But each node is processed once (at its cheapest cost), so each edge is processed once → at most E pushes.
• 🪜 Every push/pop on a heap of up to E entries costs log E → E × log E.
• Plus O(V) to set up dist → strictly O(V + E log E). Usually written O(E log E) = O(E log V) (since E ≤ V² makes log E ≤ 2 log V). The V only matters with many isolated nodes.

SC: adjacency list O(V + E) + dist[] O(V) + heap up to E entries → O(V + E).

2️⃣ ⏭️ Skip stale entries

A node can sit in the heap several times, once per cheaper path found. Only the entry matching dist[node] is current. Skip the rest:

if (currTime > dist[node]) continue   // stale: a cheaper path already won

10 · ⏳ 2577 vs 3341/3342 — Can You Wait, or Must You Move?

🎯 All THREE use Dijkstra. The ONE difference: can you WAIT in place?

if (neiTime <= currTime+1) nextTime = currTime+1
else if ((neiTime-currTime)%2===0) nextTime = neiTime+1
else nextTime = neiTime

⚠️ Special case: (0,0) has NO parent to bounce with. If BOTH its neighbors need >1 to enter, you're stuck immediately:

if (grid[0][1]>1 && grid[1][0]>1) return -1

✅ 3341/3342 (Reach Last Room I/II): FREE waiting. Just sit and wait, then move:

nextTime = max(currTime, moveTime[nr][nc]) + moveCost

11 · 🎯 Binary Search + BFS vs Binary Search + Dijkstra

🎯 "Can I reach X using only edges ≤ mid?" → BFS. "What's the CHEAPEST path?" → Dijkstra.

🔑 Binary search already picked the max allowed weight and filtered the graph, so the check only needs YES/NO reachability.

📐 LC 3419 (minimize the max edge weight so every node can reach node 0): check(mid) = keep edges ≤ mid, reverse them, BFS from 0, did it reach every node? No distances needed.

12 · 🟠 Bellman-Ford — Negative Weights or At Most K Stops

🚨 Negative weights → Bellman-Ford. Dijkstra treats a popped node as final, and a negative edge found later can break that. Relax every edge for V−1 rounds, O(V·E). If an extra round still improves something → a negative cycle reachable from the source.

🎯 At most K stops (LC 787): K stops = K+1 edges = K+1 rounds.

for (let round = 0; round <= k; round++) {
  const prev = [...dist]                    // read last round only
  for (const [u, v, w] of flights)
    if (prev[u] + w < dist[v]) dist[v] = prev[u] + w
}

❓ Why prev?

Each round allows at most one more edge. Read from dist while you update it, and a value set earlier in the same round is used again, so one round walks several edges.

LC 787, k = 1
edges: 0→1 100, 1→2 100,
       2→3 200, 1→3 600

❌ no prev, round 1:
   dist[1]=100 → dist[2]=200 → dist[3]=400
   3 edges in 1 round = 2 stops

✅ prev
   round 1: dist[1]=100
   round 2: dist[2]=200, dist[3]=700

13 · 🌊 Floyd-Warshall — Diagonal 0, Edges with Math.min, via Outermost

🎯 Shortest distance between EVERY pair of nodes, O(V³).

1️⃣ 🧱 Build dist (n × n)

• ↘️ Diagonal = 0: dist[i][i] = 0 (top-left → bottom-right). The distance from a node to itself is 0.
• ♾️ Everything else = "no path yet" (Number.MAX_SAFE_INTEGER or Infinity).
• 🔗 Edges [u, v, c] → keep the cheaper: dist[u][v] = Math.min(dist[u][v], c). The same u → v can come twice with different costs. Undirected → set dist[v][u] too.
• 🔤 Nodes are letters or names? Same rules. Map each one to an index first: letter → ch.charCodeAt(0) - 97, name → a Map of name → index.

2️⃣ 🔁 Relax through every middle stop (via outermost)

📐 Your LC 2976 (Minimum Cost to Convert String I), with letters as nodes:

const dist = Array.from({length: 26}, () => Array(26).fill(Number.MAX_SAFE_INTEGER));
for (let i = 0; i < 26; i++) dist[i][i] = 0;               // diagonal

for (let i = 0; i < m; i++) {
    const u = ori[i].charCodeAt(0) - 97;                     // letter → index
    const v = ch[i].charCodeAt(0) - 97;
    dist[u][v] = Math.min(dist[u][v], cost[i]);              // keep the cheaper edge
}

for (let via = 0; via < 26; via++)                           // MUST be outermost
    for (let s = 0; s < 26; s++)
        for (let d = 0; d < 26; d++)
            if (dist[s][via] !== Number.MAX_SAFE_INTEGER && dist[via][d] !== Number.MAX_SAFE_INTEGER)
                dist[s][d] = Math.min(dist[s][d], dist[s][via] + dist[via][d]);

// answer: sum dist[src[i]][tar[i]], any MAX_SAFE_INTEGER → return -1

🛡️ Why the !== guard: MAX_SAFE_INTEGER + anything is past the safe range. With Infinity you can drop the guard, because Infinity + x stays Infinity.

Checked in Node: your code gives the LC 2976 answers 28, 12, −1 ✅. The duplicate above gives 2 with Math.min and 5 without.

14 · 🍰 Dijkstra on States — Node Alone Isn't Enough → dist[node][extra]

❓ Ask: "can I decide the next move from the node alone?"

• ✅ Yes → normal dist[node]
• ❌ No, I also need something about the path so far → put it in the state → dist[node][extra]

🍰 Layered graph: every (node, extra) pair is its own node in a bigger graph. Run plain Dijkstra on it, nothing else changes. Same for BFS: queue [node, extra], visited[node][extra].

normal: node 1 has ONE cost
states: (1, run 1) and (1, run 2) each have their OWN cost

🐛 Why dist[node] breaks (LC 3970, at most k = 2 same labels in a row):

labels: 0=a 1=a 2=b 3=a
edges:  0→1 (1) · 0→2 (5) · 2→1 (5) · 1→3 (1)

🏃 cheap:  0→1, cost 1,  run "aa" = 2 → 1→3 makes "aaa" ❌
🐢 dear:   0→2→1, cost 10, run "a" = 1 → 1→3 ✅ total 11

dist[1] = 1 already → cost 10 is thrown away → returns -1 ❌ (real: 11)

✅ Fix: one cost per (node, count):

const dist = Array.from({ length: n }, () => Array(k + 1).fill(Infinity))
dist[0][1] = 0
if (currDist > dist[node][count]) continue          // stale per (node, count)
if (neiDist < dist[nei][newCount]) {
  dist[nei][newCount] = neiDist
  pq.enqueue([neiDist, nei, newCount])
}
// answer = Math.min(...dist[n - 1])

🚨 Trigger words:

• 🛑 "at most k stops" → dist[node][stops] (LC 787, or Bellman-Ford #12)
• 🔁 "no more than k in a row" → dist[node][count] (LC 3970)
• 🧱 "can remove k obstacles" → dist[cell][removalsLeft] (LC 1293, BFS)
• 🔑 "fuel / keys collected" → dist[node][fuel], dist[node][keysMask] (LC 864, BFS)

⏱️ States = n · k → TC O(E·k log(E·k)). Same question as the param test in Recursion #1: does the future need it? Checked in Node: on 5,000 random graphs, dist[node] was wrong 7 times, dist[node][count] never.

15 · 🔗 Union-Find — First Ask "What Is a Node?" (947 vs 305)

🎯 The Union-Find engine never changes: new node → count++, real union (two different roots) → count--. What changes is what you call a node.

// 947: stone = edge (row, col)
uf.add(r); uf.add(c + 10001); uf.union(r, c + 10001)

// 305: a cell is a node
const id = r * cols + c

🪨 Why stones − components: in a group of k connected stones you can remove all but one, so each group gives k − 1.

🏝️ Why Union-Find, not BFS: land arrives one cell at a time. BFS would rescan the grid after every add. Union-Find only joins the new cell to its neighbours.

🔒 LC 305 is Premium, free copy: LintCode 434. Checked in Node: 947 examples → 5, 3, 0 · 305 example → [1, 1, 2, 3]. Union-Find also powers Kruskal (#16) and the undirected cycle check (#17).

16 · 🕸️ MST — Kruskal's = Sort Edges + Union-Find (Skip Prim's)

🎯 Connect ALL nodes (directly or through others) with the MINIMUM TOTAL edge cost. Not "shortest path between two nodes": that's Dijkstra, a different question. Dijkstra adds up distance from a source; MST doesn't care about distance from anywhere.

Problems: LC 1584 Min Cost to Connect All Points, LC 1135 Connecting Cities With Minimum Cost 🔒.

// general MST: n nodes, edges = [u, v, weight]
function minCostToConnectAllNodes(n: number, edges: number[][]): number {
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = Array(n).fill(0);

    function find(x: number): number {
        let root = x;
        while (parent[root] !== root) root = parent[root];
        while (parent[x] !== root) {
            const next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    function union(x: number, y: number): boolean {
        const px = find(x), py = find(y);
        if (px === py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[px] = py; rank[py]++; }
        return true;
    }

    edges.sort((a, b) => a[2] - b[2]); // sort by weight ascending

    let totalCost = 0, edgesUsed = 0;

    for (const [u, v, weight] of edges) {
        if (union(u, v)) {
            totalCost += weight;
            edgesUsed++;
            if (edgesUsed === n - 1) break; // tree complete
        }
    }

    return edgesUsed === n - 1 ? totalCost : -1; // -1 if graph can't be fully connected
}

🧩 The Kruskal family — why Union-Find keeps showing up

Kruskal's skips any edge that would make a cycle. "Would it make a cycle?" = "are u and v already in the same group?" → union(u, v) returns false. So every Kruskal-style question is sort, then union in order.

Checked in Node: all 6 Kruskal versions give the LC example answers (1584 → 20 · 1579 → 2, 0, −1 · 1489 → [[0,1],[2,3,4,5]] · 3600 → 2, 6, −1 · 778 → 3, 16).

17 · 🔄 Cycle Detection — All Methods, At a Glance

🔗 UNDIRECTED — 3 ways

1. DFS + parent-skip:

dfs(node, parent):
  visited[node] = true
  for nei in graph[node]:
    if nei === parent: skip
    if visited[nei]: CYCLE
    dfs(nei, node)

2. BFS + parent-skip: same idea, queue holds (node, parent) pairs instead of recursion.

3. Union-Find:

for each edge (u,v):
  if find(u) === find(v): CYCLE
  else union(u,v)

➡️ DIRECTED — 2 ways (Union-Find does NOT apply — no sense of direction)

1. DFS with 0/1/2 marking:

state: 0=unvisited, 1=exploring, 2=done
dfs(node):
  state[node] = 1
  for nei in graph[node]:
    if state[nei]===1: CYCLE (back edge to node still exploring)
    if state[nei]===0: dfs(nei)
  state[node] = 2

2. Kahn's (BFS topological sort): keep peeling nodes with indegree 0. Nodes on a cycle, and nodes that come after one, never reach 0.

queue = all nodes with indegree 0
process queue, decrementing neighbors' indegree, adding new indegree-0 nodes
if processedCount < n: CYCLE (leftovers = on a cycle or after one)

18 · 🌳 Valid Tree — Just Two Rules: Connected + No Cycle

🎯 Any tree (binary, ternary, any number of children) is valid when:

1. 🔗 Connected: one component, every node reachable
2. 🚫 No cycle

Binary vs ternary only limits children per node. It doesn't change what makes it a tree.

🛠️ How to check:

• Undirected edges (LC 261 🔒, free: LintCode 178): exactly n − 1 edges + connected (no cycle follows from that)
• Parent pointers (LC 1361): each node has ≤ 1 parent, exactly one root (0 parents), all reachable from the root

19 · ✈️ Hierholzer's — Every Edge Once, Post-Order, Reverse

🎯 Eulerian path = use every EDGE once, not every node. Push the node to the result on the way OUT (post-order), then reverse at the end.

⏱️ TC: the walk itself is O(E), because each edge is removed once (graph[node].pop()) and a node is visited once per outgoing edge. LC 332 also sorts each airport's tickets first → O(E log E) end to end.

🚨 Why post-order? (LC 332 Reconstruct Itinerary)

➡️ Add an airport to res ONLY after all its tickets are used. The first time you get stuck, you are at the final stop, so the stuck node goes in first. res builds the trip backwards → reverse at the end.

tickets: JFK→A, JFK→B, B→JFK
(smallest first: A before B)

❌ pre-order (add on arrival)
   JFK → A → B → JFK
   no ticket A→B! A written too early

✅ post-order
   res = [A, JFK, B, JFK]
   reverse → JFK → B → JFK → A

20 · ⚖️ V+E Is a Shortcut — Only Safe When Work Is O(1)

🎯 V+E really means V × (work per node) + E × (work per edge).

✅ Work per node/edge is O(1) (a comparison, a neighbour check) → just write V+E.

📐 Example — removeInvalidParentheses (n = string length): up to 2^n states, each makes up to n children (edges), and each child is an O(n) string slice.

Total = 2^n states × n children × O(n) slice = O(2^n · n²)

21 · 📊 How Many Edges? Grid, Dense, Sparse, Tree

Grid M×N:  V = MN, E ≤ 4MN  → V+E = O(MN)   (the 4 drops)
Dense:     E = O(V²)        ← max for a simple graph
Sparse:    E = O(V)
Tree:      E = V − 1        ← always sparse

🎯 Values between V and V² exist (V log V, V√V), but interviews only need the two bounds. Union-Find follows the same split: O(E · α(V)) → sparse ≈ O(V), dense ≈ O(V²).

1 · 🌲 Serialize/Deserialize Tree → think PREORDER

• Binary Tree (297): preorder + null markers
• BST (449): preorder alone suffices — BST bounds preserve structure

2 · 🔍 BST → think INORDER first

Inorder on a BST = sorted order. Use for:

• Kth smallest/largest
• Validate BST
• Predecessor/successor
• Recover BST

3 · 🌳 Tree Traversal as Undirected Graph — Parent Map

Trees only give CHILD pointers (left/right) — no way UP.

🎯 Don't build a full adjacency-list graph — just add the ONE missing piece: parent.

📐 One DFS pass, passing (node, parent), building parentMap.set(node, parent).

Used for: All Nodes Distance K in Binary Tree (863) — any problem needing "go up" in a tree.

4 · 🍎 Collect Items in a Tree — dfs Returns "Has Item?", Not Time

🎯 Don't make dfs return "time to reach here". Return does this subtree have an apple? A child says yes → you must walk that edge down and back → totalTime += 2 (LC 1443).

// dfs(node, parent) -> tell if subtree has apple or not
let currTreeHasApple = hasApple[node]
for (const nei of graph[node]) {
    if (nei === parent) continue
    if (dfs(nei, node)) { totalTime += 2; currTreeHasApple = true }
}
return currTreeHasApple

⏱️ TC O(n): each node once (parent guard), edges scanned once in total, E = n − 1. SC O(n): adjacency list + recursion stack (path-shaped tree).

5 · 🏗️ Full vs Complete vs Perfect — and Their Height

• 📏 Height = edges on the longest root → leaf path (root alone = 0).
• 🔗 Every perfect tree is also full and complete.
• ⛰️ Complete → heap: height log n, so push/pop is O(log n), and it fits in an array (children of i = 2i + 1, 2i + 2).
• 🐍 Skewed tree (a chain): height n − 1 → BST ops become O(n).

1 · ↕️ Ask the Child, Tell the Child, or Both — Where Does the Answer Travel?

• 🔙 ASK the child: "what's the best from you?" The child returns a value, and the parent adds its own part.
• ⬇️ TELL the child: "here's what I have so far." It goes in a parameter, and the last call records it in best.
• 🔁 TELL + RETURN: pass the value down, the last call returns the finished value, and the parent picks the best of the finished answers.

🖼️ Min path sum on [[1, 3], [2, 1]] (move right or down). All three give 4.

🤔 Which one? Ask: can a loser now become a winner later?

• 🔢 No (+, min, max), one number → 🔙 ask → memo → DP (LC 64)
• 🧵 Every path, or the path itself → ⬇️ tell → backtracking
• 🔄 Yes, XOR (1 ^ 2 = 3 worse, 3 ^ 2 = 1 better) → 🔁 tell + return (LC 3882)
• ➖ Yes, × with negatives → ask, but return both min AND max (LC 152)

// 🔁 LC 3882 Min XOR Path (bounds checks left out)
const y = x ^ grid[r][c];                            // ⬇️ tell: XOR so far
if (r === m - 1 && c === n - 1) return y;            // 🏁 last cell returns the finished XOR
best = Math.min(dfs(r + 1, c, y), dfs(r, c + 1, y)); // 🔙 pick among finished answers

🧪 Why XOR can't just ask: [[2,7,1],[4,5,3]]. Keeping only the smallest XOR gives 3. The real answer is 0 (2 → 4 → 5 → 3).

🧪 Param test: "does the FUTURE need this to decide?"

• ✅ Yes (row, prevCol, XOR so far x) → keep it, that's the state. x < 1024 → memo [r][c][x] fits (Math #4)
• ❌ No, it's only the past (currSum) → drop it and ask instead. With the past in the params, nothing repeats and the memo never hits.

2 · 🎯 Sentinel-Seeding: When It's Safe vs When It's Not

🎯 The REAL question: does my function have an EXPLICIT base case, or is the "seed value" secretly ACTING as the base case?

✅ Explicit base case exists (if(...) return 0; / a clean, dedicated return) → sentinel-seeding is SAFE, don't overthink it. The base case ALWAYS overrides the sentinel with a real answer.

function dfs(row, col) {
    if (invalid) return 0;          // explicit base case, resolves cleanly
    ...
    let maxGold = 0;                 // sentinel is fine, loop always gets overridden
    for (...) maxGold = Math.max(maxGold, dfs(...));
    return currGold + maxGold;       // add currGold ONCE, here
}

function dfs(row, col) {
    // no explicit base case — dead end = loop simply doesn't run
    let maxGold = currGold;          // seed = the correct dead-end answer itself
    for (...) maxGold = Math.max(maxGold, currGold + dfs(...));
    return maxGold;
}

3 · 🔀 Backtracking — used[], Reuse and Duplicates: Ask 3 Questions Before the Loop

🎯 Before writing any backtracking code, answer three questions in order. Together they decide the whole loop: where it starts, what you recurse with, and whether you need used[] or a skip.

1️⃣ Does order matter?

Test with a tiny example: is [1,2] the same answer as [2,1]?

• Different (order matters) → 🔴 Permutation → loop starts from 0 every call (any element can follow any element)
• Same (order doesn't matter) → 🟢 Subset / Combination → loop starts from start (never look back at earlier indices)

2️⃣ Can an element be reused?

// Combination: reuse is decided by what you recurse with
for(let i = start; i < n; i++) dfs(i, ...);       // reuse allowed  (Combination Sum)
for(let i = start; i < n; i++) dfs(i + 1, ...);   // no reuse       (Combination Sum II, Subsets)

// Permutation, NO reuse: used[] blocks an element already on the path (Permutations)
for(let i = 0; i < n; i++) {
    if(used[i]) continue;
    used[i] = true;
    path.push(nums[i]);
    dfs();
    path.pop();
    used[i] = false;
}

// Permutation, reuse allowed: no used[] at all (Combination Sum IV)
for(let i = 0; i < n; i++) dfs(...);

3️⃣ Does the input have duplicate values?

Sort first, then skip a repeated value at the SAME level of the tree:

nums.sort((a, b) => a - b);

// Combination / Subset (Subsets II, Combination Sum II)
if(i > start && nums[i] === nums[i - 1]) continue;

🔀 Permutations II (LC 47) — same sort, then two used[] checks:

for(let i = 0; i < n; i++) {
    if(used[i]) continue;                                             // already in my path
    if(i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;    // same value as left twin, twin not in my path
    used[i] = true; path.push(nums[i]);
    backtrack();
    path.pop(); used[i] = false;
}

🔁 Can't sort? Use a LOCAL Set instead (LC 491 Non-decreasing Subsequences — sorting would destroy the subsequence order). Create it INSIDE each call, right before the loop:

const seen = new Set();                        // fresh per call
for(let i = start; i < n; i++) {
    if(seen.has(nums[i])) continue;            // already tried this VALUE at this level
    seen.add(nums[i]);                         // never removed — no undo
    path.push(nums[i]); dfs(i + 1); path.pop();
}

4 · 🔢 Set → Bitmask — A Set of Small Integers Is ONE Integer

🎯 When the options are small integers (columns 0…n−1, digits 1…9), a Set of them fits in one integer: number x is in the set ⇔ bit x is ON. Same algorithm, cheaper operations. (#8 uses a mask to memoize; here it only speeds up plain backtracking.)

bit = 1 << x

set.has(x)      →   mask & bit
set.add(x)      →   mask |= bit
set.delete(x)   →   mask &= ~bit

♟️ N-Queens: 3 Sets → 3 integers

// Set
const cols = new Set<number>()
cols.has(col)
cols.add(col)
cols.delete(col)

// Bitmask
let cols = 0
cols & (1 << col)
cols |= 1 << col
cols &= ~(1 << col)

diag1 and diag2 work exactly the same (with d1 and d2). 🔎 Example: queens in columns 1 and 3 → bits 1010 = 10.

🔢 Sudoku: array of 9 Sets → array of 9 integers

// Set
const rows = Array.from({length: 9}, () => new Set<string>())
rows[r].has('5')

// Bitmask
const rows = new Array(9).fill(0)
const bit = 1 << Number('5')
rows[r] & bit
rows[r] |= bit
rows[r] &= ~bit

5 · ♟️ Game Search — Is There a Move After Which My Opponent Loses?

🧭 Which pattern? Ask in order:

1. Does an opponent reply after my move? → ♟️ game search
2. Do I decide each item once, in order? → 🛒 take / not-take with an index
3. Building an arrangement, one option per slot? → 🧩 for-loop backtracking

🛒 A shopping list is one person going item by item, so the state is an index. ♟️ Chess has two players alternating, so you ask ONE question: "Is there a move after which my opponent loses?"

canWin(state):
  for each move:
    if (!canWin(stateAfterMove)) return true   // opponent is stuck, I win
  return false                                 // no good move, I lose

// Score games: best = max over moves of (gain - dfs(stateAfterMove))   → #14

⚠️ Check the base case in the rules. "No moves left → lose" fits Flip Game II and Stone Game IV. In Can I Win, reaching the target wins.

🔑 State = what's left after a move. Clean (only ends or front) → i or (i, j). Messy → the whole board, or a bitmask (#4).

6 · 🌲 Unmemoized Recursion TC — 3-Question Framework

🎯 Ask these in order. Stop at the first one that fits.

Q1 — Constant branching? (same # choices every call)

→ branches^depth. (take/skip → 2ⁿ)

• 🧱 Grid, 4 directions → branch≈4, depth≈M×N → O(4^(M×N))
• ↘️ Grid, right/down only → branch=2, depth=M+N → O(2^(M+N))

Loose bounds — actual cost depends on visited-tracking and work per call.

Q2 — Variable branching, but is there a FIXED set of positions each getting an independent yes/no?

→ 2^(that count).

Stone Game II: n-1 gaps → cut or not → 2^(n-1)
LC 131 Palindrome Partitioning: n-1 gaps → cut or not → 2^(n-1)

Q3 — Branching is a SPLIT POINT choice (pick k, recurse both sides)?

→ Catalan-shaped: dfs(i,j) = Σ dfs(i,k) ⊗ dfs(k,j)

function dfs(i: number, j: number): number {
    if (i >= j) return 1;
    let total = 0;
    for (let k = i; k < j; k++) {
        total += dfs(i, k) * dfs(k + 1, j);   // k = split point
    }
    return total;
}

k = root (96 Unique BST), last-op (241), last-burst (312 Burst Balloons), matrix-split (Matrix Chain Mult — the textbook Catalan recurrence itself).

None of the above fits?

→ Just say "exponential, no clean polynomial form" — honest, accepted answer.

LC 301 Remove Invalid Parentheses — removable set shifts as string changes
LC 3629 prime teleport (brute force) — branch count varies per index
LC 291 Word Pattern II, LC 139 Word Break (brute) — branch = segment length, a range not a yes/no

7 · 🍃 Recursion Tree — bᵈ Counts LEAVES, Not Every Node

🎯 2ⁿ (take/skip) and nᵈ (a for loop inside recursion) are the number of leaves. The tree has more nodes than that, but not a different big-O.

branching b ≥ 2, depth d
leaves = b^d
nodes  = 1 + b + … + b^d = (b^(d+1) − 1) / (b − 1)  ≤ 2·b^d

take/skip:    leaves 2^n,  nodes 2^(n+1) − 1   → still O(2^n)
permutations: leaves n!,   nodes ≈ e·n!         → still O(n!)

📐 Why: the last level is bigger than all the levels above it put together, so it decides the big-O.

⚖️ What actually changes the answer is the work per node:

• ⚡ O(1) at every node → O(bᵈ)
• 🍃 Real work only at the leaves (copy a path of length n) → O(n · bᵈ)
• 🌲 O(n) at every node (slice, copy, join) → also O(n · bᵈ)

8 · 🧠 Recursion / DP — Designing the STATE: Read the Question Twice

🎯 Read the question TWICE before any recursion or DP:

• 1️⃣ Read 1, "what do they want?" (max, min, count, true/false) → what dfs RETURNS.
• 2️⃣ Read 2, "after each choice, what changes that my NEXT choices depend on?" → the STATE (the dfs params).

🧪 Friend test: pause the recursion and hand it to a friend. The MINIMUM they need to finish the job is your state.

🗺️ State shapes — almost every problem is one of these

✂️ 3 rules to get the state right

• ➕ Add a variable only if the future depends on it (Stock Cooldown needs holding).
• 🧮 Drop what you can compute (Cherry Pickup: c2 = r1 + c1 − r2).
• 🗑️ Drop what's already decided. The path so far is NOT state, unless it changes your next choices (like prev in LIS).

⚖️ Small state vs big state

• 🔢 Small (a few numbers) → the same state repeats → memoize → DP
• 📦 Big (an array or a path) → too big to memoize → mutate + undo → backtracking (Distribute Cookies: childSums[])
• 🗜️ Squeeze big → small: Cookies has n ≤ 8, so "which cookies are used" fits in a bitmask → dp[child][mask].

📏 Constraints hint the shape: n ≤ 20 → mask · n ≤ 500 → (l, r) · n ≤ 10⁵ → 1D.

9 · 🧭 Recursion → DP: Direction and Starting Index Come FROM the Recurrence

🎯 Workflow: write the recursion first, find its recurrence, then read direction + start straight off it — don't guess either one.

Direction — which way does the recurrence point?

dp[i] depends on dp[i+1], dp[i+2]... (LARGER index) → loop i: n-1 DOWN TO 0
dp[i] depends on dp[i-1], dp[i-2]... (SMALLER index) → loop i: 0 UP TO n

Starting index — ask ONE question: is this index's value already hardcoded, or does the recurrence still need to compute it?

Already hardcoded outside the loop (a true base case, e.g. dp[n] = 0)
  → loop EXCLUDES it, starts one step further in

Not hardcoded — computed BY the recurrence using a virtual sentinel
before/after the array (e.g. treating dp[-1] as 0)
  → loop INCLUDES it, starts right there

📐 Example — hardcoded base (excluded from loop):

dp[n] = 0;                          // base case, set once, outside
for (i = n - 1; i >= 0; i--) { ... }  // excludes n

📐 Example — computed via sentinel (included in loop):

// dp[i] built from dp[i-1], "nothing before index 0" = sentinel 0
for (i = 0; i <= n; i++) {
    dp[i] = (i === 0 ? 0 : dp[i - 1]) + something;
}

10 · 🎯 Skip/Take vs "Committed Rule" DP — When Skip/Take Breaks

🎯 Skip/Take works when "take or skip" depends on ONE thing: comparing to the LAST picked element.

✅ LIS: "is nums[i] > nums[prev]?" — one comparison, one reference point. Skip/Take works fine.

📐 1027 Longest Arithmetic Subsequence: "does nums[i] continue the SAME DIFFERENCE this chain already has?" — but a chain only HAS a difference once it's got 2+ elements. Skip/Take (state = just prev) can't express this.

📌 Problems in this "committed rule" family:

• 1027 Longest Arithmetic Subsequence — rule = the common difference
• 873 Length of Longest Fibonacci Subsequence — rule = the last TWO numbers, state = (j, i)

Not in this family: 673 Number of LIS and 368 Largest Divisible Subset only compare with the last element, so they are plain LIS shape (#11).

🟢 LIS pseudocode (skip/take works — state = just prev):

dfs(i, prevIdx):
  if i === n: return 0
  skip = dfs(i+1, prevIdx)
  take = 0
  if prevIdx === -1 or nums[i] > nums[prevIdx]:
    take = 1 + dfs(i+1, i)
  return max(skip, take)

🔴 1027 Longest Arithmetic Subsequence — recursive framing (state = committed rule, "ending at i"):

// dfs(i, diff) -> longest arithmetic subsequence ENDING AT index i, using common difference diff
memo = map, keyed by (i, diff)

dfs(i, diff):
  if memo has (i, diff): return memo[(i, diff)]
  best = 1   // just this element alone, base length
  for j in 0..i:
    if nums[i] - nums[j] === diff:
      best = max(best, 1 + dfs(j, diff))
  memo[(i, diff)] = best
  return best

answer = max over all i, all diff = nums[i]-nums[j] for j<i, of dfs(i, diff)

🔴 1027 as tabulation

function longestArithSeqLength(nums: number[]): number {
    const n = nums.length;

    // diff range -500 to 500
    const OFFSET = 500;

    const dp = Array.from({length: n}, () => Array(1001).fill(1));

    let ans = 1;

    for(let i = 0; i < n; i++) {
        for(let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            const key = diff + OFFSET;

            dp[i][key] = Math.max(dp[i][key], 1 + dp[j][key]);
            ans = Math.max(ans, dp[i][key]);
        }
    }

    return ans;
}

📐 Why dp[j][key] (same key): nums[i] - nums[j] = diff extends the chain ending at j with that SAME diff, so read dp[j] at the same key. It is the tabulated dfs(i, diff) above.

11 · 🔗 LIS-Family: Natural Recursion ≠ Standard DP (Different States, Not a Compression)

🎯 For LIS-shaped problems, the recursion you'd naturally write and the DP everyone actually uses are TWO DIFFERENT state definitions — the DP is NOT a rolling-array compression of the recursion's memo table.

dfs(i, prevIdx):
  skip = dfs(i+1, prevIdx)
  take = 0
  if condition(nums[i], nums[prevIdx]):
    take = 1 + dfs(i+1, i)
  return max(skip, take)

→ O(2ⁿ) raw. Memoized: state = (i, prevIdx) → O(n²) states × O(1) work = O(n²) time, O(n²) space.

for i in 0..n:
  for j in 0..i:
    if condition(nums[i], nums[j]) and dp[j]+1 > dp[i]:
      dp[i] = dp[j] + 1

→ Also O(n²), but with O(n) space — a smaller, DIFFERENT state (dp[i] alone, no prevIdx dimension).

Problems in this family: LC 300 Longest Increasing Subsequence, LC 368 Largest Divisible Subset, LC 673 Number of LIS. LC 1027 also ends at i, but needs the diff in its state (#3).

🔗 LC 368 Largest Divisible Subset — LIS with %

Sort first. Then nums[i] % nums[j] === 0 for j < i is enough, because divisibility carries along the sorted order. length[i] = longest chain ending at i, and prevIdx[] lets you walk back to rebuild the subset itself.

function largestDivisibleSubset(nums: number[]): number[] {
    const n = nums.length;
    nums.sort((a, b) => a - b);

    const length = Array(n).fill(1);
    const prevIdx = Array(n).fill(-1);

    let maxLen = 1;
    let lastChosenIdx = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] !== 0) continue;

            if (length[j] + 1 > length[i]) {
                length[i] = length[j] + 1;
                prevIdx[i] = j;
            }

            if (length[i] > maxLen) {
                maxLen = length[i];
                lastChosenIdx = i;
            }
        }
    }

    const res: number[] = [];
    while (lastChosenIdx !== -1) {
        res.push(nums[lastChosenIdx]);
        lastChosenIdx = prevIdx[lastChosenIdx];
    }

    return res;
}

12 · ✂️ Palindrome Partitioning I vs II — Min Cuts = Min Pieces − 1

🎯 Don't treat "min cuts" as a new problem. It's the SAME dfs shape as counting/listing palindrome partitions — just optimize Math.min instead of collecting paths, then subtract 1 at the very end.

"aab" → pieces: ["aa","b"] → 2 pieces → 1 cut

Same skeleton for both LC 131 (list all) and LC 132 (min cuts):

function dfs(start: number): number {
    if (start === n) return 0;              // 0 pieces needed for empty suffix
    let minPieces = Infinity;
    for (let end = start + 1; end <= n; end++) {
        if (isPalin[start][end - 1]) {
            minPieces = Math.min(minPieces, 1 + dfs(end));
        }
    }
    return minPieces;
}

return dfs(0) - 1;   // pieces → cuts

13 · 🗡️ Dungeon Game — Need Here = Need Ahead − This Cell (at least 1)

🎯 dfs(r, c) = the minimum HP needed walking INTO this cell. Leap of faith: trust dfs to give the need for the rest of the trip.

// past the destination → 1 (just survive). Off the grid → Infinity
const neededAhead = Math.min(dfs(r + 1, c), dfs(r, c + 1))
return Math.max(1, neededAhead - dungeon[r][c])

➖ Why subtract: damage -2 → need goes UP by 2. Heal +8 → need goes DOWN by 8. One formula covers both.

🛡️ Why max(1, …): HP can never be 0 or below, even if a big heal "covers" everything ahead.

14 · 🎲 Stone Game Family — Each Variant Has Its OWN Shape, Don't Force-Fit

🅰️ Stone Game I — front/back pick, NO for-loop, Math.min-the-opponent

Every move removes exactly ONE pile from either END (i or j) → state stays a clean interval [i,j]. Two explicit choices only — no loop needed. Opponent (next player) wants to MINIMIZE what's left for you:

function dfs(i: number, j: number): number {
    // base case
    if(i > j) return 0;

    const pickStart = piles[i] + Math.min(dfs(i + 2, j), dfs(i + 1, j - 1));
    const pickEnd = piles[j] + Math.min(dfs(i, j - 2), dfs(i + 1, j - 1));

    return Math.max(pickStart, pickEnd);
}

🅱️ Stone Game II — variable move size, for-loop + suffix sum

Move size X isn't fixed (1..2M) → single advancing pointer i, no "other end." For-loop tries every X, subtracts the opponent's best from here, takes the max:

function dfs(idx: number, m: number): number {
    // base case
    if(idx >= n) return 0;
    if(idx + 2 * m >= n) return suffix[idx]; // must be suffix[idx], NOT suffix[0] — remaining sum, not total sum

    let best = Number.MIN_SAFE_INTEGER;
    for(let x = 1; x <= 2 * m; x++) {
        const taken = suffix[idx] - suffix[idx + x];
        const oppoTake = dfs(idx + x, Math.max(m, x));
        best = Math.max(best, taken - oppoTake);
    }

    return best;
}

🅲 Stone Game VII — front/back pick like SG1, but needs PREFIX SUM for scoring

Like SG1, picks from either end — but the SCORE for a move isn't piles[i]/piles[j] directly, it's the SUM of whatever stones remain after removing that pile. Needs a prefix-sum array for O(1) range-sum lookup. Shape follows SG1 (2 explicit choices, no loop) since it's still a fixed-one-pile-per-move front/back game:

function dfs(i: number, j: number): number {
    // base case
    if(i >= j) return 0;

    const pickFront = (prefix[j + 1] - prefix[i + 1]) - dfs(i + 1, j);
    const pickBack = (prefix[j] - prefix[i]) - dfs(i, j - 1);

    return Math.max(pickFront, pickBack);
}

1 · 🎯 Binary Search — One Pattern: Inclusive Range + ans

1. 📦 low, high = the real range, inclusive. Indices → 0 … n − 1. Values → lowest … highest. Nothing extra.
2. 🔁 while (low <= high), mid = Math.floor((low + high) / 2).
3. ✅ Condition true → it could be the answer → ans = mid. Search left → high = mid − 1. Search right → low = mid + 1.
4. ❌ Else → move the other way.

let low = 0, high = n - 1, ans = -1
while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (condition(mid)) { ans = mid; high = mid - 1 }   // search LEFT
    else low = mid + 1
}
return ans

🧪 Examples (only the start and the if change):

// 🔍 Exact — LC 704: [-1,0,3,5,9,12], 9 → 4
low = 0, high = n - 1
if (arr[mid] === target) return mid
else if (arr[mid] < target) low = mid + 1
else high = mid - 1

// ⬅️ First that works — LC 35: [1,3,5,6], 2 → 1
low = 0, high = n - 1, ans = n
if (arr[mid] >= target) { ans = mid; high = mid - 1 }
else low = mid + 1

// ➡️ Last that works — LC 69 Sqrt: 8 → 2 (values, not indices)
low = 0, high = x, ans = 0
if (mid * mid <= x) { ans = mid; low = mid + 1 }
else high = mid - 1

Checked in Node: LC 704 → 4, −1 · LC 35 → 2, 1, 4 · LC 69 → 2, 2, 0, 1, 46340 · first/last match brute force on 20,000 random arrays.

1 · 🗺️ Prefix / Suffix — Range Sum in O(1), the +1 Goes on j

index:      0    1    2    3    4    5
piles:    [ 2 ][ 7 ][ 9 ][ 4 ][ 4 ]

suffix:   [26 ][24 ][17 ][ 8 ][ 4 ][ 0 ]
                                    ↑ sentinel (nothing after index 4)

prefix:   [ 0 ][ 2 ][ 9 ][18 ][22 ][26 ]
            ↑ sentinel (nothing before index 0)

🎯 Suffix sentinel sits at the END. Prefix sentinel sits at the START. Both mean the same thing: "empty range → 0."

suffix[i] INCLUDES piles[i]. prefix[i] EXCLUDES it (sum of everything before i).

➕ Sum of i..j (inclusive): the +1 always goes on j.

prefix[j + 1] - prefix[i]   // 1..3 → 22 - 2 = 20 (7 + 9 + 4)
suffix[i] - suffix[j + 1]   // 1..3 → 24 - 4 = 20

🔁 Same trick, other interview shapes:

• 🎯 Subarray sum = k (LC 560): count seen[prefix - k]. Start with seen = {0: 1}, that's the sentinel (empty prefix).
• ⊕ Range XOR: px[j + 1] ^ px[i], same shape as sum.
• 🔲 2D range sum (LC 304): P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1] (add back the corner you subtracted twice).
• 📈 Range ADD (difference array): diff[i] += v, diff[j + 1] -= v, then prefix-sum it. The +1 lands on j again.
• ✖️ Product except self (LC 238): left[i] * right[i], both EXCLUDE i.

2 · 🪟 Subarray Sum: Sliding Window or Prefix Sum + Map?

🔑 Why: a window needs one direction. Adding an element must always push the sum the same way, so you know which pointer to move. Mixed signs break that.

💥 [5, -3, 1], target 3: the window drops 5 as "too big" before -3 arrives, and never finds the whole array.

3 · 🧮 Count Subarrays: Turn Everything Into atMost()

atMost(k)   // shrink while count > k, then res += right - left + 1
atLeast(k) = total - atMost(k - 1)   // total = n * (n + 1) / 2
exactly(k) = atMost(k) - atMost(k - 1)

🔑 Why: every subarray is ≥ k or ≤ k − 1, never both, so all = atLeast(k) + atMost(k − 1).

🎓 5 students: 3 scored ≥ 60, 2 scored ≤ 59 → atLeast(60) = 5 − 2 = 3.

4 · 🔄 Circular Index — Wrap Any Jump With + n

🎯 Cue: a circular array where you jump by a value that can be negative (LC 457 Circular Array Loop, LC 3379 Transformed Array).

next = ((i + step) % n + n) % n;   // always 0…n-1

• ⚠️ Why: JS % keeps the sign of the left side, so (0 - 1) % 5 is -1, an invalid index.
• 🧠 % n brings it into -(n-1)…n-1, + n makes it non-negative, the last % n folds it back under n.

5 · 🔗 One-to-One Mapping — Check Both Directions

🎯 Cue: "each X maps to exactly one Y, and no two X share a Y". LC 205 Isomorphic Strings, LC 290 Word Pattern.

• 🔁 Keep X→Y consistent and Y→X consistent.
• 🧰 Two maps, or one map plus a Set of used values.
• ⚠️ One direction is not enough: "ab" → "aa" passes X→Y but fails Y→X.

6 · ✂️ Split Into k Pieces — k−1 Cuts, and Each Cut Leaves Room for the Pieces After It

🎯 A string of n characters has n − 1 gaps. k pieces = pick k − 1 gaps (3 pieces → 2 cuts 🔪🔪). This is the same fence-post idea as Recursion #12, here used to write the loop bounds.

👀 Read it: write the index below each number and the cut in the gap before it. Cut 0 and cut n (dashed) are the ends, not real cuts, so real cuts are 1 … n − 1. Cut c = slice(…, c) ends before index c.

for (let i = 1; i <= n - 2; i++)          // slice cuts
    for (let j = i + 1; j <= n - 1; j++) {}

for (let i = 0; i < n - 2; i++)           // array ends
    for (let j = i + 1; j < n - 1; j++) {}

🔒 Why the limits stop early: every piece after a cut needs at least 1 character. The 3rd piece needs 1 → j stops 1 early. The 2nd and 3rd need 2 → i stops 2 early. The array version is just the slice version shifted by 1.

7 · 🔁 Each Index Needs Its Left + Right → Precompute Both, Don't Rescan

🐢 Brute force: for each i, loop left to get the max, loop right to get the max → n × n = O(n²).

💡 Spot the waste: every i rescans the same cells. The max up to i is just the max up to i − 1, plus h[i]. So one pass each way → O(n).

🌧️ LC 42 Trapping Rain Water, h = [4,2,0,3,2,5]: water at i = min(leftMax, rightMax) − h[i]

Total = 9.

for (let i = 0; i < n; i++)      left[i]  = Math.max(h[i], i > 0 ? left[i - 1] : 0)
for (let i = n - 1; i >= 0; i--) right[i] = Math.max(h[i], i < n - 1 ? right[i + 1] : 0)

🧱 Include h[i] in both maxes, so the water is never negative.

✖️ Same shape, other operations: LC 238 Product Except Self = product before i × product after i. Range sums are #1.

Checked in Node: brute force and left/right arrays both give 6 and 9 on the LC 42 examples, and agree on 2,000 random arrays.

8 · 📏 Intervals — Sort by Start or End, Overlap = Latest Start ≤ Earliest End

1️⃣ Sort first: by start or by end?

2️⃣ Overlap check

• 📈 Sorted by start: just s2 ≤ e1 (does the next one start before this one ends?)
• 🔀 Unsorted: max(s1, s2) ≤ min(e1, e2)

3️⃣ Touching edges ⚠️ [1,2] & [2,3]

Checked in Node: the overlap formula matches a brute-force point check on 5,000 random pairs, and 56, 435, 452, 253 give the LC example answers plus the touching results above. Full patterns: Intervals cheat sheet.

1 · 🔢 Sieve of Eratosthenes

2 · 🍕 A % B when A < B → Always Just A

🎯 Smaller % bigger = the number itself. B goes into A zero times → nothing gets subtracted off.

2 % 6 = 2     3 % 10 = 3     1 % 2 = 1

3 · 🧮 Pairs vs Subarrays vs Subsets — How Many?

n = 3
pairs:        (0,1) (0,2) (1,2)         = 3
subarrays:    3 pairs + (0,0)(1,1)(2,2) = 6
every (i, j): 3 × 3                     = 9
subsets:      2 × 2 × 2                 = 8

4 · ⚡ XOR Stays Inside the Bits → Range 0 … 2ᵇ − 1 = Your Memo Size

🧠 Rule: max value → how many bits (b) → XOR stays inside those bits → range 0 … 2ᵇ − 1 → that's your memo / array size.

💡 Other ops:

• ✅ OR | → only turns bits on, never adds a new bit → same range
• ✅ AND & → only turns bits off → ≤ the smallest value
• ❌ Sum + → carries add new bits (1023 + 1 = 1024)

const b = 32 - Math.clz32(maxVal) // 1000 → 10
const size = 1 << b               // 1024 slots

Where it's used: LC 3882 Min XOR Path, memo on (i, j, x). Checked in Node: XOR / OR of 200,000 random sets never left 0 … 2ᵇ − 1, AND never passed the smallest value.

1 · 🚨 JS Never Throws on Out-of-Bounds Array Access

🎯 arr[100] (too big) or arr[-1] (negative) → both silently return undefined. NO crash, NO error.

💥 One case does crash: a missing ROW. dp[n] is undefined, so dp[n][j] throws TypeError: Cannot read properties of undefined.

📐 Where I hit this: Stone Game DP — dp[i+1][j-1] when j=0 reads dp[1][-1] → undefined → Math.min(0, undefined) = NaN → cascaded corruption through the whole table.

✅ The fix: ?? 0 (or another sensible default) right at the access point:

dp[i+1][j-1] ?? 0   // undefined → 0, before it reaches Math.min/arithmetic

2 · 🚨 || / && Short-Circuit SILENTLY Skips a Second Call With Side Effects

🎯 A || B and A && B don't always evaluate both sides — JS stops early the moment the result is already decided.

A || B → if A is truthy, B is NEVER CALLED (result already true)
A && B → if A is falsy,  B is NEVER CALLED (result already false)

📐 Where it bit — LC 1579 (Remove Max Edges, dual Union-Find for Alice+Bob):

if(alice.union(u, v) || bob.union(u, v)) edgesUsed++;   // ❌

If alice.union(u, v) returns true (union succeeded), bob.union(u, v) never runs at all — short-circuited. For a "shared" edge meant to help BOTH graphs, Bob's DSU silently misses the merge whenever Alice's happens to succeed first. No error, no crash — just a wrong final answer.

✅ Fix — call both FIRST, combine the booleans AFTER:

const usedByAlice = alice.union(u, v);
const usedByBob = bob.union(u, v);
if (usedByAlice || usedByBob) edgesUsed++;

3 · ➗ Binary Search Mid — >> 1 Overflows Past 2³¹ − 1, Use Math.floor

💥 The bug: lo and hi each fit, but lo + hi can pass 2³¹ − 1. Then >> 1 overflows → rubbish mid → rubbish answer (or an endless loop → TLE).

lo = 1.5e9, hi = 2e9              // each fits ✅, sum = 3.5e9 ❌
(lo + hi) >> 1                    // -397483648 💥 rubbish
Math.floor((lo + hi) / 2)         // 1750000000 ✅
lo + ((hi - lo) >> 1)             // 1750000000 ✅ uses the gap, not the sum

Checked in Node: the outputs above, and a search on [0, 2e9] with >> 1 never ends.