1. Later-slot / Fluency / chapter 05 families
Short form. Open the chapter 05 id for the full compilable Java.
All Nodes Distance K without parent map IE-asked
Question they ask. You are given a binary tree and a target node. Return every node value whose path distance from the target is exactly k. They may forbid storing a parent Map.
Example. Tree: root 1, left 2, right 3; 2 has left 4 and right 5. Target = node 5, k = 2. Paths of length 2 from 5: 5→2→1 and 5→2→4. Answer: [1, 4] (order does not matter). Use their drawing if they draw a different tree.
Dry run — walk this before you code.
Say out loud. I will not store Map<Node,Node>. Parent is a DFS argument. Then BFS from the target. Time O(n), space O(n).
Source. LC 7406809 AUTA R2; LC 7623949 Fluency-labeled slot was DSA. Full Java: distance-k-no-parent-map.
Clue → pattern. Tree + distance K + they forbid a parent Map → undirected view or recursive return.
Why this. Distance K from a target needs parent edges. Storing Map<Node,Node> is what they banned. Pass parent as a DFS argument while you build adj, then BFS from target. Or recurse: find returns distance to target; on the way up, collect the other subtree at k−dist−1.
Brute. Store parent map (forbidden) or enumerate all nodes and path-length via LCA O(n²). Time O(n²). Space O(n).
Optimal. Build undirected adj O(n), BFS O(n). No parent HashMap. Time O(n). Space O(n).
int dfs(TreeNode n, TreeNode t, int k, List<Integer> a) {
if (n == null) return -1;
if (n == t) { down(n, k, a); return 0; }
int L = dfs(n.left, t, k, a);
if (L >= 0) { if (L + 1 == k) a.add(n.val); down(n.right, k - L - 2, a); return L + 1; }
int R = dfs(n.right, t, k, a);
if (R >= 0) { if (R + 1 == k) a.add(n.val); down(n.left, k - R - 2, a); return R + 1; }
return -1;
}
Fluency invite can still be this tree. Write the tree first. Intern LC 7643209 unnamed min-heap is not Distance K.
Next Greater Element IE-asked
Question they ask. For every index, find the first value to its right that is strictly greater. If none, -1. Confirm: one array vs two arrays; circular or not.
Example. Input [2, 1, 2, 4, 3] → output [4, 2, 4, -1, -1].
Dry run — walk this before you code.
Say out loud. Brute is nested j>i, O(n²). Optimal: decreasing ArrayDeque of indices. Next-greater-same digits is next permutation, not this.
Source. LC 7724048 mapped R3 HM. Full Java: next-greater-element.
Clue → pattern. Next greater / next warmer day → monotonic stack.
Why this. Each index waits for the first later larger value. A decreasing stack of unresolved indices pops when today is the answer. Nested scan is the brute they expect you to name.
Brute. For each i scan i+1..n−1. Time O(n²). Space O(1).
Optimal. ArrayDeque of indices, decreasing values. Time O(n). Space O(n).
int[] nge(int[] a) {
int n = a.length; int[] ans = new int[n]; Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && st.peek() <= a[i]) st.pop();
if (!st.isEmpty()) ans[i] = st.peek();
st.push(a[i]);
}
return ans;
}
Next greater same digits is next permutation, not this stack.
Dynamic k-th largest (k changes) IE-asked
Question they ask. Maintain the k-th largest while numbers are added (and k may change). Not a static sort-once.
Example. Stream [4, 5, 8, 2], k=3. After these four, 3rd largest is 4. Then add 3; 3rd largest is still 4. If they set k=2, 2nd largest is 5.
Dry run — walk this before you code.
Say out loud. Size-k min-heap: peek is kth. If they delete arbitrary values, TreeMap counts, not a Java PriorityQueue.
Source. LC 7850431 mapped R3. Full Java: dynamic-kth-largest.
Clue → pattern. Kth while the stream / k moves → heap policy, not one sort.
Why this. Static kth is size-k min-heap. If k or the set changes, you need a structure that inserts/deletes. Size-k heap still works if you re-fill; two heaps if it is a running median-like policy.
Brute. Sort after every update. Time O(q n log n). Space O(n).
Optimal. Min-heap of size k, or TreeMap counts if they delete arbitrary values. Time O(log n) per update typical. Space O(n).
PriorityQueue min = new PriorityQueue<>(); // size k
Quickselect is for a static array, not a stream of updates.
Variation of Find All Anagrams IE-asked
Question they ask. Find every start index where a substring of s is an anagram of p (same letters, any order). Window length is |p|.
Example. s = cbaebabacd, p = abc → starts [0, 6] because cba and bac match.
Dry run — walk this before you code.
Say out loud. Do not sort every substring. Fixed window + int[26]. Group-anagrams of whole words is a different map-of-keys problem.
Source. LC 8362604 AUTA R3 HM. Full Java: find-anagrams-variation.
Clue → pattern. Same multiset in a window of length p → fixed window + counts.
Why this. Anagram = same frequencies. Window size is |p|. Slide one char; compare 26-counts. Not “exactly K distinct.”
Brute. Sort every substring of length m. Time O(n m log m). Space O(m).
Optimal. int[26] need vs have; match counter. Time O(n). Space O(1).
// add s[r]; remove s[r-m]; if match record r-m+1
Group anagrams (whole strings) is HashMap of sorted key — different card (Sachin LC 49).
Combine Garlands / connect ropes IE-asked
Question they ask. You repeatedly glue two ropes/garlands. Cost of a glue is the sum of those two lengths. The new rope goes back into the pile. Minimize total cost.
Example. [4, 3, 2, 6]. Always merge the two smallest.
Dry run — walk this before you code.
Say out loud. Why not sort once? After 2+3 the new 5 competes with 4. Heap, not Koko (Koko is binary search on speed).
Source. LC 8362604 AUTA; GFG 2025 Connect Sticks (OA-as-R1 on that GFG). Full Java: combine-garlands.
Clue → pattern. Repeatedly merge two pieces, cost = sum → min-heap.
Why this. After you merge, the new length goes back into the set. One sort is wrong because the merge order is data-dependent. Always take the two smallest.
Brute. Try all merge orders. Time exponential. Space O(n).
Optimal. PriorityQueue; poll+poll, add cost, offer sum. Use long. Time O(n log n). Space O(n).
while (pq.size() > 1) { long s = pq.poll() + pq.poll(); cost += s; pq.offer(s); }
Koko min-speed is BS on answer, not this heap.
Count Number of Nice Subarrays IE-asked
Question they ask. Count contiguous subarrays that contain exactly k odd numbers.
Example. [1,1,2,1,1], k=3 → 2 subarrays: [1,1,2,1] and [1,2,1,1].
Dry run — walk this before you code.
Say out loud. Odds are 0/1. Exact-sum with negatives is prefix+HashMap, not this window.
Source. LC 6806195 AUTA BR. Full Java: nice-subarrays.
Clue → pattern. Exactly K odds in a subarray → atMost(K) − atMost(K−1).
Why this. Odds are a 0/1 budget. “Exactly K” is not monotone; “at most K” is. Subtract.
Brute. All L,R count odds. Time O(n²). Space O(1).
Optimal. Two sliding windows on odd count. Time O(n). Space O(1).
int atMost(int[] a, int k) {
int l = 0, odds = 0, ans = 0;
for (int r = 0; r < a.length; r++) {
odds += a[r] & 1;
while (odds > k) odds -= a[l++] & 1;
ans += r - l + 1;
}
return ans;
}
int numberOfNice(int[] a, int k) { return atMost(a, k) - atMost(a, k - 1); }
Exact sum with negatives is prefix+map, not this window. Do not prefix-sum odds into a HashMap unless they want a different exact-sum wording — window is enough on 0/1.
Tree path A/B/C print IE-asked
Question they ask. UNNAMED print format. They named nodes A/B/C on a tree and wanted a path printed or marked. Ask what A, B, C are and what to print.
Example. Suppose A=2, B=5, C unused. Path 2-1-5. Do not invent their letters.
Dry run — walk this before you code.
Say out loud. Do not stamp LC 236 as the asked id. Confirm the print spec, then DFS.
Source. LC 7406809 AUTA BR. UNNAMED details — no LC id. Full Java: tree-path-abc.
Clue → pattern. Print / mark a path between named nodes on a tree.
Why this. Find LCA or recurse “does this subtree contain A/B/C.” Stay unnamed on the exact print format they used.
Brute. All pairs paths. Time O(n²). Space O(n).
Optimal. One or two DFS; parent-as-arg if they ban a map. Time O(n). Space O(n).
// do not invent the print spec; ask what A/B/C means
Unnamed stays unnamed. Do not stamp LC 236 as “what they asked.”
Top-K Frequent Elements IE-asked
Question they ask. Return the k values that appear most often. Order of the k answers: ask.
Example. [1,1,1,2,2,3], k=2 → [1,2].
Dry run — walk this before you code.
Say out loud. O(n log k) after counting. Bucket sort if frequencies are in 1..n. A live stream of “top k so far” is a different structure.
Source. LC 7406809 AUTA R1; TUF 12 live. Full Java: top-k-frequent.
Clue → pattern. Top K by frequency → HashMap + size-K heap (or bucket).
Why this. Count first. Then you only need K extremes, not a full sort of n keys.
Brute. Sort unique keys by freq. Time O(u log u). Space O(n).
Optimal. Min-heap size K on freq, or bucket[freq] lists if freq ≤ n. Time O(n log K). Space O(n).
// freq map then min-heap of [freq, key] size k
Stream “K most frequent so far” is a different running structure (DevBrainiac BR — NMF loop shape).
Merge k sorted linked lists IE-asked
Question they ask. Merge k already-sorted linked lists into one sorted list.
Example. lists = [1→4→5], [1→3→4], [2→6] → 1→1→2→3→4→4→5→6.
Dry run — walk this before you code.
Say out loud. Use Integer.compare. Pairwise merge is O(kN); heap is tighter when k is not tiny.
Source. LC 7563011 AUTA R2; Bhavya R1. Full Java: merge-k-lists.
Clue → pattern. K sorted lists → min-heap of current heads.
Why this. The next global min is the min of k heads. Heap of size k. Pairwise merge is O(kN); heap is O(N log k).
Brute. Collect all values, sort. Time O(N log N). Space O(N).
Optimal. PriorityQueue<ListNode> of k heads. Time O(N log k). Space O(k).
pq.offer heads; dummy tail; while pq: n=poll; tail.next=n; if (n.next) pq.offer(n.next);
Integer.compare on node.val — do not use b−a.
Maximum Sum Linked List from two sorted lists (common nodes) IE-asked
Question they ask. Two sorted linked lists. Some values appear in both (common nodes). You may switch lists only at a common value. Build the list with the maximum node-sum.
Example. A: 1→3→30→90→120→150. B: 0→3→12→32→90→100→120→180. Commons 3, 90, 120. Take the better segment between commons. You may switch only at a common value. Not LC 962.
Dry run — walk this before you code.
Say out loud. Do not stamp LC 962 or LC 210. Delivery-stations topo is a different problem on the same IE.
Source. LC 6881058 / LC 6369243. Do NOT stamp LC 962. Full Java: max-sum-switching-lists.
Clue → pattern. Two sorted lists, may switch only at equal values → two pointers, take better segment.
Why this. Common values are switch points. Accumulate each segment; at a common node take max of the two running sums and reset.
Brute. Enumerate every switch sequence. Time exponential. Space O(1).
Optimal. Two pointers on already-sorted lists O(n+m). Time O(n+m). Space O(1) extra if you relink.
// p, q walk like merge. If p.val < q.val: sumA += p.val; p = p.next;
// else if q.val < p.val: sumB += q.val; q = q.next;
// else /* common */: attach heavier of (segA, segB), then the common once;
// reset both segment sums; p = p.next; q = q.next;
// after loop: heavier tail. Do not stamp LC 962.
Not LC 962 / not LC 210. Delivery-stations topo is a sibling on 6369243, different problem.
Grid paths avoiding −1, then max reward IE-asked
Question they ask. Grid, only right and down. Some cells are traps (−1). (1) count paths from top-left to bottom-right. (2) follow-up: max reward on a valid path. OA-as-R1 on that IE — their later “R3” is often this loop’s already-done R2 analogue.
Example. 3×3, traps on some cells, start 0,0 end n-1,n-1.
Dry run — walk this before you code.
Say out loud. Say OA-as-R1 remap. Unique Paths II is the count-only sibling.
Source. LC 6800853 AUTA. OA-as-R1: their later live is often this loop’s completed R2 analogue. Full Java: grid-paths-max-reward.
Clue → pattern. Right/down only, traps, count then max → DP.
Why this. DAG moves ⇒ dp[i][j] from left/up. Count ways separately from max score. DFS without memo explodes.
Brute. Recurse every path. Time exponential. Space O(mn).
Optimal. DP count + DP max. Rolling 1D if they want space. Time O(mn). Space O(mn) or O(n).
if (g[i][j]==-1) dp=0; else dp = from_up + from_left;
OA-as-R1 remap. Unique Paths II is the no-reward sibling — Swati similar-not-exact.
Min ops reduce n to 0 subtracting a digit of n IE-asked
Question they ask. Start from n. In one operation subtract one digit that currently appears in n. Minimize operations to reach 0. Example they wrote: n=27 → 5 operations.
Example. n=27. Digits of 27 are 2 and 7. You cannot subtract 9 just because 9 is a digit in general.
Dry run — walk this before you code.
Say out loud. Not Koko (Koko searches a speed). Digits are of the current value.
Source. LC 6800853 same IE. Example n=27 → 5. Full Java: reduce-by-digit.
Clue → pattern. Integer state, unweighted op → BFS. Greedy largest digit is not proven.
Why this. From n you can go to n−d for each digit d of n. Shortest sequence is BFS on integers 0..n.
Brute. Recurse every digit choice. Time exponential with overlap. Space O(n).
Optimal. Queue BFS, dist[x]. Time O(n · digits). Space O(n).
q.offer(n); while: for digit in x: nxt=x-d; if unseen offer
Not Koko. Not “subtract any 1..9.” Digits are of the current value.
Encoded string frequency 1226#24#(2) IE-asked
Question they ask. Parse an encoded string like 1226#24#(2) into letter frequencies (length-26 counts). Do not confuse with Decode Ways (number of interpretations).
Example. Classic mapping: 1=a … 26=z with # for two-digit, and (2) repeats the previous token. Lock their grammar on the example they wrote → they said it becomes something like abzxx family. Use their mapping.
Dry run — walk this before you code.
Say out loud. Decode Ways ii (TUF 02) counts interpretations of digits and *. Different family.
Source. LC 6800853 mapped our R1 analogue (OA-as-R1). Full Java: encoded-frequency.
Clue → pattern. Grammar parse → index walk + count[26], not a window.
Why this. #, two-digit letters, and “(2)” repeats are a parser. Expanding the full string can explode. They asked frequencies — multiply into a 26-array.
Brute. Decode fully, then count. Time O(decoded) may be huge. Space O(decoded).
Optimal. Parse O(n), count[26]. Time O(n). Space O(1).
int[] freq = new int[26]; // walk i, handle # and (k)
Not Decode Ways (number of interpretations). TUF 02 Decode Ways ii is a different live title.
Rotten Oranges IE-asked
Question they ask. In a grid, 0 empty, 1 fresh orange, 2 rotten. Every minute, rotten oranges rot 4-neighbors. Return minutes until no fresh left, or −1.
Example. One 2 in the corner and fresh oranges in a chain. Minutes = BFS layers.
Dry run — walk this before you code.
Say out loud. Brute rescan of the whole grid each minute is O((mn)²). Multi-source BFS is O(mn).
Source. igreaper / GFG 2025 / LC 7406809 variation / TUF 11. Mixed OA-as-R1. Full Java: rotten-oranges.
Clue → pattern. Minutes until all rot → multi-source BFS.
Why this. Every rotten orange starts at time 0. Each minute is one BFS layer. DFS cannot keep global time. Fresh count == 0 or −1.
Brute. Rescan the grid every minute. Time O((mn)²). Space O(1).
Optimal. Queue all 2s first; layer BFS. Time O(mn). Space O(mn).
// offer all rotten; while q && fresh: sz=q.size(); minutes++; …
If they said variation, ask 4-dir vs 8-dir and whether already-all-rotten is 0.
Maximal Rectangle of 1s IE-asked
Question they ask. Largest rectangle containing only 1s in a 0/1 matrix (axis-aligned).
Example. One row [1,0,1,1,1] is already a histogram of heights 1,0,1,1,1. Largest 1-height rectangle width 3.
Dry run — walk this before you code.
Say out loud. Brute all sub-rectangles is O(m²n²). Do not confuse with Largest Submatrix With Rearrangements.
Source. igreaper their R3 = our R2 analogue. Full Java: maximal-rectangle.
Clue → pattern. Largest 1s rectangle → histogram per row + monotonic stack.
Why this. height[j] = consecutive 1s ending at this row. Largest rectangle in histogram is next-smaller left/right via stack.
Brute. All sub-rectangles. Time O(m²n²). Space O(1).
Optimal. O(n) stack per row. Time O(mn). Space O(n).
// for each row update height[]; largestRectangle(height)
Largest Submatrix With Rearrangements (TUF 18 HM) lets you reorder columns — different.
Unique Paths II / obstacle grid DP IE-asked
Question they ask. Count paths from top-left to bottom-right, only right and down, zeros on obstacles.
Example. 2×2 open grid: 2 paths (right-down, down-right). If the end is blocked, 0.
Dry run — walk this before you code.
Say out loud. DFS all paths is exponential. Label similar-not-exact if they said similar to Unique Paths II.
Source. TUF 06/10/20; Swati similar-not-exact; LC 7035289 Unique Paths–like BR. Full Java: unique-paths-obstacles.
Clue → pattern. Number of ways right/down with blockers → DP.
Why this. Ways add from left and up. Obstacle zeroes the cell. Rolling 1D is enough.
Brute. DFS all paths. Time exponential. Space O(mn).
Optimal. dp[j] += dp[j-1] with obstacle = 0. Time O(mn). Space O(n).
if (obstacle) dp[j]=0; else if (j>0) dp[j]+=dp[j-1];
Max reward follow-up is a second DP, not the same array. Label similar-not-exact when they said similar.
Course Schedule II / directed cycle IE-asked
Question they ask. n courses, list of prerequisites [a,b] meaning b before a. Return a valid order, or say it is impossible (cycle).
Example. n=2, prereq [1,0] → order [0,1]. If also [0,1], cycle, impossible.
Dry run — walk this before you code.
Say out loud. LC 210 was linked on LC 6282609 only. Do not stamp 210 on delivery-stations (LC 6369243).
Source. LC 6282609 linked LC 210 on that post only. TUF 03 Kahn. Full Java: course-schedule.
Clue → pattern. Prereq / can finish → Kahn or DFS colors.
Why this. You can finish iff DAG. Kahn emits an order and detects leftover nodes.
Brute. All permutations. Time O(n!). Space O(n).
Optimal. indegree + queue O(V+E). Time O(V+E). Space O(V+E).
cycle = order.size() < n;
Do not copy 210 onto LC 6369243 delivery stations.
Sliding Window Maximum IE-asked
Question they ask. For every contiguous window of size k, return the maximum in that window.
Example. [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7].
Dry run — walk this before you code.
Say out loud. Scanning each window is O(nk). Heap is O(n log n). Deque is the Live Code answer at n=1e5.
Source. GFG sde1-off-campus R1 story wrap; 1-year-experienced-2 their R3. Full Java: sliding-window-maximum.
Clue → pattern. Max in every window of k → monotonic deque.
Why this. Deque of decreasing indices; front is max; drop expired; drop back if ≤ a[i].
Brute. Scan each window. Time O(nk). Space O(1).
Optimal. ArrayDeque amortized O(n). Time O(n). Space O(k).
// pollFirst expired; pollLast while a[last]<=a[i]; offerLast i
Heap of window is n log n — say deque if n=1e5.
House Robber I → II (circular) IE-asked
Question they ask. Houses in a line: max money, cannot rob two adjacent. Follow-up: houses in a circle (first and last are adjacent).
Example. Linear [1,2,3,1] → 4 (1+3). Circle same array → cannot take both 1s at ends; max of rob(0..n-2) and rob(1..n-1) = 4 still, or 3 on other arrays.
Dry run — walk this before you code.
Say out loud. House Robber III is a tree. Do not stamp III on a line.
Source. LC 8029194 R1 named; Sachin R2 LC 213. Full Java: house-robber-ii.
Clue → pattern. Max sum no two adjacent; circular → split.
Why this. Linear is dp: skip or take+prev-skip. Circular forbids both ends → max of two linear ranges.
Brute. 2^n subsets with adjacency check. Time O(2^n). Space O(n).
Optimal. O(n) two linear passes. Time O(n). Space O(1).
return Math.max(robLine(0,n-2), robLine(1,n-1));
House Robber III is tree DP (intern family). Do not stamp III on a linear prompt.
Merge Intervals IE-asked
Question they ask. Given half-open or closed intervals, merge all overlapping ones. Ask inclusive ends.
Example. [1,3],[2,6],[8,10],[15,18] → [1,6],[8,10],[15,18].
Dry run — walk this before you code.
Say out loud. Min platforms counts how many overlap at once. That is a different card.
Source. GFG fresher R1; TUF OA also — OA is not a live round. Full Java: merge-intervals.
Clue → pattern. Overlap unions → sort by start, greedy merge.
Why this. After sort, only the last emitted interval can overlap the next.
Brute. Pairwise union-find. Time O(n²). Space O(n).
Optimal. Sort + linear merge. Time O(n log n). Space O(n).
if (iv[i][0] <= cur[1]) cur[1]=max; else emit
Min platforms is concurrent count, not merge.
Minimum Platforms / Meeting Rooms II IE-asked
Question they ask. Trains/meetings with start and end. How many platforms/rooms do you need so no two overlap on one platform?
Example. starts 900, 940, 950. ends 910, 1200, 1120. Need 3 at the peak.
Dry run — walk this before you code.
Say out loud. This is interval-count DSA, not the Meeting Room Scheduler product in chapter 22.
Source. Prabhash R1; GFG off-campus-10 their R3; TUF 06. Mentor extra-DSA is not 10454435. Full Java: minimum-platforms.
Clue → pattern. How many overlap at once → sweep or min-heap of ends.
Why this. A room/platform frees at the earliest end. Sort starts/ends or heap ends.
Brute. For each meeting scan others. Time O(n²). Space O(1).
Optimal. O(n log n) sweep. Time O(n log n). Space O(n).
if (starts[i] < ends[j]) { cur++; i++; } else { cur--; j++; }
Not the Meeting Room Scheduler product (ch.22). This is the interval-count DSA.
Celebrity Problem IE-asked
Question they ask. In n people, a celebrity is known by everyone and knows nobody. You may call knows(i,j). Find the celebrity or −1.
Example. n=3. 0 knows 1, 1 knows nobody, 2 knows 1. Celebrity is 1 if 0 and 2 both know 1 and 1 knows neither.
Dry run — walk this before you code.
Say out loud. Brute is O(n²) matrix. Older Amazon classic, not 2026 AUTA default. Still rehearse.
Source. GFG off-campus-10 year-out remainder. Standard CS classic. Full Java: celebrity.
Clue → pattern. Everyone knows X, X knows nobody → eliminate.
Why this. One knows() discards one person. Verify the survivor’s row/column.
Brute. O(n²) matrix scan. Time O(n²). Space O(1).
Optimal. O(n) eliminate + O(n) verify. Time O(n). Space O(1).
if (knows(a,i)) a=i; then verify
Not 2026 AUTA default. Still rehearse — older Amazon classic.
Min Stack variation (object with size and id) IE-asked
Question they ask. Stack with push/pop/top and getMin in O(1). Variation: the object also carries size and id, not only the min integer.
Example. push 3, push 5, getMin=3, push 2, getMin=2, pop, getMin=3.
Dry run — walk this before you code.
Say out loud. Heap is the wrong DS for O(1) min. Store a record if they want id/size.
Source. TUF 07/09 their R2 (no OA in that write-up). Ch.05 + TUF “more complex Min Stack.” Full Java: min-stack.
Clue → pattern. O(1) min plus extra fields → aux stack of pairs, not a heap.
Why this. Heap is log n. Two stacks: values, and mins (or pairs (val,minSoFar)). Variation asked for size+id on the object — store a record, still O(1) if min is on the aux top.
Brute. Scan the stack each min query. Time O(n) per min. Space O(n).
Optimal. ArrayDeque of records; min field copied down. Time O(1). Space O(n).
st.push(new Rec(x, id, st.isEmpty()?x:Math.min(x, st.peek().min)));
Candidate tried stack+map+PQ — say why that is slower than aux min.
LRU Cache IE-asked
Question they ask. Cache of capacity cap. get(key) and put(key,val) in O(1). Evict the least recently used key when full. If they say LFU, that is frequency buckets — TUF 15 URL vs body conflict, ask.
Example. cap=2. put 1, put 2, get 1, put 3 → 2 is evicted because 1 was used more recently.
Dry run — walk this before you code.
Say out loud. LinkedHashMap only if you know access-order + removeEldest. Prefer HashMap+DLL in Live Code.
Source. Bhavya Hyd Interview 2; TUF 15 linked LRU but body said LFU — write the conflict. Full Java: lru-cache.
Clue → pattern. O(1) get/put eviction of least recent → HashMap + DLL.
Why this. Hash finds the node; DLL splice is O(1) move-to-front. LinkedHashMap access-order is the library version — they often want the hand-rolled pair.
Brute. List scan to find / evict. Time O(n). Space O(n).
Optimal. HashMap<Integer,Node> + dummy head/tail. Time O(1). Space O(capacity).
// remove(node); addFront(node); if size>cap evict tail.prev
Not Login Tracker (unverified). If they said LFU, add freq buckets.
Open the Lock (similar) IE-asked
Question they ask. 4-digit lock, each wheel 0–9 wrap. Deadends blocked. Min turns from 0000 to target, or −1. Similar-to on that IE — confirm exact IO.
Example. target 0202, a few deadends. Each move changes one digit ±1.
Dry run — walk this before you code.
Say out loud. Do not stamp LC 752 unless they linked it.
Source. LC 7623949 similar to Open the Lock. Full Java: open-lock.
Clue → pattern. 4-digit wheel, deadends, min turns → BFS on strings/ints.
Why this. Unweighted moves (±1 on one digit). Deadends are blocked nodes. DFS is not shortest.
Brute. All sequences. Time exponential. Space O(10^4).
Optimal. BFS, 10000 states. Time O(10000 · 8). Space O(10000).
// state as int 0..9999; ±1 on each digit with wrap
Similar-to, not stamped as exact LC 752 unless they linked it. This post also had Distance K in Fluency.
Max path between two leaves / two-leaves path IE-asked
Question they ask. Maximum path sum between two leaves (not the any-node path that can start in the middle). Do not clamp a negative child to zero the way LC 124 does.
Example. A node with left leaf 3 and right leaf −1: through-node sum is 3+(node)+(−1) if both sides must be leaves. Ask if a single child still counts as a leaf-path.
Dry run — walk this before you code.
Say out loud. Paste-only until the bible has a URL. Ask the leaf constraint out loud.
Source. ch.05 max-path-between-leaves; _answers/09-dsa-new-ies.md. Full Java: max-path-between-leaves.
Clue → pattern. Path value through a node using two child heights → tree DP.
Why this. At each node, best path that goes through it is left-gain + right-gain + val. Return the best downward gain to the parent.
Brute. All leaf pairs. Time O(n²). Space O(n).
Optimal. One DFS. Time O(n). Space O(h).
int down = val + max(0, max(L,R)); global = max(L+R+val);
Diameter in hops vs weighted path — ask which.
Remove K Digits IE-asked
Question they ask. Remove exactly k digits from a number-string so the remaining number is the smallest possible. Keep order. Strip leading zeros.
Example. num=1432219, k=3 → 1219 (drop 4,3,2).
Dry run — walk this before you code.
Say out loud. Maximize instead of minimize flips the compare. Phone LC 6630775 is OA-as-R1 remap.
Source. LC 6630775 phone (OA-as-R1 remap). Intern DesiQnA Set-61 = INTERN. Full Java: remove-k-digits.
Clue → pattern. Delete k digits, smallest number → increasing monotonic stack.
Why this. A larger digit in a more significant place is worse if you can still delete.
Brute. All subsets of deletions. Time C(n,k). Space O(n).
Optimal. Stack O(n). Strip leading zeros. Time O(n). Space O(n).
while (k>0 && !st.isEmpty() && st.peek()>c) { st.pop(); k--; }
Maximize instead of minimize flips the compare.
Most frequent subtree sum IE-asked
Question they ask. For every node, subtree sum = node + left + right. Return the subtree-sum value(s) that occur most often.
Example. A small tree where two subtrees both sum to 2 → answer [2].
Dry run — walk this before you code.
Say out loud. Equal-split tree wants total/2, not the mode. Different card.
Source. ch.05 most-frequent-subtree-sum. Full Java: most-frequent-subtree-sum.
Clue → pattern. Subtree sums + frequencies → postorder + HashMap.
Why this. A subtree sum is left+right+val. Count those sums; take the mode.
Brute. For each node rescan the subtree. Time O(n²). Space O(n).
Optimal. One postorder; map sum→count. Time O(n). Space O(n).
int sum = u.val + dfs(u.left) + dfs(u.right); freq.merge(sum,1,Integer::sum);
Equal-split tree wants total/2, not the mode of sums.
Longest increasing path in a matrix IE-asked
Question they ask. Longest strictly increasing path in a matrix; from a cell you may walk 4-dir to a strictly larger neighbor. Do not stamp LC 329 as Job 10454435.
Example. A cell 1 next to 2 next to 9 → length 3 if that chain is the longest.
Dry run — walk this before you code.
Say out loud. Prince right/diag max-sum is a different DAG. Year-out GFG BR.
Source. ch.05 longest-increasing-path-matrix. Full Java: longest-increasing-path-matrix.
Clue → pattern. 4-dir increasing path → memo DFS, not Unique Paths DP.
Why this. Moves are not a DAG from origin; they are “to a strictly larger neighbor.” Memoize best path from each cell.
Brute. DFS every path. Time exponential. Space O(mn).
Optimal. memo[i][j] = 1+max(legal neighbors). Time O(mn). Space O(mn).
if (memo[i][j]!=0) return memo[i][j];
Prince right/diag max-sum is a different DAG DP. Do not stamp Falling Path as identical.
Kth ancestor (even / binary lifting family) IE-asked
Question they ask. Sum (or list) of nodes whose k-th ancestor is even — year-out GFG twist. First you need k-th parent of each node.
Example. Root 1, child 2, grandchild 4, k=1: 4’s 1st ancestor is 2 (even) → include 4.
Dry run — walk this before you code.
Say out loud. Year-out. Do not invent LC 1483 as this Job ID.
Source. ch.05 kth-ancestor-even. Full Java: kth-ancestor-even.
Clue → pattern. Repeated parent hops → binary lifting or climb.
Why this. k jumps on parent[] is O(k). Precompute up[i][p] = 2^p parent for O(log k).
Brute. Walk parent k times per query. Time O(q k). Space O(n).
Optimal. Binary lifting O(n log n) preprocess, O(log k) query. Time O(n log n + q log k). Space O(n log n).
// up[v][0]=parent; up[v][j]=up[ up[v][j-1] ][j-1]
If they said a twist (“even”), stay with their constraint; do not invent LC 1483 as Job 10454435.
Distance between two nodes / LCA then path IE-asked
Question they ask. Distance between two nodes in a binary tree (shortest path unique).
Example. A and B with LCA L. dist = depth[A]+depth[B]−2·depth[L].
Dry run — walk this before you code.
Say out loud. If they ban a parent map, pass parent as an argument like Distance K.
Source. TUF 11 Binary Tree Shortest Path; ch.05 distance-two-nodes. Full Java: distance-two-nodes.
Clue → pattern. Two nodes on a tree → LCA, dist = d(a)+d(b)−2d(lca).
Why this. Unique path. Find LCA; depths from root or from LCA.
Brute. BFS from A to B after building undirected. Time O(n). Space O(n).
Optimal. One or two DFS. Same O(n). Time O(n). Space O(n).
// dist(u,v) = depth[u]+depth[v]-2*depth[lca]
LCA II/III TUF 14/21 are node-pointer variants (parent pointers on III).
Stack get-middle IE-asked
Question they ask. Stack that also returns the middle element in O(1) (or O(1) delete middle — ask).
Example. push 1,2,3,4,5. Middle is 3. pop → middle becomes 3 or 2 depending on even/odd rule — lock it.
Dry run — walk this before you code.
Say out loud. Do not use ArrayList get(mid) if they also want O(1) push at the front of a vector — DLL is the intended structure.
Source. ch.05 stack-get-middle. Full Java: stack-get-middle.
Clue → pattern. Push/pop + get mid → DLL + mid pointer, or two structures.
Why this. ArrayList get mid is O(1) but pop front is O(n). DLL with a mid pointer moves mid on size parity.
Brute. Vector + index mid each time O(n) push at 0. Time O(n). Space O(n).
Optimal. DLL + mid. O(1) all if they allow custom nodes. Time O(1). Space O(n).
// if size odd after push, mid = mid.next; pop reverse
java.util.Stack is legacy. ArrayDeque has no O(1) middle.
Next Permutation IE-asked
Question they ask. Rearrange the array into the next lexicographic permutation. If already last, reverse to the first. “Next greater with same digits” is this, not NGE stack.
Example. [1,2,3] → [1,3,2]. [3,2,1] → [1,2,3].
Dry run — walk this before you code.
Say out loud. Prabhash mixed this wording with NGE. Ask: next permutation or next greater element?
Source. AUTA LC 6806195 similar; Prabhash next greater same digits. Full Java: next-permutation.
Clue → pattern. Next lexicographic arrangement → pivot from right, swap, reverse suffix.
Why this. Longest non-increasing suffix is already the last perm of those digits. Pivot is the left descent; swap with the rightmost successor; reverse suffix.
Brute. Generate all perms, pick next. Time O(n!). Space O(n!).
Optimal. O(n) in-place. Time O(n). Space O(1).
// i from n-2 while a[i]>=a[i+1]; swap with rightmost > a[i]; reverse i+1..end
Not NGE stack. “Same digits” wording is this, not next greater element.
Count of smaller numbers after self IE-asked
Question they ask. For each index i, count how many j > i have a[j] < a[i]. NMF / year-out — label it. Do not treat as AUTA default.
Example. [5,2,6,1] → [2,1,1,0].
Dry run — walk this before you code.
Say out loud. If the IE was US/FTC, NMF. Fenwick is rare SDE I — still know the inversion idea.
Source. ch.05 count-smaller-after-self. Bible / 09-dsa-new-ies: NMF or year-out — label it. Full Java: count-smaller-after-self.
Clue → pattern. For each i, count j>i with a[j]
Why this. Inversion-like. Brute n². Merge sort while counting right-half smaller, or Fenwick on ranks.
Brute. Nested j>i. Time O(n²). Space O(1).
Optimal. O(n log n) merge or BIT. Time O(n log n). Space O(n).
// fenwick on compressed ranks, iterate right to left
NMF-possible (Hyderabad onsite paste; not UTA two-DSA default). Candidate named LC 315 on that paste — do not copy that id onto unnamed “count smaller” prompts. Not a 10454435 forecast.
Minimum / generalized Knight Moves IE-asked
Question they ask. Min knight hops from a square to a target (infinite board or chessboard — ask). Generalized deltas: same BFS, different DIRS.
Example. From (0,0) to (2,1) is 1 hop on a standard knight.
Dry run — walk this before you code.
Say out loud. DFS depth-limit is exponential. BFS on visited cells.
Source. LC 6629948 Minimum Knight Moves; ch.05 generalized-knight-moves. Full Java: generalized-knight-moves.
Clue → pattern. Knight on infinite/chess board min hops → BFS.
Why this. Unweighted hops. Symmetric — you can BFS in one quadrant. Generalized deltas: same BFS, different DIRS.
Brute. DFS depth-limit. Time exponential. Space O(visited).
Optimal. BFS O(cells reached). Time O(area). Space O(area).
int[][] K = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
Race Car is a different BFS-on-state (position, speed) — GFG sde-1-34.
Partition to target / combination sum family IE-asked
Question they ask. Can you pick a subset that sums to target T? (Or list partitions — ask.)
Example. [1,5,11,5], T=11 → yes (11, or 5+5+1).
Dry run — walk this before you code.
Say out loud. Factor Combinations is backtracking on factors, not subset-sum.
Source. ch.05 partition-target-combination. Full Java: partition-target-combination.
Clue → pattern. Can you pick a subset summing to T → DP knapsack or backtrack if n small.
Why this. 0/1 knapsack boolean dp[t]. Backtrack if they want the actual partitions.
Brute. All subsets. Time O(2^n). Space O(n).
Optimal. dp[x] |= dp[x−a[i]]; O(nT). Time O(nT). Space O(T).
boolean[] dp = new boolean[t+1]; dp[0]=true;
Factor Combinations TUF 201 BR is backtracking on factors, not subset-sum.
Device capability (pasted-IE family) IE-asked
Question they ask. Pasted-IE family. Open chapter 05. Do not invent a LeetCode id. Remap in chapter 18 before treating it as your third live.
Example. Capability / version numbers usually sort + greedy or binary search on a threshold. Use their paste.
Dry run — walk this before you code.
Say out loud. Do not restamp a random LC.
Source. ch.05 device-capability — remap in ch.18 before treating as your third live. Full Java: device-capability.
Clue → pattern. Read the pasted stem. Do not invent a LeetCode id.
Why this. Capability / version gating is usually sort + greedy or BS on answer. Open the ch.05 card; stay with their constraints.
Brute. Depends on the paste. Time see ch.05. Space see ch.05.
Optimal. See chapter 05 — do not restamp. Time see ch.05. Space see ch.05.
// open 05-dsa.html#device-capability
Pasted IE ≠ Job 10454435. OA-as-R1 remap in chapter 18.
Server partitions (pasted-IE family) IE-asked
Question they ask. Pasted-IE. Split / load servers. If “minimize the max load”, that is binary search on answer. If machines are a graph, DSU.
Example. Lock IO from the paste.
Dry run — walk this before you code.
Say out loud. Open chapter 05. Unnamed paste.
Source. ch.05 server-partitions. Full Java: server-partitions.
Clue → pattern. Split servers / load → often minimize-max BS or greedy pack.
Why this. If the paste is “partition so max load is minimized,” that is BS on answer. If it is connected components of machines, DSU.
Brute. see ch.05 Time see ch.05. Space see ch.05.
Optimal. see ch.05 Time see ch.05. Space see ch.05.
// open 05-dsa.html#server-partitions
Unnamed paste stays unnamed. Not a 10454435 lock.
Loyal customer logs (pasted-IE family) IE-asked
Question they ask. Pasted logs: customer id + day. “Loyal” usually means seen on ≥ k distinct days or in a window. Ask the definition.
Example. Do not invent a metric.
Dry run — walk this before you code.
Say out loud. Not Nisarg’s k-page sequence unless they said pages.
Source. ch.05 loyal-customer-logs. Full Java: loyal-customer-logs.
Clue → pattern. Logs + customer ids + dates → HashMap of sets / sliding on days.
Why this. “Loyal” usually means appeared on ≥k distinct days or in a window. Parse, then map customer → TreeSet of days.
Brute. see ch.05 Time see ch.05. Space see ch.05.
Optimal. see ch.05 Time see ch.05. Space see ch.05.
// open 05-dsa.html#loyal-customer-logs
Do not invent a metric. Ask the definition of loyal.
Logger message global IE-asked
Question they ask. shouldPrintMessage(t, msg): print if this message was not printed in the last 10 seconds. Not the distributed Rate Limiter (count = 1, not UTA).
Example. print foo at t=1, again at t=2 → false, at t=11 → true.
Dry run — walk this before you code.
Say out loud. Classic logger rate limit. Related to logger LLD, not Login Tracker.
Source. ch.05 logger-message-global. Related to logger LLD in bible §5.C Reddit 1ueybmg. Full Java: logger-message-global.
Clue → pattern. Rate-limit messages / shouldPrintMessage → HashMap timestamp.
Why this. Classic LC 359 family: map message→last print; allow if t >= last+10. This is not the distributed Rate Limiter (count = 1, not UTA).
Brute. List of all prints, scan. Time O(n). Space O(n).
Optimal. HashMap O(1) average. Time O(1). Space O(#messages).
if (!map.containsKey(m) || t >= map.get(m)+10) { map.put(m,t); return true; }
Do not upgrade this to Redis/Kafka HLD on a two-DSA loop.
Basic calculator OOD / expression IE-asked
Question they ask. Evaluate + − * / and/or parentheses. Ask which operators. RPN (TUF 17) is postfix — different card.
Example. 2-1+2 = 3. (1+(4+5+2)-3)+(6+8) = 23.
Dry run — walk this before you code.
Say out loud. OOD wrap is Strategy for ops only if they asked classes.
Source. ch.05 basic-calculator-ood. Full Java: basic-calculator-ood.
Clue → pattern. Parse +−*/ or nested parens → stack of signs / nums.
Why this. One pass with a sign stack handles +− and parens. * / need a tighter last-number hold. OOD wrap is Strategy for ops if they asked classes.
Brute. Eval with a library — they will refuse. Time —. Space —.
Optimal. Stack O(n). Time O(n). Space O(n).
// sign, num, stack; on +− flush; on ( push sign
Evaluate RPN TUF 17 is the postfix sibling — stack of values, not infix.
2. Bible §5.A remainder (deduped against §1)
Still other candidates, still not Job 10454435. OA-as-R1 flagged on the source line when the bible says so.
Count Complete Subarrays IE-asked
Question they ask. A subarray is complete if it contains every distinct value that appears in the whole array. Count them. GFG 2025 first live (OA-as-R1).
Example. Array with global distinct = 3. Once a window already holds all 3, every extension to the right is also complete.
Dry run — walk this before you code.
Say out loud. OA-as-R1: their later Connect Sticks + Rotten is often our R2 analogue.
Source. GFG 2025 off-campus. OA-as-R1 first live.
Clue → pattern. Complete = contains all distinct of the whole array → window at-most / two pointers on distinct.
Why this. Once the window holds every global distinct, every extension to the right is also complete. Count with a shrink/expand on HashMap size vs global size.
Brute. All L,R; HashSet slice vs global. Time O(n²). Space O(Σ).
Optimal. O(n) window. Time O(n). Space O(Σ).
// let need = global distinct; expand r until size==need; ans += n-r; shrink
OA-as-R1: their “R3” Connect Sticks + Rotten is often our R2 analogue.
Daily Temperatures–like monotonic stack IE-asked
Question they ask. For each day, how many days until a warmer temperature? If none, 0. Same stack as NGE, answers are distances.
Example. [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].
Dry run — walk this before you code.
Say out loud. Naina UTA R1 similar-to. Second R1 problem was UNNAMED — do not invent it.
Source. Naina Medium UTA R1 12 Jun 2025.
Clue → pattern. Days until a warmer temperature → NGE distances.
Why this. Same decreasing stack; store index; answer[i] = j−i.
Brute. O(n²) scan. Time O(n²). Space O(1).
Optimal. O(n) stack. Time O(n). Space O(n).
ans[st.pop()] = i - st.peek() /* after pop compare */;
Second R1 problem was UNNAMED logic-heavy — do not invent it.
Path Sum–like tree IE-asked
Question they ask. Path-sum–like on a tree (Akash snippet). Ask: root-to-leaf equals target, or any path?
Example. Root-to-leaf: subtract node val, at a leaf check remaining==0.
Dry run — walk this before you code.
Say out loud. Snippet only. Similar-not-exact.
Source. Akash LinkedIn AUTA Jan 2026 snippet.
Clue → pattern. Root-to-leaf or any-path sum → DFS remaining.
Why this. Subtract node val; at leaf check 0. Any-path is prefix + HashMap on the tree (path sum III family) — they said similar; ask.
Brute. All paths. Time O(n²). Space O(h).
Optimal. DFS O(n) for root-to-leaf. Time O(n). Space O(h).
boolean dfs(u, left) { if (u==null) return false; if (leaf && left==u.val) return true; }
Snippet only. Similar-not-exact.
Currency Converter (graph) IE-asked
Question they ask. Equations a/b = w. Query x/y as a product along a path, or −1 if disconnected. TUF Evaluate Division similar.
Example. a/b=2, b/c=3, query a/c → 6.
Dry run — walk this before you code.
Say out loud. Shiwangi UTA R1. Do not invent FX APIs.
Source. Shiwangi Medium UTA R1. TUF 01 Evaluate Division similar.
Clue → pattern. a/b = w equations, query product → weighted DFS/BFS.
Why this. Each equation is a bidirectional edge with weight w and 1/w. Query is a path product. HashMap of adj.
Brute. Try all conversion sequences. Time exponential. Space O(V+E).
Optimal. DFS/BFS per query or Floyd if few currencies. Time O(V+E) per query. Space O(V+E).
// adj.get(a).add({b,w}); adj.get(b).add({a,1/w}); dfs multiply
TUF linked Evaluate Division — similar. Do not invent extra FX APIs.
Number of Islands IE-asked
Question they ask. Count 4-connected groups of '1' land in a grid.
Example. Two blobs separated by water → 2.
Dry run — walk this before you code.
Say out loud. AUTA LC 8362604 R1 / Deepak.
Source. LC 8362604 AUTA R1; Deepak Jul 2026.
Clue → pattern. Grid components → flood DFS/BFS.
Why this. Each unvisited land starts a component. Mark visited in-place.
Brute. Union every adjacent pair with a slow structure. Time O(mn α). Space O(mn).
Optimal. DFS flood O(mn). Time O(mn). Space O(mn) stack worst.
if (g[i][j]=='1') { dfs; islands++; }
Max area / distinct islands are follow-ups, not assumed.
Median of Data Stream IE-asked
Question they ask. Insert numbers over time; after each insert (or on query) return the median.
Example. 1, then 2 → median 1.5; then 3 → median 2.
Dry run — walk this before you code.
Say out loud. Integer overflow on (a+b)/2 — use /2.0 after peek.
Source. LC 8362604 AUTA R1; LC 6475219.
Clue → pattern. Running median → two heaps.
Why this. Low max-heap, high min-heap; sizes differ by ≤1. Rebalance on insert.
Brute. Keep a sorted list, insert O(n). Time O(n) per add. Space O(n).
Optimal. Two PriorityQueues. Time O(log n) add, O(1) median. Space O(n).
// if x<=low.peek() low else high; then rebalance sizes
Integer overflow on (a+b)/2 — use /2.0 after peek.
Generate all subsets IE-asked
Question they ask. Generate every subset of an array (power set). n is small.
Example. [1,2] → [], [1], [2], [1,2].
Dry run — walk this before you code.
Say out loud. AUTA LC 7406809 R1 linked.
Source. LC 7406809 AUTA R1 LC-linked.
Clue → pattern. All combinations of include/skip → backtracking.
Why this. n ≤ ~20. Each element in or out. Output size 2^n is required.
Brute. Same exponential, generate then unique. Time O(2^n · n). Space O(n).
Optimal. Choose/skip recurse. Time O(2^n · n). Space O(n).
path.add; recurse i+1; path.remove; recurse i+1;
Count of subsets with a constraint is DP, not this.
Koko / Capacity to Ship Packages / BS-on-answer family IE-asked
Question they ask. Minimum eating speed / ship capacity so you finish in ≤ H hours/days. Binary search the answer, not the index.
Example. Piles [3,6,7,11], H=8 → min speed 4 (Koko family). Capacity to ship packages is the same monotone feasible.
Dry run — walk this before you code.
Say out loud. TUF 13 Smallest Divisor and TUF 16 Bouquets are the same family. Naina UTA R2 Koko-like.
Source. Naina UTA R2 Koko-like; LC 6806195 Ship Packages AUTA; TUF 07/09 Koko (no OA in that IE).
Clue → pattern. Min speed/capacity so hours/days ≤ H → BS on answer + feasible.
Why this. Larger capacity always succeeds if smaller does. feasible is a linear pack. Heap is the wrong first tool.
Brute. Try every speed 1..max. Time O(MAX · n). Space O(1).
Optimal. O(n log RANGE). Time O(n log RANGE). Space O(1).
if (feasible(mid)) { ans=mid; hi=mid-1; } else lo=mid+1;
TUF 13 Smallest Divisor and TUF 16 Min Days Bouquets are the same family.
Asteroid Collision (similar) IE-asked
Question they ask. Asteroids on a line: positive go right, negative left. Same magnitude: both explode; smaller abs explodes.
Example. [5,10,-5] → [5,10] (−5 explodes). [8,-8] → empty.
Dry run — walk this before you code.
Say out loud. Similar-to on AUTA 6806195. Intern TUF 104 is INTERN.
Source. LC 6806195 similar R1; Parimal ~Apr 2026 named; TUF 16 live; intern TUF 104.
Clue → pattern. Opposite directions destroy → stack of survivors.
Why this. A right-mover waits. A left-mover fights the stack top while the top is smaller and right-going.
Brute. Rescan the list after each collision. Time O(n²). Space O(n).
Optimal. ArrayDeque O(n). Time O(n). Space O(n).
while (!st.isEmpty() && incoming<0 && st.peek()>0) { /* compare abs */ }
Similar-to on 6806195. Intern 104 is INTERN.
Similar to Cheapest Flights Within K Stops IE-asked
Question they ask. n cities, flights [from, to, price], src, dst, and at most k stops (so ≤ k+1 edges). Cheapest price, or −1. Similar-to — lock their k meaning (stops vs edges).
Example. n=4, flights 0→1 cost 100, 1→2 cost 100, 0→2 cost 500, 0→3 cost 100, 3→2 cost 100, src=0, dst=2, k=1 stop. Direct 0→2 is 500. Path 0→1→2 uses 1 stop and costs 200. Path 0→3→2 also 1 stop, cost 200.
Dry run — walk this before you code.
Say out loud. State is (node, stops). Bellman k+1 rounds or PQ on (cost, node, stops). Do not stamp LC 787 as exact.
Source. LC 7850431 snippet R1.
Clue → pattern. Weighted graph, at most K edges → BFS/Bellman relax K+1 times, not plain Dijkstra.
Why this. Dijkstra without a stop dimension can take a cheap long path that uses too many stops. State is (node, stops).
Brute. All walks with ≤K edges. Time exponential. Space O(V).
Optimal. Relax E edges K+1 rounds or PQ on (cost,node,stops). Time O(K · E). Space O(K V).
int[] dist = new int[n]; Arrays.fill(dist, INF); dist[src] = 0;
for (int i = 0; i <= k; i++) {
int[] nd = dist.clone();
for (int[] e : flights) if (dist[e[0]] < INF) nd[e[1]] = Math.min(nd[e[1]], dist[e[0]] + e[2]);
dist = nd;
}
return dist[dst] == INF ? -1 : dist[dst];
Snippet “similar to.” Do not stamp LC 787 as exact. Dijkstra without a stop dimension is the trap.
Power allocation max-min (BS-on-answer) IE-asked
Question they ask. Allocate power/resource to n parts. Maximize the minimum any part gets. Ask the exact constraint (sum ≤ budget, or stations on a line).
Example. Stalls/positions [1, 2, 4, 8, 9], place 3 cows, maximize min gap. Same monotone as Aggressive Cows / chapter 25.
Dry run — walk this before you code.
Say out loud. Binary search the answer. Greedy place / pack is the check. Snippet — lock the assignment constraint.
Source. LC 7850431 snippet R1.
Clue → pattern. Maximize the minimum allocation → BS on T + feasible.
Why this. Same maximize-minimum card as chapter 25.
Brute. Try every T. Time O(MAX · n). Space O(1).
Optimal. O(n log RANGE). Time O(n log RANGE). Space O(1).
// feasible(T): can we assign so every part >= T
Snippet. Ask the assignment constraint out loud.
Detonate the Maximum Bombs IE-asked
Question they ask. Bombs at (x,y) with radius r. Detonating i detonates every j with distance ≤ r[i]. Max bombs in one chain.
Example. A at (0,0) r=2; B at (1,0) r=1; C at (10,0) r=1. A reaches B (dist 1 ≤ 2). B does not reach A if dist 1 > r[B]? 1≤1, yes. C is alone.
Dry run — walk this before you code.
Say out loud. Graph + DFS/BFS from each start. O(n²). Not a union-find unless radii are symmetric.
Source. LC 7724048 snippet R1.
Clue → pattern. Bomb i reaches j if dist ≤ radius → directed graph, DFS/BFS count.
Why this. Asymmetric radii ⇒ directed edges. From each start, count reachable. O(n²) build + O(n) search.
Brute. Same O(n²) to test pairs — that is also the build. Time O(n³) naive recompute. Space O(n²).
Optimal. Build adj O(n²), DFS each source O(n²). Time O(n²). Space O(n²).
// if dist2 <= r*r add edge i→j; dfs count
Snippet. Confirm Euclidean vs Manhattan.
Diameter of Binary Tree variation IE-asked
Question they ask. Longest path in a binary tree (or a general tree). Ask: hop count vs weighted edges; binary vs n-ary.
Example. Tree 1—2—3 with 2 also having child 4. Longest path 3-2-4 or 3-2-1, length 2 hops.
Dry run — walk this before you code.
Say out loud. Ask hop vs weight. Variation — do not assume LC 543 wording.
Source. LC 7280347 13 Aug 2025.
Clue → pattern. Longest path in a tree → two heights or two BFS.
Why this. See chapter 25 tree-diameter.
Brute. All pairs. Time O(n²). Space O(n).
Optimal. One DFS heights. Time O(n). Space O(h).
d = max(d, leftH+rightH); return 1+max(leftH,rightH);
Variation — ask hop vs weight.
Uni-valued subtrees; Search in Rotated Sorted Array IE-asked
Question they ask. Two problems on one R1: (1) count uni-valued subtrees (every node in the subtree equal). (2) search a target in a rotated sorted array.
Example. Tree: 5 with left 5 and right 5, left-left 5, left-right 4. Uni subtrees: each leaf, the right 5, not the whole tree. Rotated: [4,5,6,7,0,1,2] target 0 → index 4.
Dry run — walk this before you code.
Say out loud. Two titles. Speak both. Rotated: one half is sorted — that is the invariant.
Source. LC 6461439 28 Jan 2025.
Clue → pattern. Two problems: tree all-equal subtrees (postorder flag); rotated search (BS + mid side).
Why this. Uni-valued: a subtree is uni if both children are uni and values match. Rotated: one half is sorted; decide which half holds the target.
Brute. Recompute subtree set each node; linear search rotated. Time O(n²) / O(n). Space O(n).
Optimal. O(n) tree; O(log n) rotated. Time O(n) / O(log n). Space O(h) / O(1).
// if a[l]<=a[mid] left sorted else right sorted
Two titles on one R1. Single element in sorted array (LC 6475219 R2) is a different rotated/xor BS.
Longest Repeating Character Replacement variation IE-asked
Question they ask. Longest substring you can make all-same by replacing at most k characters. Variation — lock if they meant something else.
Example. s = AABABBA, k=1. Window AABA length 4, maxFreq A=3, replacements 4−3=1 ≤ k. Answer 4.
Dry run — walk this before you code.
Say out loud. Not find-all-anagrams. Window + max frequency.
Source. Prince Medium 17 Oct 2025. Candidate linked LC 424. Job 3057703 — not 10454435.
Clue → pattern. Replace at most k to make a repeating window → window + max-freq.
Why this. Window is valid while (length − maxFreq) ≤ k. MaxFreq does not have to decrement on shrink for this problem (standard trick).
Brute. All windows. Time O(n²). Space O(1).
Optimal. O(n) window, int[26]. Time O(n). Space O(1).
while (r-l+1 - maxf > k) shrink;
Different Job ID. Pattern reuse only.
Count good-review words; sort reviews IE-asked
Question they ask. Given review strings and a set of “good” words, count good words per review and/or sort reviews by their rule. Ask the sort key.
Example. good = {good, great}. Reviews: “good product”, “ok”, “great and good”. Counts 1, 0, 2.
Dry run — walk this before you code.
Say out loud. Membership then sort. Speak the comparator they stated.
Source. LC 6570344 14 Mar 2025.
Clue → pattern. Words + a good-set → HashSet lookup; then sort by their rule.
Why this. Membership is O(1) average. Sorting is whatever comparator they stated — ask.
Brute. For each word scan the good list. Time O(n · G). Space O(1).
Optimal. HashSet of good words. Time O(n + sort). Space O(G).
if (good.contains(w)) cnt++;
Do not invent the sort key. HashMap internals were asked after a review-word-count in bible §5.F — be ready.
Min Arrows to Burst Balloons IE-asked
Question they ask. Balloons as intervals [start, end] on a number line. One arrow at x bursts every balloon covering x. Minimum arrows.
Example. [1,6], [2,8], [7,12], [10,16]. One arrow at 6 bursts the first two. One at 12 bursts the last two. Answer 2.
Dry run — walk this before you code.
Say out loud. Greedy on earliest end. Count groups, do not emit merged ranges.
Source. Deepak Jul 2026 with Islands.
Clue → pattern. Points on a line, shoot if overlap → sort by end, greedy.
Why this. Earliest-ending balloon must be shot; that arrow bursts all that cover that end.
Brute. Try all arrow x. Time O(n²). Space O(1).
Optimal. Sort by end O(n log n). Time O(n log n). Space O(1).
if (start > arrow) { arrows++; arrow=end; }
Not merge-intervals output — it is a count of non-overlappable groups.
Burning Tree IE-asked
Question they ask. Tree (usually binary). Fire starts at a target. Each minute it spreads to adjacent nodes. Minutes to burn all. Parent map may be banned.
Example. Same tree as Distance K: 1 with 2,3; 2 with 4,5. Start at 5. Minute 1: 2. Minute 2: 1 and 4. Minute 3: 3. Answer 3.
Dry run — walk this before you code.
Say out loud. BFS from target after you can walk to parent. Not Distance K’s “collect layer k.”
Source. GFG fresher 25 Jan 2025 R1 with Merge Intervals.
Clue → pattern. Minutes for fire from a target to all nodes → parent links + BFS.
Why this. Fire spreads to parent and children. Build parent map (or undirected adj) then multi-source is just BFS from target; time = max dist.
Brute. Simulate sets of burning nodes each minute naively. Time O(n²). Space O(n).
Optimal. BFS O(n). Time O(n). Space O(n).
// parent[u]=p; q.offer(target); max dist
If they ban parent map, pass parent as DFS arg then BFS — same as Distance K.
Race Car IE-asked
Question they ask. Start position 0 speed +1. Instruction A: pos += speed, speed *= 2. R: speed = −1 if speed>0 else +1 (and speed sign flip per their statement). Min instructions to reach target. Year-out remainder.
Example. target = 3. A → pos 1 speed 2. A → pos 3 speed 4. Two A’s. (Exact A/R table: use their statement.)
Dry run — walk this before you code.
Say out loud. BFS on state. Not UTA-default. Still the template if they name Race Car.
Source. GFG sde-1-34 ~2024 slug race-car. Reprint sde-1off-campus-2023.
Clue → pattern. Position + speed state, A/R instructions → BFS on state.
Why this. Not a 1D DP on position only — speed is part of the state. BFS min instructions.
Brute. All instruction strings. Time exponential. Space O(states).
Optimal. BFS (pos, speed). Time O(states). Space O(states).
// state key = pos+":"+speed; A: pos+=speed; speed*=2; R: speed = speed>0?-1:1
Year-out remainder, not UTA-default. Still a BFS-on-state template.
Search in Rotated Sorted Array; circular Kadane IE-asked
Question they ask. Two problems: search in rotated sorted array; maximum subarray sum on a circular array.
Example. Rotated: [4,5,6,7,0,1,2] target 0. Circular Kadane: [5, −3, 5] wrap 5+5=10 beats linear 5.
Dry run — walk this before you code.
Say out loud. Circular max = max(kadane, total − minSubarray) with the all-negative guard.
Source. LC 8014509 Apr 2026.
Clue → pattern. Rotated search = BS. Circular max subarray = max(kadane, total−minSubarray) with the all-negative guard.
Why this. Wrap max is total minus the worst middle segment, unless that would take nothing.
Brute. Rotate + linear; all wrap intervals. Time O(n²). Space O(1).
Optimal. O(n) kadane + min-kadane; O(log n) rotated search. Time O(n) / O(log n). Space O(1).
return Math.max(kadane, total - minKadane); // if not all negative
House Robber circular is a different split (cannot take both ends).
Group anagrams (small modifications) IE-asked
Question they ask. Group the strings that are anagrams of each other. Small modifications — ask if they want sorted groups or original order.
Example. [eat, tea, tan, ate, nat, bat] → groups {eat,tea,ate}, {tan,nat}, {bat}.
Dry run — walk this before you code.
Say out loud. HashMap of canonical keys. O(n L log L) if you sort each string.
Source. Sachin LinkedIn LC 49 ~May 2026.
Clue → pattern. Group strings that are anagrams → map of sorted key or count-key.
Why this. Canonical key is sorted chars or int[26] frozen as a string.
Brute. Compare every pair. Time O(n² · L). Space O(nL).
Optimal. HashMap<String,List>. Time O(n L log L) sorted key. Space O(nL).
char[] c=s.toCharArray(); Arrays.sort(c); map.computeIfAbsent(new String(c), …)
Find-all-anagrams-in-a-string is a window, not grouping whole strings.
Longest Valid Parentheses; Median of Two Sorted Arrays IE-asked
Question they ask. Two heavy titles: longest valid parentheses substring; median of two sorted arrays (log time).
Example. Parens: ()(() longest valid is 2. Median: [1,3] and [2] → 2.
Dry run — walk this before you code.
Say out loud. Parens O(n) stack or DP. Median O(log(n+m)) partition. Do not merge then pick middle unless n is tiny.
Source. LC 6606011 26 Mar 2025.
Clue → pattern. Longest valid () → stack of indices or DP. Median of two sorted → BS on partition (hard).
Why this. Valid parens: stack of last unmatched ‘(’ index; gap is length. Median: binary search the cut so left-max ≤ right-min.
Brute. All substrings check balance; merge arrays O(n+m). Time O(n²) / O(n+m). Space O(n).
Optimal. O(n) stack; O(log(n+m)) median BS. Time O(n) / O(log(n+m)). Space O(n) / O(1).
// stack push -1; on ) pop; if empty push i else ans=max(i-st.peek())
Two heavy titles in one R1. Median-of-two is easy to burn the clock — speak the partition invariant first.
Heaters; Max Width of Binary Tree IE-asked
Question they ask. Heaters: houses and heater positions; min radius so every house is covered. Max width of BT: max (rightmost−leftmost+1) index on any level.
Example. Houses [1,2,3,4], heaters [1,4]. Radius 1 covers (house 2 needs heater at 1, dist 1). Width: complete 3-level tree width 4 at the bottom.
Dry run — walk this before you code.
Say out loud. Heaters: monotone radius. Width: BFS indices, not node values.
Source. LC 7035289 AUTA ~2025.
Clue → pattern. Heaters: min radius to cover houses → BS on answer or two pointers on sorted. Width: BFS with column indices.
Why this. Radius R covers if every house has a heater within R — monotone. Width is last-first index on a level; use long for 2^height.
Brute. Try R; BFS without indices. Time O(R · n) / O(n). Space O(n).
Optimal. O(n log RANGE) heaters; O(n) width. Time see opt. Space O(n).
// width: q.offer({node, idx}); ans = max(ans, last-first+1)
TUF 11 also named Max Width live. Heaters is the BS sibling on the same AUTA post.
Trapping Rainwater; DP on Stocks IE-asked
Question they ask. Trap rain water on heights; and a stocks DP (buy/sell, maybe cooldown or 2 transactions — ask).
Example. Rain: [0,1,0,2,1,0,1,3,2,1,2,1] water 6. Stocks II (unlimited): prices [7,1,5,3,6,4] profit 7.
Dry run — walk this before you code.
Say out loud. Rain is min(Lmax,Rmax)−h. Stocks is state DP. Lock k.
Source. igreaper Nov 2025. OA-as-R1 first live.
Clue → pattern. Rain: Lmax/Rmax or stack. Stocks: state DP.
Why this. Water at i is min(leftMax,rightMax)−h[i]. Stocks: hold/cash transitions.
Brute. For each i scan left and right; recurse stock days. Time O(n²) / O(2^n). Space O(1) / O(n).
Optimal. O(n) two arrays or two pointers; O(n) stock states. Time O(n). Space O(n) or O(1).
water += Math.max(0, Math.min(l[i], r[i]) - h[i]);
OA-as-R1. Their later Maximal Rectangle is our R2 analogue on that write-up.
GetRandom O(1); sqrt to 8 decimals IE-asked
Question they ask. O(1) insert, delete, getRandom on a set of ints; and compute sqrt(x) to 8 decimals (no library if they forbid).
Example. Insert 1,2,3; delete 2; getRandom uniformly 1 or 3. sqrt(2) ≈ 1.41421356.
Dry run — walk this before you code.
Say out loud. Map + compact array. Sqrt is real binary search or Newton. Not Job 10454435.
Source. LC 6573582 Feb 2025 BLR.
Clue → pattern. Insert/delete/getRandom O(1) → HashMap + ArrayList swap-delete. Sqrt: binary search reals or Newton.
Why this. Random index needs a compact array. Delete = swap with last. Sqrt: BS on double until precision.
Brute. List.contains O(n); Math.sqrt if they allow. Time O(n) / library. Space O(n).
Optimal. Map+list O(1); BS log PRECISION. Time O(1) / O(log P). Space O(n) / O(1).
int i=map.get(x); int last=arr.get(arr.size()-1); arr.set(i,last); map.put(last,i); arr.remove(arr.size()-1);
Reddit 1lqy9uq also GetRandom on R2. Two IEs, still not 10454435.
Zig-Zag BT; Largest BST in BT IE-asked
Question they ask. Zigzag (level-order, alternate reverse); and size of the largest BST subtree in a binary tree.
Example. Zigzag on 3 / 9,20 / 15,7 → [[3],[20,9],[15,7]]. Largest BST: a tree that is not a BST but a subtree of 3 nodes is.
Dry run — walk this before you code.
Say out loud. Zigzag is BFS. Largest BST is one postorder with bounds. Keys and Rooms was R2 on that IE.
Source. LC 6491881 Feb 2025.
Clue → pattern. Zigzag = BFS + reverse odd levels. Largest BST = postorder (min,max,size,isBST).
Why this. Level order with a deque (addFirst/addLast) or collect then reverse. BST check must return bounds so a parent can validate.
Brute. Inorder all subtrees. Time O(n²). Space O(n).
Optimal. O(n) both. Time O(n). Space O(n).
// Info dfs: if left.bst && right.bst && left.max < u.val < right.min
Keys and Rooms was R2 on the same IE.
Find Median from stream; max sum level in BT IE-asked
Question they ask. Running median of a stream; and the level of a binary tree with maximum node-sum (1-based level).
Example. Stream 1,2,3 → medians 1, 1.5, 2. Tree levels sums 1 | 2+3=5 | … return the level with max sum (tie: smallest level — ask).
Dry run — walk this before you code.
Say out loud. Heaps for stream. BFS for level sum. long, not int.
Source. LC 6475219 Feb 2025 BLR.
Clue → pattern. Two heaps + BFS level sums.
Why this. Already covered median. Level sum is BFS; track max.
Brute. Sort stream; DFS levels with extra maps. Time O(n log n). Space O(n).
Optimal. Heaps + BFS. Time O(log n) / O(n). Space O(n).
// TUF 13 Maximum Level Sum is the same BFS family.
Same IE also had single-element-in-sorted and LL sum-0 nodes on R2.
Equal-split tree (remove one edge) IE-asked
Question they ask. Remove exactly one edge from a tree so the two sides have equal node-value sums (or equal counts — ask). Return yes/the edge.
Example. Values: root 1 with children 2 and 3; total 6. Subtree 3 equals 6/2. Cut the edge to 3.
Dry run — walk this before you code.
Say out loud. One DFS returning subtree sums. Not a graph diameter.
Source. Naina UTA R2. Candidate said GFG.
Clue → pattern. Remove one edge, two equal node-sum halves → subtree sums.
Why this. If any subtree sum == total/2 (total even), you can cut that edge. One DFS.
Brute. Remove each edge, sum both sides. Time O(n²). Space O(n).
Optimal. One DFS returning subtree sum. Time O(n). Space O(h).
if (sub*2==total) found=true; return sub;
Follow-ups they wrote: why not BFS, recursion banned, space. Speak iterative stack if asked.
Row with max 1s in row-sorted 0/1 matrix IE-asked
Question they ask. m×n matrix, each row sorted 0s then 1s. Return the row with the most 1s (or its index). Ties: ask first vs last.
Example. Row0 0 0 1 1, row1 0 1 1 1, row2 0 0 0 1. Row 1 has three 1s.
Dry run — walk this before you code.
Say out loud. Staircase. Binary search per row is O(m log n) — mention then upgrade.
Source. IE.in 2024-grad AUTA mail R2.
Clue → pattern. Rows sorted 0 then 1 → staircase from top-right O(m+n).
Why this. Never move right. Left means this row has more ones; down tries the next row with the same column bound.
Brute. Count 1s per row O(mn) or BS per row O(m log n). Time O(mn). Space O(1).
Optimal. O(m+n) staircase. Time O(m+n). Space O(1).
int j=n; for i: while (j>0 && mat[i][j-1]==1) j--; track n-j
Search 2D Matrix II (TUF 21) is staircase for a target, same walk.
Bipartite students / enemies not same group IE-asked
Question they ask. Students (or nodes); enemy pairs cannot share a group. Can you split into two groups?
Example. Enemies (1-2),(2-3),(3-1). Triangle. Odd cycle → no.
Dry run — walk this before you code.
Say out loud. O(V+E) 2-color. Odd cycle is the no.
Source. LC 8362604 AUTA R2.
Clue → pattern. Enemy edges → 2-color BFS/DFS.
Why this. Odd cycle ⇒ impossible. Each component colored independently.
Brute. 2^n assignments. Time O(2^n). Space O(n).
Optimal. O(V+E) color. Time O(V+E). Space O(V).
if (col[v]==-1) col[v]=col[u]^1; else if (col[v]==col[u]) return false;
Not topo. Not DSU unless you DSU “must-same” and check enemy pairs.
Rotate Image 90° IE-asked
Question they ask. Rotate an n×n matrix 90° clockwise in place.
Example. [[1,2,3],[4,5,6],[7,8,9]] → [[7,4,1],[8,5,2],[9,6,3]].
Dry run — walk this before you code.
Say out loud. Transpose + reverse rows. Extra matrix is the brute they want named.
Source. LC 6806195 AUTA R2 with Next Perm similar.
Clue → pattern. In-place 90 clockwise → transpose then reverse each row.
Why this. (i,j) → (j, n-1-i). Transpose is (i,j)↔(j,i); reverse row finishes it.
Brute. Extra matrix. Time O(n²). Space O(n²).
Optimal. In-place O(n²) time O(1) extra. Time O(n²). Space O(1).
swap m[i][j], m[j][i]; then reverse row
Anti-clockwise is transpose + reverse columns. Ask.
Longest subarray sum = 0 IE-asked
Question they ask. Longest subarray whose sum is 0 (negatives allowed).
Example. [15, −2, 2, −8, 1, 7, 10, 23]. Subarray −2,2,−8,1,7 sums to 0, length 5.
Dry run — walk this before you code.
Say out loud. HashMap prefix → first index. Count of zero-sum subarrays is a different map (counts, not first).
Source. LC 7850431 snippet R2.
Clue → pattern. Exact sum 0 → prefix + first-index HashMap.
Why this. prefix[j]−prefix[i]=0 ⇒ same prefix. Store first occurrence to maximize j−i.
Brute. All L,R. Time O(n²). Space O(1).
Optimal. O(n) map. Time O(n). Space O(n).
if (!map.containsKey(sum)) map.put(sum,i); else ans=max(i-map.get(sum));
Count of zero-sum subarrays stores counts, not first index.
Aggressive Cows IE-asked
Question they ask. n stalls on a line, place k cows, maximize the minimum distance between cows.
Example. Stalls [1,2,4,8,9], k=3. Best min-distance 3 (places 1,4,8 or 1,4,9).
Dry run — walk this before you code.
Say out loud. BS on distance + greedy place. Snippet.
Source. LC 7724048 snippet R2.
Clue → pattern. Maximize min distance → BS on answer + greedy place.
Why this. Chapter 25 maximize-minimum.
Brute. Try every distance. Time O(MAX · n). Space O(1).
Optimal. Sort stalls + O(n log RANGE). Time O(n log n + n log RANGE). Space O(1).
// feasible(d): place k cows with gap >= d
Snippet. Same family as power allocation on that loop’s R1.
Clone Graph; Next Palindromic Number IE-asked
Question they ask. Clone a graph (cycles, Node.neighbors); and next palindromic number after n (as digits).
Example. Graph 1—2—3—1 triangle: clone must not loop forever. Next palindrome after 129 → 131.
Dry run — walk this before you code.
Say out loud. Clone is DFS/BFS + map. Palindrome is digit mirror + increment. Two titles.
Source. LC 7280347 28 Aug 2025.
Clue → pattern. Clone: map old→new + DFS. Next palindrome: mirror left half, increment if needed.
Why this. Graph clone must map before walking neighbors (cycles). Palindrome: mirroring is O(digits); handle 9s carry.
Brute. No map infinite loop; increment n until palindrome O(n · digits). Time infinite / O(gap · D). Space O(V).
Optimal. O(V+E) clone; O(D) palindrome. Time O(V+E) / O(D). Space O(V) / O(D).
if (map.containsKey(u)) return map.get(u); Node n=new Node(u.val); map.put(u,n);
Two titles. Next palindrome is not next permutation.
Falling Path Sum variation; Rotten variation IE-asked
Question they ask. Falling path (down / diag-down, min or max sum) and a Rotten Oranges variation. Prince later wrote a right/diag matrix that is not identical — lock moves.
Example. 3×3 grid falling min: from each cell go down, down-left, down-right. Rotten: multi-source BFS minutes.
Dry run — walk this before you code.
Say out loud. DP on the DAG they drew. Rotten is BFS. Confirm directions.
Source. LC 6461439 28 Jan 2025 R2.
Clue → pattern. Grid down/diag max/min → DP. Rotten = multi-source BFS.
Why this. Prince’s later matrix (Job 3057703) is right/diag-up/diag-down to a fixed end — not identical. Speak the move set they drew.
Brute. All paths / rescan minutes. Time exp / O((mn)²). Space O(mn).
Optimal. DP O(mn); BFS O(mn). Time O(mn). Space O(mn).
// dp[c] = a[r][c] + min(dp3 from prev row)
Not identical to LC 931 unless they said so.
LL → height-balanced BST; First Missing Positive IE-asked
Question they ask. Convert a sorted linked list to a height-balanced BST; and first missing positive in an unsorted int array (O(n) time, O(1) extra if they insist).
Example. LL 1→2→3→4→5 → BST rooted at 3. Array [3,4,−1,1] first missing positive 2.
Dry run — walk this before you code.
Say out loud. Sorted LL → pick mid. FMP → cyclic sort. HashSet is the extra-space brute.
Source. Deepak Jul 2026.
Clue → pattern. Sorted LL to BST → mid split. First missing positive → cyclic sort 1..n.
Why this. Balanced BST from sorted sequence is always pick mid as root. Missing positive in O(1) extra: swap each a[i] to index a[i]−1 if in 1..n.
Brute. Insert sequentially (skew); HashSet positives. Time O(n log n) / O(n). Space O(n).
Optimal. Array mid O(n); cyclic sort O(n) time O(1) extra. Time O(n). Space O(n) array / O(1).
while (a[i]>=1 && a[i]<=n && a[a[i]-1]!=a[i]) swap;
Cyclic sort follow-up also appeared on Prem’s OA-as-R1 R2.
Dijkstra with PQ IE-asked
Question they ask. Non-negative weighted shortest path from src. They said Dijkstra with a priority queue.
Example. 0→1 weight 2, 0→2 weight 5, 1→2 weight 1. dist[2] should be 3, not 5.
Dry run — walk this before you code.
Say out loud. O((V+E) log V). Skip stale pairs. Non-negative weights only.
Source. Sachin ~May 2026 R2 with House Robber II.
Clue → pattern. Non-neg weighted shortest → PQ, skip stale.
Why this. BFS is wrong on weights. Decrease-key is not in Java PQ — push new (dist,node), ignore stale if d!=dist[u].
Brute. Bellman O(VE) or DFS all paths. Time O(VE). Space O(V).
Optimal. O((V+E) log V). Time O((V+E) log V). Space O(V).
if (d != dist[u]) continue; // stale
Cheapest-within-K-stops is not plain Dijkstra.
Keys and Rooms IE-asked
Question they ask. rooms[i] is a list of keys. Start in room 0. Can you visit every room?
Example. rooms = [[1],[2],[3],[]] → yes. [[1,3],[3,0,1],[2],[0]] → room 2 never reached? Keys in 2 are stuck — cannot enter 2. False.
Dry run — walk this before you code.
Say out loud. O(n + keys). If visited < n, false.
Source. LC 6491881 R2.
Clue → pattern. Rooms[i] = keys → DFS/BFS from 0, visited == n.
Why this. Reachability on a directed graph. Start at 0 only.
Brute. Perms of rooms. Time O(n!). Space O(n).
Optimal. O(n + keys). Time O(V+E). Space O(n).
dfs(0); return visCount==n;
Not Number of Islands (undirected grid).
Single element in sorted array; remove consecutive LL nodes sum 0 IE-asked
Question they ask. Two problems: the single non-duplicate in a sorted array of pairs; delete consecutive linked-list nodes that sum to 0.
Example. Array [1,1,2,3,3,4,4,8,8] unique 2. LL 1→2→−3→3→1 after removing 1+2+(−3)=0 becomes 3→1 (or further if they chain).
Dry run — walk this before you code.
Say out loud. Do not mix with first missing positive. Two separate codes.
Source. LC 6475219 R2.
Clue → pattern. All pairs but one unique, sorted → XOR or BS on even/odd index. LL: prefix map of sum → last node, delete the middle.
Why this. Unique element: in pairs, even index should equal next; BS the mismatch. Sum-0 consecutive: dummy + HashMap prefix→node; when prefix repeats, relink.
Brute. Linear XOR still O(n) — OK; they may want log n. LL: nested. Time O(n) / O(n²). Space O(1) / O(n).
Optimal. O(log n) BS; O(n) prefix map on LL. Time O(log n) / O(n). Space O(1) / O(n).
// if prefix seen: dummy-to-that-node.next = cur.next; wipe map range
Two problems. Do not mix with first missing positive.
Word Ladder; Count Beautiful Splits IE-asked
Question they ask. Word Ladder (shortest transformation length) and Count Beautiful Splits. Beauty definition was not fully specified — ask before coding splits.
Example. hit → cog with dict hot,dot,dog,lot,log,cog. Length 5. Beautiful splits: lock their predicate (e.g. both halves palindrome — that is a different LC; do not assume).
Dry run — walk this before you code.
Say out loud. Ladder is BFS on the word graph. Splits wait for their rule.
Source. LC 7035289 AUTA. TUF 06 Word Ladder II + Beautiful Splits.
Clue → pattern. Ladder = BFS words. Beautiful splits: title named — clarify the beauty definition; no extra LC id unless they linked one.
Why this. Ladder: 26-letter edges, remove from dict when queued. II asks all shortest paths — keep parents per layer.
Brute. All word sequences; all split indices. Time exp / O(n² · check). Space O(dict).
Optimal. BFS O(N · L · 26). Splits: only after they define beauty. Time O(N L 26). Space O(N).
for each pos 26 letters; if dict.remove(nxt) q.offer
Beautiful splits stay unnamed on mechanism if the body did not define it.
Stone Collision; reconstruct coins from ways-DP IE-asked
Question they ask. Stone collision (asteroid-like signed stones) and reconstruct a coin combination from a ways-DP they already wrote. Do not invent the coin recurrence.
Example. Stones [5,10,−5] → [5,10] if 10 > 5 and signs oppose? Standard asteroid: same as §1 asteroid card. Coins: walk their dp table backwards from dp[amount].
Dry run — walk this before you code.
Say out loud. Collision is the stack. Coins reconstruction follows their DP, not a guessed LC.
Source. LC 6606011 R2. Beyond those phrases in §5.B unnamed.
Clue → pattern. Collision = asteroid-like stack. Coins: they had a ways-DP and asked reconstruct — stay with their recurrence.
Why this. Do not invent the coin recurrence. Stone collision is the asteroid stack unless they defined a different rule.
Brute. Resimulate / enumerate coin sequences. Time O(n²) / exp. Space O(n).
Optimal. Stack / reconstruct from DP parents. Time O(n) / O(nT). Space O(n).
// unnamed coins: ask the transition; do not stamp LC 518 as exact
§5.B says do not guess beyond the phrases.
LFU Cache + extensible-cache LLD IE-asked
Question they ask. LFU cache: get/put O(1), evict least-frequent, tie → LRU inside that frequency. They also said extensible cache (Strategy for eviction). TUF 15 URL vs body may say LRU vs LFU — speak the conflict.
Example. cap=2. put 1, put 2, get 1 (freq 1 is now 2), put 3. Evict 2 (freq 1) not 1.
Dry run — walk this before you code.
Say out loud. LFU is not LRU. Say which they want. O(1) needs freq buckets.
Source. Reddit 1idtlan 22 Nov 2024.
Clue → pattern. LFU: HashMap key→node, freq→DLL, minFreq. Extensible: Strategy for eviction.
Why this. Need O(1) bump freq and evict min-freq LRU-inside-bucket. LRU is not enough.
Brute. Scan all keys for min freq. Time O(n). Space O(n).
Optimal. O(1) bucket maps. Time O(1). Space O(capacity).
// node.freq++; move to freq+1 list; if old list empty minFreq++
TUF 15 URL vs body LFU/LRU conflict — say it. Not Login Tracker.
Kadane water-level-change; in-place freq 1..N IE-asked
Question they ask. A Kadane-shaped “water level change” (ask the exact formula) and in-place frequencies of values in 1..N.
Example. Freq: a = [2,3,3,2,5], n=5. After encoding, counts of 1..5. Water: if they give deltas, max subarray of deltas is Kadane.
Dry run — walk this before you code.
Say out loud. Ask the water formula. 1..N freq without a second array is the encoding.
Source. Prabhash May 2025 R2.
Clue → pattern. Max water from a delta array → Kadane-like. Freq 1..N in-place → ±n encoding or swap.
Why this. Ask the water formula. 1..N freq without extra array: add n to a[a[i]%n] then decode counts as /n.
Brute. Prefix extras. Time O(n). Space O(n).
Optimal. O(n) time O(1) extra if they insisted in-place. Time O(n). Space O(1).
a[v] += n; count(i) = a[i]/n;
Described, not an LC stamp.
Cyclic sort similar to First Missing Positive; graph BFS/DFS IE-asked
Question they ask. Cyclic sort similar to first missing positive, then an unnamed graph BFS/DFS. OA-as-R1. Graph stays unnamed.
Example. Array [3,1,2,4] cyclic sort → [1,2,3,4]. Graph: do not invent the prompt.
Dry run — walk this before you code.
Say out loud. Cyclic sort in-place. Unnamed graph: stay unnamed.
Source. Prem LinkedIn OA-as-R1 ~Oct 2025.
Clue → pattern. Put values at index+1; then a graph traversal they did not name.
Why this. Cyclic sort family already in Deepak card. Unnamed graph stays unnamed.
Brute. HashSet. Time O(n). Space O(n).
Optimal. In-place swaps. Time O(n). Space O(1).
while (a[i] in 1..n && a[a[i]-1]!=a[i]) swap;
OA-as-R1. Their “R3” is not automatically your R3.
Array two-pointer; DP on triangular matrices IE-asked
Question they ask. An array two-pointer problem (unnamed exact) and DP on a triangular matrix (path sum). OA-as-R1. Titles unnamed beyond the phrases.
Example. Triangle [[2],[3,4],[6,5,7],[4,1,8,3]] min path 2+3+5+1=11. Two-pointer: e.g. sorted pair-sum — lock their array.
Dry run — walk this before you code.
Say out loud. Triangle is bottom-up DP. Two-pointer after they name the invariant.
Source. Vaishali ~Mar 2026 OA-as-R1.
Clue → pattern. Two-pointer on sorted / opposite ends. Triangle DP is path-sum from the bottom.
Why this. Triangle: dp[r][c] = val + min(below, below-right). Two-pointer: name the sort invariant.
Brute. Nested / all paths. Time O(n²) / exp. Space O(n²).
Optimal. O(n) two-pointer; O(n²) triangle or rolling. Time O(n) / O(n²). Space O(1) / O(n).
// triangle: for r=n-2..0 dp[c]=a[r][c]+min(dp[c],dp[c+1])
Titles unnamed beyond those phrases. OA-as-R1.
Remove K Digits; Split Array Largest Sum IE-asked
Question they ask. Split array into m non-empty contiguous parts; minimize the largest part-sum. (Remove K Digits is already §1 — this card is the split.) Phone OA-as-R1.
Example. [7,2,5,10,8], m=2. Split after 7+2+5=14 vs 10+8=18 → max 18; better 7+2=9 vs 5+10+8=23 worse; 7+2+5+10=24 vs 8. Best max is 18.
Dry run — walk this before you code.
Say out loud. Minimize-maximum: BS on the cap + greedy pack. DP O(n² m) is the brute.
Source. LC 6630775 Apr 2025 phone. OA-as-R1 flag on bible row.
Clue → pattern. Split array into m parts, minimize the max part → BS on answer.
Why this. Chapter 25 minimize-maximum. feasible(M) = can we cut into ≤ m pieces each sum ≤ M.
Brute. DP O(n² m). Time O(n² m). Space O(n m).
Optimal. BS + greedy pack O(n log SUM). Time O(n log SUM). Space O(1).
// same lo/hi as ship packages; feasible counts pieces
Phone OA-as-R1. Remove K Digits already in section A.
Validate Sum Tree; Minimum Knight Moves IE-asked
Question they ask. Validate a sum tree (every node equals left-subtree-sum + right-subtree-sum; leaves 0 or themselves — lock). Knight moves already in §1.
Example. Node 10 with 4 and 6, 4 has 1 and 3. 1+3=4, 4+6=10. Valid. Knight: see §1 knight card — one rehearsal.
Dry run — walk this before you code.
Say out loud. One postorder. Knight is BFS. Same loop may ask both.
Source. LC 6629948 Apr 2025.
Clue → pattern. Sum tree: node = left-sum+right-sum (or 0 leaf). Knight: BFS.
Why this. Postorder return subtree sum and a boolean. Knight card already in A.
Brute. Resum each subtree from scratch. Time O(n²). Space O(h).
Optimal. One postorder O(n). Time O(n). Space O(h).
int[] dfs: {sum, ok}; ok = leaf || (val==Lsum+Rsum && L.ok && R.ok)
Knight already linked in A — one rehearsal.
Delivery stations / parcels + classes + topological sort IE-asked
Question they ask. Delivery stations / parcels as classes, plus a topological order of jobs. Not LC 210 Course Schedule. Not LC 962. Sibling on that post is max-sum switching lists.
Example. Station A must finish before B, B before C. Classes: Parcel, Station, Graph. Order A,B,C.
Dry run — walk this before you code.
Say out loud. Types then Kahn. Do not open LC 210 as the answer id.
Source. LC 6369243. First-hand wording.
Clue → pattern. Entities + prereq order → OOD types then Kahn. Not LC 210.
Why this. They asked classes and a topo of jobs/stations. Design Station/Parcel/Graph, then indegree.
Brute. Manual order. Time —. Space —.
Optimal. Kahn on the job graph. Time O(V+E). Space O(V+E).
// class Station, Parcel; Graph.kahn()
NOT LC 962. NOT Course Schedule 210. Sibling problem on that post is max-sum switching LLs.
Validate sudoku (not Solver) IE-asked
Question they ask. Validate a filled or partial 9×9 sudoku (rows, cols, 3×3 boxes). They said validate, not solve.
Example. A board with two 5s in row 0 is invalid. Empty cells skip.
Dry run — walk this before you code.
Say out loud. Validation only. Do not start a solver.
Source. GFG sde-1-17 their later live.
Clue → pattern. Check 9 rows, 9 cols, 9 boxes → sets.
Why this. Validation is O(1) cells (81). Solver is backtracking — they said validate.
Brute. Same 81 checks. Time O(1). Space O(1).
Optimal. boolean[9] or HashSet per unit. Time O(1). Space O(1).
int b = (r/3)*3 + c/3; if seen row/col/box return false;
Pre-2024 dump also has Sudoku Solver — different, year-out.
Word Ladder family CAT→MEN IE-asked
Question they ask. Word Ladder with begin CAT and end MEN (year-out adjacent). Same BFS as Word Ladder I.
Example. CAT → CAT with one letter? Use their dictionary. Length is BFS layers.
Dry run — walk this before you code.
Say out loud. BFS. Do not DFS the dictionary first.
Source. GFG sde-1-17 R4/BR-adjacent.
Clue → pattern. Same BFS as Word Ladder. Begin/end given as CAT/MEN.
Why this. Unweighted transformations. Dictionary membership.
Brute. All sequences. Time exp. Space O(dict).
Optimal. BFS. Time O(N L 26). Space O(N).
// same as Word Ladder card
Year-out adjacent. Pattern reuse. Same BFS family as Word Ladder above.
Sum of a very long string IE-asked
Question they ask. Add two numbers given as strings (too long for long). Schoolbook add from the right. Not the 1226# encoded parser. Sibling: k-page visits.
Example. 999 + 1 → 1000.
Dry run — walk this before you code.
Say out loud. O(L) digit add. AUTA. k-page is the sibling IE problem.
Source. Nisarg AUTA R1 with k-page visit sequence.
Clue → pattern. Add digit-strings that do not fit in long → schoolbook add from the right, StringBuilder.
Why this. BigInteger is honest to mention; they often want digit loops. Do not parse as int. Encoded-frequency is a different parser.
Brute. Reverse to int arrays, add with carry. Time O(L). Space O(L).
Optimal. Two indices i,j; carry; sb.append. Time O(L). Space O(L). Linear vs trying all alignments.
int i = a.length()-1, j = b.length()-1, c = 0; StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || c > 0) {
int s = c + (i>=0 ? a.charAt(i--) - '0' : 0) + (j>=0 ? b.charAt(j--) - '0' : 0);
sb.append(s % 10); c = s / 10;
}
return sb.reverse().toString();
AUTA. Not encoded 1226#. k-page sequence is the sibling on the same IE.
k-page visit sequence IE-asked
Question they ask. A sequence of page ids; something about k consecutive visits (unique k-gram, count, last-k — title named, extra constraints unnamed). Clarify IO. Not loyal-customers-two-days.
Example. pages [1,2,1,3], k=2. Windows (1,2), (2,1), (1,3). If they want unique pages in the window, counts differ.
Dry run — walk this before you code.
Say out loud. Window of k + map. Lock the output before coding.
Source. Nisarg AUTA R1. Title named; extra constraints unnamed — lock IO.
Clue → pattern. Sequences of k page visits (unique consecutive k, count, or reconstruct — clarify) → sliding window of k + HashMap.
Why this. Exact prompt unnamed beyond the title. Typical: last-k pages or unique k-grams. Do not invent loyal-customers-two-days.
Brute. All windows of k, copy into a set. Independent windows. Time O(n·k). Space O(k).
Optimal. Deque + Map of counts in the window. Time O(n). Space O(k). Linear vs per-window copies.
Deque<Integer> w = new ArrayDeque<>(); Map<Integer,Integer> f = new HashMap<>();
for (int p : pages) {
w.addLast(p); f.merge(p, 1, Integer::sum);
if (w.size() > k) { int x = w.removeFirst(); if (f.merge(x,-1,Integer::sum)==0) f.remove(x); }
}
Title named, details unnamed. Clarify. Not loyal-customer logs paste.
Matrix max-path right/diag (Prince) IE-asked
Question they ask. Max path in a matrix moving right and diagonal (Prince Job 3057703). He wrote it is not identical to Falling Path. Lock which diagonals. Not Job 10454435.
Example. After they name dirs, e.g. right / right-up / right-down. Small grid [[1,2],[3,4]]: start left column, end right — ask start cells.
Dry run — walk this before you code.
Say out loud. Confirm moves, then DP. Do not call it Falling Path.
Source. Prince Job 3057703 R2. Not identical to Falling Path. Not Job 10454435. LC 424 was Prince R1.
Clue → pattern. Max path moving right and diagonal (lock which diags) → DP from the left.
Why this. Prince wrote it is not identical to Falling Path. Unique Paths is right/down count, not max. Do not reuse falling-path down/diag-down until they confirm dirs.
Brute. DFS all allowed moves. All paths. Exponential. Space O(mn) stack.
Optimal. dp[r][c] = a[r][c] + max of allowed predecessors. Time O(mn). Space O(mn) or O(m). DP vs all paths.
// after they name dirs, example right / right-up / right-down:
// dp[r][c] = a[r][c] + max(left, up-diag, down-diag)
// confirm before typing — this is not Falling Path
Job 3057703. Do not call it Falling Path. Do not stamp an LC id.
3. TUF popular-companies — named or described live, not already a §1/§2 card
Opened bodies in old experiences/takeyouforwardexperiences/. SDE II/L5 were not copied. 07 and 09 are the same write-up (Koko + Min Stack) counted once.
Maximum Size Subarray Sum Equals k IE-asked
Question they ask. Longest subarray with sum exactly k (negatives possible → prefix map). TUF 01 live R3 and R5.
Example. [1, −1, 5, −2, 3], k=3. One answer length 4 (1,−1,5,−2) or 2 (5,−2) — longest 4.
Dry run — walk this before you code.
Say out loud. Prefix + first-index map. Same as sum=0 with need prefix−k.
Source. TUF 01 live R3 and again R5.
Clue → pattern. Longest subarray with sum k → prefix + first-index map.
Why this. Same as sum=0 but need = prefix−k. Window only if all non-negative.
Brute. O(n²) pairs. Time O(n²). Space O(1).
Optimal. O(n) HashMap. Time O(n). Space O(n).
need=sum-k; if (map.containsKey(need)) ans=max(i-map.get(need));
They used a sliding-window wording on the second ask — still verify signs.
Decode Ways ii IE-asked
Question they ask. Decode Ways with ‘*’ wildcards (1–9 or 10–26 cases). Number of ways, not the 1226# frequency parser. No LC id on the TUF page.
Example. s = 1*. ‘1’ then ‘*’ as 1–9 → 9 ways for the pair 11–19 plus ‘1’ and ‘*’ as two digits… lock the classic table: 1* has 18 ways on LC 639 — if they did not link it, compute from their rules.
Dry run — walk this before you code.
Say out loud. O(n) DP with * cases. Recurse splits is exponential.
Source. TUF 02 live R2. No URL on the page.
Clue → pattern. Number of ways to decode, ‘*’ wildcard → DP with 9/15 cases.
Why this. dp[i] depends on one-digit and two-digit decodes. * is 1–9 or 10–26 cases. Not the encoded-frequency parser.
Brute. Recurse splits. Time exp. Space O(n).
Optimal. O(n) DP, careful * cases. Time O(n). Space O(1) rolling.
// dp[i] += ways1(s[i-1]) + ways2(s[i-2..i-1])
No LC id on the TUF page. Do not invent one. Different from 1226#24#(2).
House Robber (linear) IE-asked
Question they ask. House Robber on a line: max money, cannot rob adjacent houses. Be ready for circular.
Example. [2,7,9,3,1] → 2+9+1=12 or 7+3=10 or 7+1=8 → 12.
Dry run — walk this before you code.
Say out loud. O(n) two variables. Linear first.
Source. TUF 02 live R3.
Clue → pattern. Linear adjacent DP — then be ready for circular (bible).
Why this. Same robLine as section A.
Brute. 2^n. Time O(2^n). Space O(n).
Optimal. O(n) two vars. Time O(n). Space O(1).
cur = max(cur, prev + a[i]);
If they then say circular, split. Do not jump to III.
Longest Consecutive Sequence IE-asked
Question they ask. Longest consecutive sequence of integers (values, not indices). Unsorted array.
Example. [100,4,200,1,3,2] → 1,2,3,4 length 4.
Dry run — walk this before you code.
Say out loud. Expand from sequence starts. Not LIS, not a sliding window on indices.
Source. TUF 02 live R5.
Clue → pattern. Longest run of consecutive ints → HashSet, expand from starts.
Why this. Only start a run if x−1 is not in the set. Each number visited twice → O(n).
Brute. Sort unique, scan. Time O(n log n). Space O(n).
Optimal. HashSet O(n) average. Time O(n). Space O(n).
if (!set.contains(x-1)) { /* expand x, x+1, … */ }
This is values, not indices. Not a sliding window on the array order.
Reorganizing linked lists (1→5→2→4→3) IE-asked
Question they ask. Reorder a list to L0→Ln→L1→Ln−1→… Example they wrote 1→5→2→4→3. Ask if that is fold or odd-even split.
Example. 1→2→3→4→5 → 1→5→2→4→3.
Dry run — walk this before you code.
Say out loud. Mid + reverse + merge. Ask the exact target order. No invented LC id.
Source. TUF 04 live R3. No URL.
Clue → pattern. Reorder / odd-even / fold the list → slow-fast + reverse second half + merge.
Why this. Classic reorder: find mid, reverse tail, weave. The example 1→5→2→4→3 is fold (L0, Ln, L1, Ln−1, …).
Brute. Copy to array, rewrite. Time O(n). Space O(n).
Optimal. In-place O(n) time O(1) extra. Time O(n). Space O(1).
// mid; reverse(slow.next); weave head and second
Ask the exact target order. Do not invent an LC id.
Reschedule Meetings for Maximum Free Time I IE-asked
Question they ask. Meetings on a timeline; you may reschedule k meetings (classic: move k consecutive) to maximize a free gap. TUF linked the LC title. Meeting Rooms II is the other R2 problem on that IE.
Example. Gaps between meetings [1,2,3,1], k=1 move ⇒ you merge 2 consecutive gaps. Max 2+3=5.
Dry run — walk this before you code.
Say out loud. Gap array + sliding window. Not Job 10454435.
Source. TUF 06 live R2. Page linked LC title.
Clue → pattern. Gaps between meetings, you may move k meetings → max gap after sliding a window of gaps.
Why this. Moving k consecutive meetings merges k+1 gaps. Sliding window on the gap array.
Brute. Try every subset of k moves. Time exp. Space O(n).
Optimal. Gap array + window of k+1 gaps. Time O(n). Space O(n).
// gaps[i] = start[i]-end[i-1]; max sum of k+1 consecutive gaps
TUF linked a title. Still not Job 10454435. Meeting Rooms II is the other R2 problem on that IE.
Word Ladder II IE-asked
Question they ask. Word Ladder II: all shortest transformation sequences from begin to end.
Example. hit→cog, dict as usual. All shortest paths of length 5, not every path.
Dry run — walk this before you code.
Say out loud. BFS parents + DFS collect. Exponential output, polynomial graph.
Source. TUF 06 live R3.
Clue → pattern. All shortest transformation sequences → BFS layers + parent lists, then DFS collect.
Why this. I is shortest length; II is all paths of that length. Do not DFS the whole dict first.
Brute. DFS all sequences, keep min. Time exp. Space O(dict).
Optimal. BFS parents per layer; DFS back. Time O(N L 26 + paths). Space O(N).
// map word -> parents found at dist-1; then dfs from end
Word Ladder I only returns length. CAT→MEN GFG is I.
Most Stones Removed with Same Row or Column (similar) IE-asked
Question they ask. Stones on a 2D grid; remove a stone if it shares a row or column with another. Max removals. Similar-to. Connecting Cities is MST, not this.
Example. Stones (0,0),(0,2),(1,1),(2,0),(2,2). Connected via rows/cols into components. Answer n − components.
Dry run — walk this before you code.
Say out loud. n − connected components. Directed? No — share row/col is undirected.
Source. TUF 08 live R2.
Clue → pattern. Remove if share row/col → DSU on stones; leftover = components.
Why this. You can remove all but one stone per connected component. Answer = n − components.
Brute. DFS on n² pair graph. Time O(n²). Space O(n).
Optimal. DSU keyed by row and ~col. Time O(n α(n)). Space O(n).
// union(stone, rowKey); union(stone, colKey); comps = unique finds
Similar-to. Connecting Cities (TUF 10) is MST, not this.
Connecting Cities With Minimum Cost IE-asked
Question they ask. n cities, bidirectional connections with cost. Min cost to connect all, or −1. FTE TUF 10, not intern MST.
Example. 3 cities, edges 1-2 cost 5, 1-3 cost 6, 2-3 cost 1. MST cost 6 (2-3 and 1-2).
Dry run — walk this before you code.
Say out loud. MST. Disconnected → −1. Not stones-on-a-grid.
Source. TUF 10 live R2.
Clue → pattern. Connect all cities min cost → MST Kruskal/Prim.
Why this. If the graph is disconnected, −1. Kruskal: sort edges, DSU. Prim: PQ from 0.
Brute. All spanning trees. Time exp. Space O(n).
Optimal. O(E log E) Kruskal. Time O(E log E). Space O(n).
// sort edges by cost; if union add cost; if comps>1 return -1
Intern MST TUF journey is INTERN. FTE TUF 10 is this title.
First non-repeating character in a stream IE-asked
Question they ask. Stream of characters; after each append, the first character that has appeared exactly once so far (or #).
Example. stream a,a,b,c → after 1: a; after 2: # (a repeated); after 3: b; after 4: b.
Dry run — walk this before you code.
Say out loud. Queue + counts. O(n).
Source. TUF 11 live R3. Page linked a slightly different title.
Clue → pattern. Stream, first unique so far → queue + count[256].
Why this. Count hits; queue holds candidates in order; pop front while count>1.
Brute. Rescan the prefix each append. Time O(n²). Space O(1).
Optimal. O(n) queue + counts. Time O(n). Space O(Σ).
while (!q.isEmpty() && cnt[q.peek()]>1) q.poll();
OA First Unique Character is a static string — different slot, still OA-not-a-round.
Maximum Points on a Line IE-asked
Question they ask. Max number of points that lie on one straight line.
Example. Points (1,1),(2,2),(3,3),(0,1) → 3 on the diagonal.
Dry run — walk this before you code.
Say out loud. Slope map per origin. gcd the fraction. Vertical is a key.
Source. TUF 12 live R2.
Clue → pattern. Largest collinear set → for each origin, map slope → count.
Why this. Slope as reduced fraction (dx/g, dy/g) with sign normalize. Duplicates at the same point handled separately.
Brute. All triples collinear. Time O(n³). Space O(1).
Optimal. O(n²) slopes from each i. Time O(n²). Space O(n).
// key = dy/g + ":" + dx/g; skip i==j; max + duplicates
Vertical line dx=0 is a special key.
Sequentially Ordinal Rank Tracker IE-asked
Question they ask. Add a restaurant (name, rating); query the k-th best so far (higher rating, then name). TUF linked the LC title. Sibling: dynamic k-th LC 7850431.
Example. add (kimchi, 4), (cafe, 5), (sushi, 4). Query 1st → cafe. Query 2nd → kimchi vs sushi by name.
Dry run — walk this before you code.
Say out loud. Balanced tree or two heaps. Speak the comparator.
Source. TUF 13 live R2. Page linked LC title.
Clue → pattern. Add restaurant, query k-th best so far → two heaps or TreeMap policy.
Why this. Like a dynamic k-th with a compare (rating, name). Balance a “best” side and a “rest” side so peek is the current queried rank.
Brute. Sort the list each query. Time O(q n log n). Space O(n).
Optimal. Two heaps / TreeSet of pairs. Time O(log n). Space O(n).
// TreeSet with (rating desc, name asc); keep iterator / two sets
Named title on TUF. Not a 10454435 lock. Dynamic k-th LC 7850431 is the bible sibling.
Cousins in Binary Tree II IE-asked
Question they ask. Cousins II: replace each node’s value with the sum of its cousins (same depth, different parent). Cousins I is only a boolean — ask which.
Example. Perfect small tree: root 1, left 2 right 3, 2 has 4, 3 has 5. Level-2 sum 9. Node 4’s cousins = 5, so 4 becomes 5 (or levelSum − siblings).
Dry run — walk this before you code.
Say out loud. BFS level sums minus sibling group. O(n).
Source. TUF 13 live R2. Linked LC title.
Clue → pattern. Replace each node with cousin-sum (same depth, different parent) → two BFS or one BFS with level sums.
Why this. Level sum minus the two children of your parent is the cousin sum. Need parent grouping.
Brute. For each node scan the level. Time O(n²). Space O(n).
Optimal. BFS store levelSum; second pass set val = levelSum − siblingCluster. Time O(n). Space O(n).
// first BFS depths/sums; second assign
Cousins I is a boolean. II is the value rewrite. Ask which.
Find the Smallest Divisor Given a Threshold IE-asked
Question they ask. Smallest divisor d such that sum of ceil(a[i]/d) ≤ threshold. Not “smallest d that divides every a[i].”
Example. a=[1,2,5,9], threshold=6. d=5 → ceil 1+1+1+2=5 ≤6. d=4 → 1+1+2+3=7>6. Answer 5.
Dry run — walk this before you code.
Say out loud. BS on d + ceil sum. O(n log MAX).
Source. TUF 13 live R3. Linked LC title.
Clue → pattern. Min divisor so sum(ceil(a[i]/d)) ≤ threshold → BS on answer.
Why this. Larger d shrinks the sum — monotone. Same family as Koko.
Brute. Try d=1..max(a). Time O(MAX · n). Space O(1).
Optimal. O(n log MAX). Time O(n log MAX). Space O(1).
feasible(d): sum (a[i]+d-1)/d <= threshold
Not “smallest number that divides all.”
Maximum Level Sum of a Binary Tree IE-asked
Question they ask. 1-based level with maximum node-sum in a binary tree. Tie: smallest level (classic) — confirm.
Example. Root 1, left 7 right 0, 7 has 7 and −8. Level1=1, level2=7, level3=−1. Max is 7 at level 2.
Dry run — walk this before you code.
Say out loud. BFS. O(n). Tie-break: ask.
Source. TUF 13 live R3.
Clue → pattern. BFS level sums, track max and the 1-based level.
Why this. Queue size is the level. long sums.
Brute. DFS with map level→sum. Time O(n). Space O(n).
Optimal. BFS O(n). Time O(n). Space O(w).
for (sz=q.size(); sz>0; sz--) { sum += poll.val; offer kids; }
Max width uses indices, not sums — TUF 11.
LCA of a Binary Tree II (org-chart DS, nodes may be missing) IE-asked
Question they ask. LCA when p or q might not be in the tree (return null if missing). They also wanted an org-chart DS with O(log n) queries. TUF 21 is LCA III (parent pointers) — do not mix.
Example. Tree 3/5,1; p=5 q=4 but 4 not in tree → null. If both exist, normal LCA.
Dry run — walk this before you code.
Say out loud. Confirm both found. Lifting if they asked log n queries.
Source. TUF 14 live R2. Also bible org-chart DS O(log n) aim.
Clue → pattern. LCA when p or q might not exist → search must confirm both found. Org-chart O(log n) is parent pointers / binary lifting / first+last Euler.
Why this. Classic LCA assumes both exist. II returns null if one is missing — track found flags. Hierarchy DS they wanted O(log n): store depth + jump table or parent chain + HashSet.
Brute. Root-to-node paths lists, last common. Time O(n). Space O(n).
Optimal. One DFS with found flags; or lifting O(log n) after O(n log n) preprocess. Time O(n) or O(log n) query. Space O(n) or O(n log n).
// lca(u) returns node; boolean[] foundP foundQ; if !(foundP&&foundQ) return null
TUF 21 is LCA III (parent pointers on nodes). Do not mix. Design-a-DS wording is TUF 14.
LRU linked, body said LFU IE-asked
Question they ask. The TUF link said LRU; the body said LFU. Say the conflict. Implement whichever they speak. Not Login Tracker.
Example. If they say LRU: cap=2, put 1, put 2, get 1, put 3 → evict 2. If LFU: see the LFU card.
Dry run — walk this before you code.
Say out loud. Name the conflict. Login Tracker is unverified and not this.
Source. TUF 15 live R3. URL vs body conflict.
Clue → pattern. Say the conflict. Implement the one they speak. LRU = HashMap+DLL. LFU = freq buckets.
Why this. If the interviewer says LFU, min-freq + LRU inside that freq. If they say LRU, do not add freq.
Brute. Scan keys. Time O(n). Space O(n).
Optimal. O(1) the structure they named. Time O(1). Space O(cap).
// ask: LRU or LFU? write that one
Write the conflict out loud. Not Login Tracker.
Minimum Days to Make M Bouquets IE-asked
Question they ask. bloomDay[i] is the day flower i blooms. You need m bouquets of k adjacent flowers. Min day, or −1.
Example. bloom [1,10,3,10,2], m=3, k=1. After day 3, flowers 0,2,4 are bloomed — three singles. Answer 3.
Dry run — walk this before you code.
Say out loud. BS on day + greedy adjacent count. O(n log MAX).
Source. TUF 16 live R2.
Clue → pattern. Min day so you can pick m adjacent-k groups → BS on day + greedy count.
Why this. After day D, bloomed[i]=true if a[i]≤D. Count adjacent groups of k. Larger D helps.
Brute. Try every day. Time O(MAX · n). Space O(1).
Optimal. O(n log MAX). Time O(n log MAX). Space O(1).
// feasible(D): adjacent bloom count / k >= m
Same monotone family as Koko. Not a heap of flowers.
Distinct Subsequences IE-asked
Question they ask. Number of times t appears as a subsequence of s (not substring).
Example. s=rabbbit, t=rabbit → 3 ways (the three b’s choose two).
Dry run — walk this before you code.
Say out loud. DP subsequence counts. Not distinct elements of the array.
Source. TUF 16 live R2.
Clue → pattern. Ways t occurs as subsequence of s → DP.
Why this. dp[i][j] = ways to form t[:j] from s[:i]. If s[i-1]==t[j-1] add dp[i-1][j-1].
Brute. Recurse all subsequences. Time O(2^n). Space O(n).
Optimal. O(n m) DP, rolling 1D backward. Time O(n m). Space O(m).
if (s[i]==t[j]) dp[j] += dp[j-1]; iterate j from m..1
Not LIS. Not “distinct count of the array.”
Evaluate Reverse Polish Notation IE-asked
Question they ask. Evaluate Reverse Polish Notation. Tokens are numbers or + − * /.
Example. [2, 1, +, 3, *] → (2+1)*3 = 9.
Dry run — walk this before you code.
Say out loud. Stack of longs. O(n). The stack is the algorithm, not a ‘brute vs opt’ story.
Source. TUF 17 live R2.
Clue → pattern. Postfix tokens → stack of longs.
Why this. Number push; operator pop two (watch order: a op b with b popped first).
Brute. Not really — the stack is the definition. Time O(n). Space O(n).
Optimal. ArrayDeque. Time O(n). Space O(n).
if (op) { int b=st.pop(), a=st.pop(); st.push(a?b); } else st.push(parse)
Infix calculator is a different stack (signs/parens).
Strong Password Checker IE-asked
Question they ask. Min changes so the password is strong: length in [6,20], has lower/upper/digit, no three identical in a row. Hard casework. Not a random edit-distance DP.
Example. aaa → need length and types and break the run. Speak cases: len<6, len in 6..20, len>20.
Dry run — walk this before you code.
Say out loud. Case analysis, not generic DP. TUF named it — still not 10454435.
Source. TUF 17 live R2. Linked LC title.
Clue → pattern. Min changes to satisfy length / classes / 3-run → greedy counts, not a generic DP.
Why this. This problem is a special case analysis (missing types, aaa runs, length <6 / >20). Speak the cases; do not invent a random edit-distance.
Brute. BFS on strings. Time huge. Space huge.
Optimal. O(n) count + casework. Time O(n). Space O(1).
// count missing lower/upper/digit; count run lengths %3
Hard. Say the cases out loud. Not Job 10454435 just because TUF named it.
Closest Divisors (kind of like) IE-asked
Question they ask. Kind-of-like closest divisors: pair of factors of n or n+1 with smallest |a−b|. Same R3 had unnamed topo — do not stamp extra ids.
Example. n=8. Factors of 8: (1,8),(2,4). Factors of 9: (1,9),(3,3). Closest is (3,3).
Dry run — walk this before you code.
Say out loud. Walk from sqrt. Use long if n is big.
Source. TUF 17 live R3. Similar-to.
Clue → pattern. Pair of factors of n or n+1 closest → walk i from sqrt down.
Why this. For x in {n, n+1} find i|x minimizing |x/i − i|. Start i=sqrt(x).
Brute. All i=1..x. Time O(n). Space O(1).
Optimal. O(sqrt n). Time O(√n). Space O(1).
for (int i=(int)Math.sqrt(x); i>=1; i--) if (x%i==0) return {i,x/i};
Kind-of-like. Same R3 also had unnamed topo. Do not stamp an extra LC id.
Assign Cookies IE-asked
Question they ask. Assign cookies: g[i] greed, s[j] size, one cookie per child if s[j]≥g[i]. Maximize content children. Follow-up may allow stacking cookies — that is a new problem.
Example. g=[1,2,3] s=[1,1] → 1 child.
Dry run — walk this before you code.
Say out loud. Sort + greedy. Speak the follow-up as a new model.
Source. TUF 18 live R2. Follow-up: one child can take multiple cookies.
Clue → pattern. Greedy: sort both, smallest-greed child first. Follow-up changes the model — ask if cookies stack.
Why this. Classic: one cookie per child, g[i]≤s[j]. Follow-up “multiple cookies” is a different packing (can you sum cookies to meet g[i]) — knapsack-ish or greedy remaining.
Brute. Try assignments. Time exp. Space O(n).
Optimal. Sort + two pointer O(n log n). Time O(n log n). Space O(1).
Arrays.sort(g); Arrays.sort(s); while i=g[i]) i++; j++;
Speak the follow-up as a new problem. Do not silently keep one-cookie.
Daily Temperatures IE-asked
Question they ask. Daily Temperatures: for each day, days until a warmer temp (0 if none). Same stack as NGE / Naina similar-to.
Example. [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].
Dry run — walk this before you code.
Say out loud. Monotonic stack O(n). Nested scan is O(n²).
Source. TUF 18 live R2. Named title. Bible Naina was similar-to.
Clue → pattern. NGE distances — section A stack.
Why this. Same monotonic stack as NGE.
Brute. O(n²). Time O(n²). Space O(1).
Optimal. O(n). Time O(n). Space O(n).
ans[i] = j - i;
Named on TUF 18; similar on Naina. One template.
Bottom View of Binary Tree IE-asked
Question they ask. Bottom view of a binary tree: leftmost to rightmost horizontal column, the lowest node in that column.
Example. Root 20, left 8 right 22, 8 has 5 and 3, 3 has 10, 22 has 25. Bottom view 5,10,3,22,25 (classic GFG drawing — use theirs).
Dry run — walk this before you code.
Say out loud. BFS + column map. Last write wins.
Source. TUF 18 live R3.
Clue → pattern. Horizontal column, last node in vertical BFS → TreeMap col→val.
Why this. BFS so a lower node overwrites the same column. DFS must compare depth.
Brute. All nodes, keep max depth per col. Time O(n log n) if tree map. Space O(n).
Optimal. BFS + TreeMap or HashMap+min/max col. Time O(n log W). Space O(n).
q.offer({node,0}); map.put(col, node.val); // BFS overwrites
Top view keeps the first, not the last. Vertical order keeps the list.
Apply Operations to an Array IE-asked
Question they ask. If a[i]==a[i+1] and nonzero, a[i]*=2, a[i+1]=0; then shift zeros to the end.
Example. [1,2,2,1,1,0] → after ops [1,4,0,2,0,0] then compact [1,4,2,0,0,0].
Dry run — walk this before you code.
Say out loud. Two passes in place. Do not invent a fancy DS.
Source. TUF 18 live R3. Linked LC title.
Clue → pattern. If a[i]==a[i+1] double and zero the next; then compact zeros — one/two passes.
Why this. Simulation is the problem. Second pass move non-zeros forward.
Brute. ArrayList rebuild. Time O(n). Space O(n).
Optimal. In-place O(n). Time O(n). Space O(1).
if (a[i]==a[i+1] && a[i]!=0) { a[i]*=2; a[i+1]=0; } then partition zeros
Easy-medium. Still say TC. Do not invent a heap.
Largest Submatrix With Rearrangements IE-asked
Question they ask. You may rearrange columns. Largest area submatrix of all 1s. Not Maximal Rectangle (that forbids reorder).
Example. After sorting heights in a row, height 3,2,1 → areas 3*1, 2*2, 1*3 → best 4.
Dry run — walk this before you code.
Say out loud. Heights + sort per row. O(m n log n). Not the stack histogram without permutation.
Source. TUF 18 live R4 HM. Linked LC title.
Clue → pattern. You may reorder columns; largest 1s-area → height histogram per row, sort heights, greedy width.
Why this. Unlike Maximal Rectangle, columns can be permuted. For each row, treat heights, sort descending, area = height[j]*(j+1).
Brute. All permutations of columns. Time O(n! · mn). Space O(mn).
Optimal. O(m n log n) sort per row. Time O(m n log n). Space O(n).
// update height; copy sort desc; ans=max(h[j]*(j+1))
Not the same as Maximal Rectangle (no reorder).
Digit Count in Range IE-asked
Question they ask. Count how many times digit d appears in all numbers in [a,b].
Example. d=1, [1,13]: 1,10,11,12,13 → 1 six times (11 counts twice). If b is 1e12, brute dies.
Dry run — walk this before you code.
Say out loud. Bounds decide brute vs digit DP. Do not start DP on 1e5.
Source. TUF 19 live R3.
Clue → pattern. Count digit d in [a,b] → digit DP or count(0..b)−count(0..a−1).
Why this. Digit DP on positions, tight flag, leading zeros. Brute loop is fine if b is small — ask the bounds.
Brute. For each x in [a,b] count digits. Time O((b−a) · D). Space O(1).
Optimal. Digit DP O(D · 2 · 2 · 10). Time O(D). Space O(D).
// count(n,d) digit-DP; return count(b)-count(a-1)
If they gave tiny b, brute is honest. Do not flex digit-DP if n≤1e6 and they want simple.
Majority Element I IE-asked
Question they ask. Element that appears more than n/2 times. Guaranteed to exist on I.
Example. [2,2,1,1,1,2,2] → 2.
Dry run — walk this before you code.
Say out loud. Moore O(1) space. Majority II is different.
Source. TUF 20 live R1 (this IE’s R1 was live DSA, not OA).
Clue → pattern. Element with count > n/2 → Boyer-Moore or HashMap.
Why this. Moore: candidate + count; verify. Sorting also works n log n.
Brute. HashMap all counts. Time O(n). Space O(n).
Optimal. Boyer-Moore O(n) O(1). Time O(n). Space O(1).
if (x==cand) c++; else if (--c==0) cand=x;
Majority II is n/3 — different.
Frog Jump IE-asked
Question they ask. Frog on stones at positions. First jump is 1. From a jump of k, next is k−1, k, or k+1. Can it reach the last stone?
Example. stones [0,1,3,5,6,8,12,17] → true (classic). [0,1,2,3,4,8,9,11] → false.
Dry run — walk this before you code.
Say out loud. DP/BFS on (stone, k). Need a position set.
Source. TUF 20 live R1. Also pre-2024 dump title.
Clue → pattern. Can the frog reach last stone with jump k−1,k,k+1 → DP/BFS on (index,k).
Why this. State is (stone, lastJump). Set of stone positions for O(1) hit.
Brute. Recurse jumps. Time exp. Space O(n²).
Optimal. DP set of possible k per stone O(n²). Time O(n²). Space O(n²).
if (stones.contains(pos+step)) dfs(pos+step, step)
GFG dump Frog Jump is year-out too. Same pattern.
Maximum Consecutive Good Numbers IE-asked
Question they ask. Maximum consecutive good numbers. TUF linked a title; body may be thin. Ask what “good” means before you code.
Example. If good is a[i] % 2 == 0: [1,2,4,3,6,8,5] longest even run is 2,4 length 2 or 6,8 length 2.
Dry run — walk this before you code.
Say out loud. Lock “good.” Then linear scan or window. No guessed id.
Source. TUF 20 live R2.
Clue → pattern. Ask their definition of good; then longest run — window or simple scan.
Why this. If good is a predicate on a[i], longest consecutive trues is a linear scan. If good depends on a window, it is a sliding window.
Brute. All L,R test. Time O(n²). Space O(1).
Optimal. O(n) once the predicate is monotone or per-element. Time O(n). Space O(1).
// ask: is good(a[i]) independent? then scan runs
TUF linked a title; body may still be thin. Ask. No extra LC id.
Find Peak Element IE-asked
Question they ask. A peak is a[i] > neighbors (ends: one neighbor). Array is unsorted. O(log n) expected.
Example. [1,2,3,1] peak index 2 (value 3). [1,2,1,3,5,6,4] 1 or 5 both peaks — any peak.
Dry run — walk this before you code.
Say out loud. Binary search the slope. Return any peak.
Source. TUF 20 live R2.
Clue → pattern. a[i]>neighbors, unsorted, O(log n) → BS the slope.
Why this. If mid < mid+1 there is a peak on the right. Unimodal argument on the array they guaranteed.
Brute. Linear scan. Time O(n). Space O(1).
Optimal. O(log n) BS. Time O(log n). Space O(1).
if (a[mid] < a[mid+1]) lo=mid+1; else hi=mid;
2D peak is a different BS. Rotated min is a different BS.
Count the Number of K-Big Indices IE-asked
Question they ask. Index i is k-big if ≥ k elements to the left are < a[i] and ≥ k to the right are < a[i]. Count them. Intern OA TUF Q47 is INTERN; FTE TUF 21 is live R2.
Example. a=[2,3,6,5,2,3], k=2? Walk i=2 (6): left 2,3 both <6 (2 elements); right 5,2,3 → two <6. If k=2, i=2 counts. Confirm on their array.
Dry run — walk this before you code.
Say out loud. Count left-smaller and right-smaller. BIT after you name the brute.
Source. TUF 21 live R2. Intern OA also named this family.
Clue → pattern. Index i is k-big if k elements to the left and to the right are < a[i] — Fenwick/merge or sorted structures.
Why this. Need left-smaller count and right-smaller count both ≥ k. Fenwick on compressed values, left-to-right then right-to-left.
Brute. For each i scan left and right. Time O(n²). Space O(1).
Optimal. O(n log n) BIT. Time O(n log n). Space O(n).
// fenwick add ranks; left[i]=query(rank[i]-1)
Intern OA TUF Q47 is INTERN. FTE TUF 21 is live R2.
Search in 2D Matrix II IE-asked
Question they ask. Matrix with each row and each column sorted. Search a target. Not 2D Matrix I (flatten + one BS).
Example. [[1,4,7],[2,5,8],[3,6,9]], target 8. Start at 7 (top-right): 8>7 go down to 8. Found.
Dry run — walk this before you code.
Say out loud. Staircase O(m+n). Do not flatten.
Source. TUF 21 live R2.
Clue → pattern. Rows and columns sorted → staircase from top-right O(m+n).
Why this. If cur > target, go left; if cur < target, go down. Not a single BS on a flattened array (that is Matrix I).
Brute. Scan all / BS each row. Time O(mn) / O(m log n). Space O(1).
Optimal. O(m+n). Time O(m+n). Space O(1).
int r=0,c=n-1; while (r=0) { if (a[r][c]==t) return; if (a[r][c]>t) c--; else r++; }
Max-1s row uses the same walk on a 0/1 matrix.
Maximum Alternating Subarray Sum (variation) IE-asked
Question they ask. Maximum alternating subarray sum (variation). Ask if contiguous (subarray) vs subsequence. Sign pattern + − + or they define it.
Example. If subarray +−+: [3, −1, 4] may be 3−(−1)+4 if they flip actual signs, or 3 + (−(−1)) + 4 — lock the formula. Simpler: [1,2,3] alt 1−2+3=2 vs 2−3=−1 vs 3; DP two states.
Dry run — walk this before you code.
Say out loud. Two-state DP after they define the signs. Ask contiguous.
Source. TUF 21 live R3. Variation.
Clue → pattern. Alternating + − + pattern → DP two states (end-plus, end-minus).
Why this. Kadane-like but the sign flips. Variation: ask if subarray must be contiguous (yes if they said subarray).
Brute. All L,R compute alt. Time O(n²). Space O(1).
Optimal. O(n) two states. Time O(n). Space O(1).
plus = a[i]; minus = plus - /*prev*/; track max
Variation. Subsequence alternating is a different LC family — ask contiguous.
Walls and Gates (variation) IE-asked
Question they ask. Walls and Gates variation: 0 = gate, INF = empty room, −1 = wall. Fill each room with dist to nearest gate. 4-dir — ask.
Example. One gate at (0,0), empty at (0,1) and (1,0). Those become 1. Multi-source like rotten oranges.
Dry run — walk this before you code.
Say out loud. Multi-source BFS. O(mn).
Source. TUF 21 live R3. Variation.
Clue → pattern. Multi-source BFS from all gates (0s) into empty rooms.
Why this. Same shape as rotten oranges. Do not DFS from each room (that is n times BFS).
Brute. BFS from every INF cell. Time O((mn)²). Space O(mn).
Optimal. Queue all 0s first. Time O(mn). Space O(mn).
// offer all gates; dist++; skip walls -1
Variation — ask INF sentinel and 4-dir.
LCA of a Binary Tree III IE-asked
Question they ask. LCA III: TreeNode has a parent pointer. No root given. Not II (missing nodes). Not org-chart lifting unless they asked preprocess.
Example. p and q in a tree, climb. Like intersecting linked lists.
Dry run — walk this before you code.
Say out loud. Parent pointers → list-intersection. O(h).
Source. TUF 21 live R4.
Clue → pattern. Nodes have parent pointers → two pointers like intersecting lists, or HashSet of parents.
Why this. Walk p to root storing set; walk q until hit. Or equalize depths then climb together. No tree root required.
Brute. All ancestors of p, scan q. Time O(h). Space O(h).
Optimal. O(h) two pointers. Time O(h). Space O(1) if you cycle like list intersection.
// like intersection of two linked lists via parent
Not II (maybe missing nodes, no parent field). Not org-chart O(log n) DS unless they asked preprocess.
Print all nodes at distance K in BT IE-asked
Question they ask. Print all nodes at distance K from a target in a binary tree. Same family as §1 Distance K / LC 7406809. If they ban a parent map, parent is a DFS argument.
Example. Use the §1 drawing: target 5, k=2 → [1,4].
Dry run — walk this before you code.
Say out loud. BFS from target after you can walk up. See Distance K.
Source. TUF 21 live R4. Same family as Distance K.
Clue → pattern. Use the no-parent-map card in section A / ch.05.
Why this. Same problem family as LC 7406809 / 7623949.
Brute. Parent map + BFS (works if they allow the map). Time O(n). Space O(n).
Optimal. Parent as DFS arg + BFS. Time O(n). Space O(n).
// see 05-dsa.html#distance-k-no-parent-map
If they ban the map, do not write Map<TreeNode,TreeNode>.
Maximum Number of Weeks for Which You Can Work (variation) IE-asked
Question they ask. milestones[i] weeks left on project i; cannot work the same project two weeks in a row. Max weeks you can work. Variation. SDE-unspecified file 201 — not a clean UTA loop, not 10454435.
Example. Classic: [1,2,3] → if max ≤ rest+1 you finish all 6; else 2*rest+1. Confirm their rule.
Dry run — walk this before you code.
Say out loud. Greedy on the max project. Lock the rule. Not 10454435.
Source. TUF 201 unspecified-SDE live R2. Variation.
Clue → pattern. Cannot work the same project two weeks in a row; milestones[] → greedy on max.
Why this. If max ≤ 1+rest you can finish all; else you are stuck after 2*rest+1. Variation: ask their exact rule.
Brute. Simulate a max-heap week by week. Time O(W log n). Space O(n).
Optimal. O(n) closed form on the classic statement. Time O(n). Space O(1).
long rest=sum-max; return max<=rest+1 ? sum : 2*rest+1;
SDE unspecified file 201, not a clean SDE I UTA loop. Variation. Not 10454435.
Replace Non-Coprime Numbers in Array (variation) IE-asked
Question they ask. While two adjacent numbers have gcd > 1, replace them with their LCM. Variation. Use long. Unspecified-SDE file.
Example. [6, 4, 3, 2, 7, 6, 2] classic: 6,4 → lcm 12, then 12,3 → 12, etc. Walk a stack.
Dry run — walk this before you code.
Say out loud. Stack + gcd/lcm while. Long for lcm.
Source. TUF 201 live R2. Variation.
Clue → pattern. While adjacent gcd>1 replace with lcm → stack, gcd/lcm.
Why this. New value may still collide with the new top — while-loop on the stack, not one pass without a stack.
Brute. Rescan the array after each replace. Time O(n² log A). Space O(n).
Optimal. Stack O(n log A). Time O(n log A). Space O(n).
while (!st.isEmpty() && gcd(st.peek(),x)>1) x=lcm(st.pop(),x); st.push(x);
Variation. Use long for lcm. Unspecified-SDE file.
Insertion Sort List (variation + follow-ups) IE-asked
Question they ask. Insertion-sort a linked list. Follow-up: they want faster → merge-sort the list O(n log n), O(1) extra if careful.
Example. 4→2→1→3 → 1→2→3→4.
Dry run — walk this before you code.
Say out loud. Insertion is O(n²). Upgrade to merge sort if they ask.
Source. TUF 201 live R3.
Clue → pattern. Sort a linked list by insertion → dummy + walk prev.
Why this. O(n²) is the algorithm’s cost. Follow-ups: merge sort list O(n log n).
Brute. Array sort + rebuild. Time O(n log n). Space O(n).
Optimal. True insertion O(n²) pointers; mention merge sort if they want faster. Time O(n²) or O(n log n). Space O(1).
// dummy; for each cur find insert point in the sorted prefix
Follow-ups were written — be ready to upgrade to merge sort list.
Factor Combinations (variation) IE-asked
Question they ask. All factor combinations of n (usually excluding n itself as a single factor). Backtracking. BR on unspecified-SDE — not UTA-default. Variation.
Example. n=8 → [2,2,2], [2,4], [4,2] if order matters — usually keep non-decreasing: [2,2,2],[2,4].
Dry run — walk this before you code.
Say out loud. Backtrack with a start index. Ask whether [n] is allowed.
Source. TUF 201 live R4 BR. Variation.
Clue → pattern. All ways to factor n (excluding n itself usually) → backtracking from last factor.
Why this. Start i from 2 or from last to keep non-decreasing. n≤ a typical backtrack bound.
Brute. Same tree, sloppier duplicates. Time depends on n. Space O(log n).
Optimal. Backtrack i=start..sqrt, recurse n/i. Time output-sensitive. Space O(log n).
for (int i=start; i*i<=n; i++) if (n%i==0) { path.add(i); dfs(n/i,i); path.remove }
BR on an unspecified-SDE write-up. Not UTA-default. Variation.
Basic tree operations / balanced trees (RB, AVL) Standard CS
Question they ask. Conceptual: BST operations, AVL vs Red-Black. Not a LeetCode. Do not claim you implemented RB at Ylogx. Java TreeMap is RB.
Example. Insert 1,2,3 into a BST without rotate → a stick, O(n) search. AVL rotates to a balanced 2-root.
Dry run — walk this before you code.
Say out loud. Speak rotations and invariants. Unbalanced BST is the O(n) warning.
Source. TUF 04 live R2. Conceptual.
Clue → pattern. They asked operations / RB / AVL — speak rotations and invariants, not a fake coding prompt.
Why this. AVL: |bf|≤1, rotate LL/LR/RR/RL. RB: 5 properties, recolor/rotate. Java TreeMap is a RB tree — O(log n) ceiling/floor.
Brute. Unbalanced BST worst O(n). Time O(n). Space O(n).
Optimal. AVL/RB O(log n) guaranteed. Time O(log n). Space O(n).
// TreeMap if they want a balanced BST without writing rotations
Conceptual. Do not invent a LeetCode. Do not claim you implemented RB at Ylogx.
Merge two already-sorted integer streams IE-asked
Question they ask. Merge two already-sorted integer streams (possibly unbounded). Same idea as merge two sorted lists. Not merge k.
Example. A: 1,3,5… B: 2,4. Output 1,2,3,4,5…
Dry run — walk this before you code.
Say out loud. Two pointers / two heads. O(n+m). Do not sort.
Source. TUF 14 described live R3.
Clue → pattern. Two sorted streams → two pointers / heap of 2 heads. Same as merge two sorted lists.
Why this. Always take the smaller current head. If they are true streams (unbounded), you cannot load all.
Brute. Buffer both, concat sort. Time O(n log n). Space O(n).
Optimal. O(n+m) two pointer. Time O(n+m). Space O(1) extra.
// while both: emit min(a,b) advance that iterator
Described, no title. Not merge k (heap of k).
All pairs with given sum IE-asked
Question they ask. All pairs that sum to a target. Sorted → two pointer (skip duplicates). Unsorted → HashMap. Described, no LC id.
Example. [2,7,11,15], target 9 → (2,7). If duplicates [1,1,1,2] target 3, ask unique pairs vs all index pairs.
Dry run — walk this before you code.
Say out loud. Lock unique vs all. Then map or two pointer.
Source. TUF 15 described live R2.
Clue → pattern. Pair sum — HashMap or two-pointer if sorted. They want all pairs: skip duplicates.
Why this. See chapter 25 pair-sum. For all pairs, after a hit move both pointers / walk equal-run counts.
Brute. O(n²). Time O(n²). Space O(1).
Optimal. O(n) or O(n log n). Time O(n). Space O(n).
// map value→indices; watch i!=j and unique pairs
Described. No LC id.
BST + float target: k closest values IE-asked
Question they ask. BST (or sorted inorder) and a float target; return k closest values. Not Top K frequent.
Example. BST inorder 1,2,3,4,5, target 3.2, k=2 → 3 and 4 (or 3 and 2 — |3.2−2|=1.2 > |3.2−4|=0.8 so 3,4).
Dry run — walk this before you code.
Say out loud. Closest on a sorted line. Inorder then two pointers is the clear story.
Source. TUF 15 described live R2.
Clue → pattern. Inorder is sorted; two pointers on the inorder array, or two stacks (pred/succ).
Why this. k closest on a sorted line: expand from the insertion point. Heap of size k also works O(n log k).
Brute. All values, sort by |x−t|. Time O(n log n). Space O(n).
Optimal. Inorder + two pointer O(n), or O(k + log n) pred/succ. Time O(n). Space O(n).
// inorder list; l,r around target; pick closer k times
Described. Not Top K frequent.
Maze: shortest path collect all keys IE-asked
Question they ask. Grid maze: walls, doors A–F, keys a–f. Shortest path to collect all keys. Not Walls and Gates.
Example. Start @, one key a, door A, end when mask has all keys. K ≤ 10 typically.
Dry run — walk this before you code.
Say out loud. BFS (r,c,mask). O(mn 2^K). Keys must be few.
Source. TUF 15 described live R3.
Clue → pattern. Walls, doors, keys → BFS state (r,c,keymask).
Why this. Keys are bits. Door ‘A’ opens if bit ‘a’ is set. Shortest is BFS on that state, not plain (r,c).
Brute. DFS all key orders. Time exp. Space O(mn · 2^K).
Optimal. BFS O(mn · 2^K). Time O(mn 2^K). Space O(mn 2^K).
q.offer({r,c,mask}); vis[r][c][mask]
Described. K keys must be small (≤10). Not Walls and Gates.
k-th largest from each suffix starting at index k IE-asked
Question they ask. They said k-th largest from each suffix starting at index k, but the example [2,2,3] matched k-th of growing prefixes. Lock the range on their example. Do not stamp a LeetCode.
Example. Array [4,2,1,3], k=2. If prefixes of length ≥2: kth of [4,2]=2, [4,2,1]=2, [4,2,1,3]=3 → [2,2,3]. If they truly mean suffixes, walk from the right instead.
Dry run — walk this before you code.
Say out loud. Lock prefix vs suffix on the example. Then size-k heap.
Source. TUF 05 described. Example [4,2,1,3], k=2 → [2,2,3].
Clue → pattern. For each i≥k−1, k-th of a[i−k+1? wait] — they said suffixes starting at k. Use the example.
Why this. Example: suffixes [4,2,1,3], [2,1,3], [1,3], [3] but they started at index k — walk i from k−1..n−1, structure on a[k−1..i] or on a[i..n−1]. The example [2,2,3] matches k-th largest of prefixes ending at i for i=1..n−1 starting when length≥k: of [4,2]=2, [4,2,1]=2, [4,2,1,3]=3. So it is prefixes from 0, not suffixes. Say the example out loud and lock the range.
Brute. Copy and sort each range. Time O(n² log n). Space O(n).
Optimal. Size-k min-heap sliding on the locked range, or Fenwick if they want each k-th of growing prefix. Time O(n log k). Space O(k).
// lock the range from the example before coding
Described. Do not stamp a LeetCode. Example wins over the word “suffix.”
Line sweep (unnamed) IE-asked
Question they ask. They said line sweep; the exact geometry is unnamed. Sort events on x, scan with a counter or TreeMap of actives. Do not invent skyline as what they asked.
Example. Meetings [1,3],[2,4]: events (1,+1),(3,−1),(2,+1),(4,−1). Sort, scan; max overlap 2.
Dry run — walk this before you code.
Say out loud. Sort events, scan. Stay unnamed on the exact prompt.
Source. TUF 03 live R2. Title not given.
Clue → pattern. Line sweep → sort events, scan with a counter or TreeMap of actives.
Why this. Meetings, skyline, overlapping: events (x, +1/−1), sort, scan. Stay unnamed on the exact geometry.
Brute. All pairs overlap. Time O(n²). Space O(1).
Optimal. O(n log n) events. Time O(n log n). Space O(n).
// events.sort; cur+=delta; ans=max(ans,cur)
UNNAMED exact prompt. Do not invent skyline as what they asked.