Open this only after you have typed your own answer on a clock. A row number is a row of lesson 6's pattern selector. Lesson 6 solves drills 1 to 3 (solution 4) and drill 8 (solution 2); this appendix repeats 1 to 3 as one runnable class and solves the rest, with the ten transfer problems from the Practice banks appendix.
Stop: solutions to the ten transfer problems
Read each one only after your own attempt is scored. Each solution names the pattern it transfers from, the idea, a trace of the invented example from the problem table, the cost, the trap, the one hint a partner may give, and a fallback that still scores. The six classes were compiled and run in one file with java --source 21 on OpenJDK 25 on 2 Nov 2026, each against a brute force on 2,000 to 5,000 random small inputs: every arrangement, a sort, a set, every substring and every single deletion, plain recursion, every column order, a minute-by-minute simulation, and every capacity from the heaviest parcel up.
T1 to T3: in place, by index
Code, 41 lines
class InPlace {
/** T1: next arrangement in dictionary order; wraps to the smallest. */
static void nextPerm(int[] a) {
int i = a.length - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--; // longest falling suffix
if (i >= 0) {
int j = a.length - 1;
while (a[j] <= a[i]) j--; // smallest bigger in suffix
swap(a, i, j);
}
reverse(a, i + 1, a.length - 1); // suffix becomes rising
}
/** T2: sort values 0, 1, 2 in one pass (three-way partition). */
static void colours(int[] a) {
int lo = 0, mid = 0, hi = a.length - 1;
while (mid <= hi) { // [mid, hi] is unread
if (a[mid] == 0) swap(a, lo++, mid++);
else if (a[mid] == 1) mid++;
else swap(a, mid, hi--); // do not advance mid
}
}
/** T3: smallest positive missing; O(n) time, O(1) extra space. */
static int firstMissing(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++)
while (a[i] >= 1 && a[i] <= n && a[a[i] - 1] != a[i])
swap(a, i, a[i] - 1); // put v at index v - 1
for (int i = 0; i < n; i++) if (a[i] != i + 1) return i + 1;
return n + 1;
}
static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
static void reverse(int[] a, int i, int j) {
while (i < j) swap(a, i++, j--);
}
}T1, next arrangement. From: two pointers (row 1), worked from the right end. Idea. The longest falling run at the end is already as large as it can be. The value just before it, the pivot, must grow by the least possible amount: swap it with the smallest larger value in the run, then reverse the run so it is as small as possible. Trace. In [1, 3, 5, 4, 2] the falling run is 5, 4, 2, so the pivot is 3 at index 1; the smallest value above 3 in the run is 4; the swap gives [1, 4, 5, 3, 2], and reversing after index 1 gives [1, 4, 2, 3, 5]. In [3, 2, 1] there is no pivot, and the whole array reverses to [1, 2, 3]. Cost. O(n) time, O(1) space. Trap. The comparisons are >= and <=; with strict ones, repeated values break the walk. Hint. "Which part of the array is already as large as it can be?" Follow-up. "Return the arrangement k steps later without stepping k times." Fallback. List every arrangement, sort them and take the next one: O(n! · n), correct, and say why it cannot run at 105. The harness walked every array of 1 to 5 values drawn from 0 to 2 through its whole cycle and checked that it met each distinct arrangement once, in order, and wrapped to the smallest.
T2, three values. From: two pointers (row 1), with three; it is the partition step of quickselect (row 18) with three regions. Idea. Keep [0, lo) all 0, [lo, mid) all 1, [mid, hi] unread and (hi, end] all 2; each step reads a[mid] and shrinks the unread part by one. Trace. [2, 0, 1, 2, 1, 0]: a 2 at mid 0 swaps with the end, [0, 0, 1, 2, 1, 2] and hi 4; two 0s move lo and mid to 2; the 1 moves mid to 3; the 2 at mid 3 swaps with hi 4, [0, 0, 1, 1, 2, 2] and hi 3; the 1 moves mid to 4, past hi, and the loop ends. Cost. One pass, O(n) time, O(1) space. Trap. After a swap with hi, do not advance mid: the value that came from hi has not been read. Hint. "Keep three finished regions and one unread middle." Follow-up. "Four values instead of three." Fallback. Count the three values, then write them back: two passes, which the prompt forbids, but correct and worth a point if you say so.
T3, smallest missing positive. From: swapping into place, as in row 18's partition, with the index as the hash key. Idea. The answer is between 1 and n + 1, so only values 1 to n matter, and each can live at index value − 1. Swap each value home, then the first index that does not hold its own value gives the answer. Trace. [3, -1, 4, 1]: at index 0, 3 goes to index 2, which brings 4; 4 goes to index 3, which brings 1; 1 is home. The array is [1, -1, 3, 4]; index 1 does not hold 2, so the answer is 2. Cost. O(n) time, because every swap puts one value home for good; O(1) extra space. Trap. The loop condition is a[a[i] - 1] != a[i], not a[i] != i + 1: on [1, 1] the second form swaps two equal values for ever. Hint. "The answer is at most n + 1. Could each value sit at its own index?" Follow-up. "The array is read-only." Fallback. A hash set of the values and a count up from 1: O(n) time and O(n) space, correct, breaking only the space limit.
Gave up / revisit when / signal (T1 to T3). Gave up: the k-th arrangement directly (factorial number system) and a stable three-way sort of objects. Revisit when: the values carry records that must keep their order. Signal: the region invariant said aloud before the loop.
T4 and T5: palindromes, from the middle and from the ends
Code, 27 lines
class Pal {
/** T4: longest palindromic substring, by growing from each centre. */
static String longest(String s) {
int bestL = 0, bestR = 0; // half-open [bestL, bestR)
for (int c = 0; c < 2 * s.length() - 1; c++) {
int l = c / 2, r = l + c % 2; // odd centre, then even
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
if (r - l - 1 > bestR - bestL) { bestL = l + 1; bestR = r; }
}
return s.substring(bestL, bestR);
}
/** T5: a palindrome after deleting at most one character? */
static boolean oneDeletion(String s) {
int l = 0, r = s.length() - 1;
while (l < r && s.charAt(l) == s.charAt(r)) { l++; r--; }
return l >= r || isPal(s, l + 1, r) || isPal(s, l, r - 1);
}
static boolean isPal(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
}T4, longest palindrome. From: two pointers (row 1), moving outward. Idea. Every palindrome has a centre, either a character or a gap between two, so there are 2n − 1 centres; grow from each while the ends match and keep the longest. Trace. In "cabbad" the gap between the two b's grows to "bb", then "abba", then stops at c and d: length 4, the longest. Cost. O(n2) time in the worst case, on a string of one letter; O(1) extra space. Trap. Forgetting the even centres, which loses "abba". Hint. "Every palindrome has a centre. How many centres are there?" Follow-up. "Count every palindromic substring instead." Fallback. A table of whether s[i..j] is a palindrome, filled by length (row 15): O(n2) time and space.
T5, one deletion. From: two pointers (row 1). Idea. Walk in from both ends while the characters match. At the first mismatch, one of those two characters must go, so try both ways once with a plain palindrome check, and allow no more deletions. Trace. "radkar": r and r match, a and a match, then d and k differ; skipping d leaves "k", a palindrome, so true. "abcda": b and d differ; neither "cd" nor "bc" reads the same both ways, so false. Cost. O(n) time, O(1) space. Trap. Trying only one side: "abbca" works only by deleting c, the right-hand character, and the harness checks that case. Hint. "Walk in from both ends. What choices do you have at the first mismatch?" Follow-up. "At most k deletions." Fallback. Delete each character in turn and test: O(n2), correct.
Gave up / revisit when / signal (T4 and T5). Gave up: Manacher's O(n) algorithm and "at most k deletions", which needs a DP. Revisit when: n reaches 106 for T4, or k is above 1 for T5. Signal: both centre kinds, or both deletions, named before the code.
T6 and T7: ways to split a string
Code, 30 lines
import java.util.Set;
class Splits {
/** T6: ways to read digits as letters 1 to 26. */
static long decode(String s) {
long prev2 = 1, prev1 = 1; // ways for i-2 and i-1 chars
for (int i = 0; i < s.length(); i++) {
long cur = s.charAt(i) == '0' ? 0 : prev1;
if (i > 0) {
int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
if (two >= 10 && two <= 26) cur += prev2;
}
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
/** T7: can s be cut into words from the dictionary? */
static boolean wordBreak(String s, Set<String> dict) {
int maxLen = 0;
for (String w : dict) maxLen = Math.max(maxLen, w.length());
boolean[] ok = new boolean[s.length() + 1]; // ok[i]: first i chars
ok[0] = true;
for (int i = 1; i <= s.length(); i++)
for (int j = Math.max(0, i - maxLen); j < i && !ok[i]; j++)
ok[i] = ok[j] && dict.contains(s.substring(j, i));
return ok[s.length()];
}
}T6, ways to decode. From: one-dimensional DP (row 15), with the climbing-stairs shape. Idea. The readings of the first i digits are the readings of the first i − 1 when digit i can stand alone (it is not 0), plus those of the first i − 2 when the last two digits form 10 to 26. Two variables hold the window. Trace. "2263": after "2", 1; after "22", 1 + 1 = 2; after "226", 2 + 1 = 3, since 26 is a letter; after "2263", 3, since 63 is not. Cost. O(n) time, O(1) space. Trap. Zeros: "0" alone and "06" are not letters, so "100" gives 0. And size: the count for k ones is a Fibonacci number, so 46 ones overflow an int and 92 overflow a long (arithmetic, checked by script on 2 Nov 2026); the limit of 90 keeps a long safe. Hint. "How many readings for the first i digits, given the counts for i − 1 and i − 2?" Follow-up. "Length 105; return the count modulo 109 + 7." Fallback. Recursion on the start index with a memo: the same O(n), with the recursion depth stated.
T7, cut into words. From: one-dimensional DP over prefixes (row 15). Idea. ok[i] says the first i characters can be cut; ok[i] is true when some earlier ok[j] is true and s[j..i) is a word. Only the last maxLen positions need checking. Trace. "loopready" with {loop, re, ad, y}: ok[4] from "loop", ok[6] from "re", ok[8] from "ad", ok[9] from "y": true. "loopread" with {loop, ready}: ok[4] is true, but no word covers "read", so false. Cost. O(n · L2) time with L the longest word, since each check builds a substring of up to L characters; O(n) space beyond the dictionary. Trap. Taking the longest matching word greedily: on "abcd" with {ab, abc, cd} greedy takes "abc" and is stuck on "d", while "ab" then "cd" works; the harness checks that case. Hint. "Which prefixes of the string can be cut cleanly?" Follow-up. "Return one valid cut, not just true or false." Fallback. Recursion on the start index with a memo of failed starts: the same bound, easier to say.
Gave up / revisit when / signal (T6 and T7). Gave up: listing every sentence (word break II, which can be exponential in output) and a trie over the dictionary (row 17) to cut the substring cost. Revisit when: the prompt asks for the sentences, or the dictionary is large and the words long. Signal: the state said in one sentence ("ok[i]: the first i characters") before the loop.
T8: n queens, pruned
Code, 21 lines
class Queens {
/** T8: count boards of n queens, none attacking another. */
static int count(int n) {
return place(0, n, new boolean[n], new boolean[2 * n],
new boolean[2 * n]);
}
private static int place(int row, int n, boolean[] col,
boolean[] diag, boolean[] anti) {
if (row == n) return 1;
int ways = 0;
for (int c = 0; c < n; c++) {
int d = row - c + n, a = row + c; // one index per diagonal
if (col[c] || diag[d] || anti[a]) continue; // prune now
col[c] = diag[d] = anti[a] = true;
ways += place(row + 1, n, col, diag, anti);
col[c] = diag[d] = anti[a] = false; // undo
}
return ways;
}
}From: backtracking (row 14), with pruning. Idea. One queen per row. Three arrays mark the columns and the two diagonal directions already attacked; row − c is the same along one diagonal and row + c along the other, so a placement is tested in O(1), and a dead square is rejected before the next row is tried. Trace. For n = 6 the search finds 4 boards. An instrumented copy, run on 2 Nov 2026, made 153 calls to place for n = 6, 2,057 for n = 8 (92 boards) and 35,539 for n = 10 (724 boards); an unpruned search for n = 8 would try 88 = 16,777,216 boards with one queen per row (arithmetic). Cost. Exponential, but the pruning keeps n up to 10 instant. Trap. row − c is negative whenever c is greater than row, so the listing adds n before using it as an index. A second trap: testing a board only once it is full, which throws away the pruning. Hint. "One queen per row. What must you remember to reject a column at once?" Follow-up. "Return one board, not the count." Fallback. Place a queen per row and check it against every earlier queen: O(n) per check instead of O(1), still pruned, still fine at n = 10. The harness compared the count with every column order for n = 1 to 8.
Gave up / revisit when / signal (T8). Gave up: bitmask columns and diagonals, which make each step a few machine operations, and printing the boards. Revisit when: n reaches 14 or more, or the prompt wants the boards. Signal: the diagonal indexes derived aloud, not recalled.
T9: spread from many sources at once
Code, 33 lines
import java.util.ArrayDeque;
import java.util.Deque;
class Spread {
/** T9: minutes until no cell is 1, or -1; 2 spreads each minute. */
static int minutes(int[][] g) {
int R = g.length, C = g[0].length, fresh = 0;
int[][] t = new int[R][];
for (int i = 0; i < R; i++) t[i] = g[i].clone(); // keep the input
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (t[i][j] == 2) q.add(new int[] {i, j}); // every source at once
if (t[i][j] == 1) fresh++;
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int min = 0;
while (fresh > 0 && !q.isEmpty()) {
min++;
for (int k = q.size(); k > 0; k--) { // one minute = one layer
int[] p = q.poll();
for (int[] d : dirs) {
int y = p[0] + d[0], x = p[1] + d[1];
if (y < 0 || y >= R || x < 0 || x >= C || t[y][x] != 1) continue;
t[y][x] = 2;
fresh--;
q.add(new int[] {y, x});
}
}
}
return fresh == 0 ? min : -1;
}
}From: BFS on a grid (row 8), started from every source at once. Idea. Put every infected machine in the queue before the first minute; each layer of the BFS is one minute. Count the working machines, subtract one per infection, and stop when none are left. Trace. {{2, 1, 1}, {0, 1, 0}, {1, 1, 2}}: minute 1 infects (0, 1) from the top-left and (2, 1) from the bottom-right; minute 2 infects (0, 2), (1, 1) and (2, 0); no working machine is left, so 2. In {{1, 0, 2}} the empty cell cuts the 1 off, so -1. Cost. O(R · C) time and space: each cell enters the queue at most once. Trap. Counting a minute for the last layer when it infects nothing; the loop runs only while working machines remain, so {{0, 2}} gives 0. A second trap: one BFS per source, then a minimum over them, which multiplies the cost by the number of sources. Hint. "What if every infected machine starts the clock at the same moment?" Follow-up. "Return the minute each machine was infected." Fallback. Simulate minute by minute over the whole grid: O((R · C)2) in the worst case, which is the harness's oracle.
Gave up / revisit when / signal (T9). Gave up: diagonal spread and walls that take time to cross (a weighted grid, row 16). Revisit when: cells spread at different speeds. Signal: all sources queued before the loop, said as the reason the layers are minutes.
T10: binary search on the capacity
Code, 22 lines
class Ship {
/** T10: least capacity that ships w, in order, within days. */
static int minCapacity(int[] w, int days) {
int lo = 0, hi = 0;
for (int x : w) { lo = Math.max(lo, x); hi += x; } // bounds
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysNeeded(w, mid) <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}
static int daysNeeded(int[] w, int cap) {
int d = 1, load = 0;
for (int x : w) {
if (load + x > cap) { d++; load = 0; }
load += x;
}
return d;
}
}From: binary search on the answer (row 12). Idea. If a capacity ships everything in time, every larger one does too, so search the least capacity between the heaviest parcel and the total weight, testing each guess with a greedy count of days. Trace. [4, 2, 7, 3, 5, 1] and D = 3: lo 7, hi 22. Guess 14: [4, 2, 7], [3, 5, 1], 2 days, so hi = 14. Guess 10: [4, 2], [7, 3], [5, 1], 3 days, so hi = 10. Guess 8: [4, 2], [7], [3, 5], [1], 4 days, so lo = 9. Guess 9: [4, 2], [7], [3, 5, 1], 3 days, so hi = 9; lo meets hi at 9. Cost. O(n log(total)) time, O(1) space. The total is at most 2.5 × 107 within the limits, so an int is safe (arithmetic). Trap. lo must start at the heaviest parcel: daysNeeded assumes every parcel fits, and below that it undercounts. Hint. "If capacity c works, does c + 1 work? Then what can you search?" Follow-up. "Why is this the same problem as cutting an array into D parts with the least largest sum?" Fallback. Try every capacity from the heaviest parcel up: O(n · total), correct, and it is the harness's oracle.
Gave up / revisit when / signal (T10). Gave up: parcels that may be reordered, which turns this into bin packing, NP-hard. Revisit when: the order is free. Signal: the monotone sentence ("if c works, c + 1 works") said before the search.
Next stop: Stop: solutions to the drill set, 12 min
Stop: solutions to the drill set
Read on only after you have typed and scored the drills. Drill 8 is lesson 6's solution 2; the other eleven are below, then the follow-ups to drills 3 and 4. Each main holds the fixed checks. Each class was run with java --source 21 on OpenJDK 25 (2 Nov 2026; drills 10 and 11 and the follow-ups on 4 Nov 2026) and compared with a brute force on random inputs.
Drills 1 to 3: reverse, cycle start, merge
Code, 61 lines
class ListDrills {
static class Node { int val; Node next; Node(int v) { val = v; } }
static Node reverse(Node head) { // drill 1
Node prev = null;
while (head != null) {
Node next = head.next; // save before overwriting
head.next = prev; prev = head; head = next;
}
return prev;
}
static Node cycleStart(Node head) { // drill 2 (Floyd)
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) { // met inside the ring
slow = head; // a steps from both
while (slow != fast) { slow = slow.next; fast = fast.next; }
return slow;
}
}
return null; // the list ends: no ring
}
static Node merge(Node a, Node b) { // drill 3
Node dummy = new Node(0), tail = dummy;
for (; a != null && b != null; tail = tail.next)
if (b.val < a.val) { tail.next = b; b = b.next; }
else { tail.next = a; a = a.next; } // ties take a: stable
tail.next = a != null ? a : b; // link the rest whole
return dummy.next;
}
static Node of(int... v) {
Node d = new Node(0), t = d;
for (int x : v) t = t.next = new Node(x);
return d.next;
}
static String str(Node n) {
StringBuilder sb = new StringBuilder();
for (; n != null; n = n.next) sb.append(n.val).append(' ');
return sb.toString().trim();
}
static void check(boolean ok) { if (!ok) throw new AssertionError(); }
public static void main(String[] args) {
check(reverse(null) == null && str(reverse(of(7))).equals("7"));
check(str(reverse(of(1, 2, 3))).equals("3 2 1"));
Node h = of(1, 2, 3, 4, 5), s = h.next.next;
s.next.next.next = s; // 5 links back to 3
Node self = of(9);
self.next = self;
check(cycleStart(h) == s && cycleStart(self) == self);
check(cycleStart(null) == null && cycleStart(of(1, 2, 3)) == null);
check(str(merge(of(1, 4, 6), of(2, 4, 5))).equals("1 2 4 4 5 6"));
Node x = of(4), y = of(4);
check(merge(x, y) == x && merge(null, null) == null);
System.out.println("lists ok");
}
}Cost. One pass each: O(n) time (O(n + m) for the merge) and O(1) extra space, because nodes are relinked, not copied. Traps. Reverse: overwrite head.next before saving it and the rest of the list is lost; the loop, not recursion, survives a 200,000-node list. Cycle start: test fast.next before fast.next.next. The restart works because if the tail before the ring has a nodes and the pointers meet b steps into the ring, a + b is a whole number of laps, so a more steps from the meeting point lands on the ring's first node, as do a steps from the head. Merge: without the dummy head the first node is a special case.
Drills 4 to 6: validate, lowest common ancestor, build
Code, 68 lines
import java.util.HashMap;
import java.util.Map;
class TreeDrills {
static class T { int val; T l, r; T(int v) { val = v; } }
static boolean isBst(T t) { // drill 4
return ok(t, Long.MIN_VALUE, Long.MAX_VALUE); // long: no clash
}
static boolean ok(T t, long lo, long hi) {
if (t == null) return true;
if (t.val <= lo || t.val >= hi) return false; // equal keys fail
return ok(t.l, lo, t.val) && ok(t.r, t.val, hi);
}
static T lca(T root, T p, T q) { // drill 5; p, q present
if (root == null || root == p || root == q) return root;
T a = lca(root.l, p, q), b = lca(root.r, p, q);
return a != null && b != null ? root : a != null ? a : b;
}
static T lcaBst(T n, T p, T q) { // BST: O(h), no stack
while (n != null)
if (p.val < n.val && q.val < n.val) n = n.l;
else if (p.val > n.val && q.val > n.val) n = n.r;
else return n; // the paths split here
return null;
}
static T build(int[] pre, int[] in) { // drill 6; distinct values
Map<Integer, Integer> at = new HashMap<>();
for (int i = 0; i < in.length; i++) at.put(in[i], i);
return build(pre, 0, 0, in.length - 1, at);
}
static T build(int[] pre, int p, int lo, int hi,
Map<Integer, Integer> at) {
if (lo > hi) return null;
T t = new T(pre[p]);
int m = at.get(pre[p]); // root's place in inorder
t.l = build(pre, p + 1, lo, m - 1, at);
t.r = build(pre, p + 1 + m - lo, m + 1, hi, at); // skip left size
return t;
}
static String show(T t) {
return t == null ? "#" : t.val + "," + show(t.l) + "," + show(t.r);
}
static void check(boolean ok) { if (!ok) throw new AssertionError(); }
public static void main(String[] args) {
T root = build(new int[] {10, 5, 1, 7, 15, 12, 20},
new int[] {1, 5, 7, 10, 12, 15, 20});
check(show(root).equals("10,5,1,#,#,7,#,#,15,12,#,#,20,#,#"));
check(isBst(root) && isBst(null) && isBst(new T(Integer.MAX_VALUE)));
root.r.l.val = 6; // a 6 under 15, right of 10
check(!isBst(root));
root.r.l.val = 12;
T dup = new T(5);
dup.l = new T(5);
check(!isBst(dup) && build(new int[0], new int[0]) == null);
T n1 = root.l.l, n7 = root.l.r, n20 = root.r.r;
check(lca(root, n1, n7) == root.l && lca(root, n1, n20) == root);
check(lca(root, root.l, n7) == root.l);
check(lcaBst(root, n1, n7) == root.l);
check(lcaBst(root, n7, n20) == root);
System.out.println("trees ok");
}
}Cost. Validate and lca: O(n) time and O(h) stack for height h; lcaBst: O(h) time, O(1) space; build: O(n) with the index map, O(n squared) if you search the inorder list for each root. Traps. Validate: comparing a node only with its parent passes the 6 under the 15 in the checks; the bounds are long, so a node holding Integer.MAX_VALUE is not mistaken for a sentinel. LCA: the three-line form assumes both nodes are in the tree; for the follow-up (one may be missing), count the targets found and return null unless both were. Build: values must be distinct, since with repeats two different trees can share both traversals; ask.
Drills 7, 9 and 12: Kadane, window maximum, window median
Code, 60 lines
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.TreeSet;
class ArrayDrills {
static long kadane(int[] a) { // drill 7; a not empty
long best = a[0], cur = a[0];
for (int i = 1; i < a.length; i++) {
cur = Math.max(a[i], cur + a[i]); // drop a negative run
best = Math.max(best, cur);
}
return best;
}
static int[] windowMax(int[] a, int k) { // drill 9; 1 <= k <= n
int[] out = new int[a.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // indexes; values fall
for (int i = 0; i < a.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
dq.addLast(i);
if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
}
return out;
}
static double[] windowMedian(int[] a, int k) { // drill 12; 1 <= k <= n
Comparator<Integer> by = (x, y) -> a[x] != a[y]
? Integer.compare(a[x], a[y]) : Integer.compare(x, y);
TreeSet<Integer> lo = new TreeSet<>(by), hi = new TreeSet<>(by);
double[] out = new double[a.length - k + 1];
for (int i = 0; i < a.length; i++) {
if (i >= k && !lo.remove(i - k)) hi.remove(i - k);
lo.add(i);
hi.add(lo.pollLast()); // the new value passes lo
if (hi.size() > lo.size()) lo.add(hi.pollFirst());
if (i >= k - 1) out[i - k + 1] = k % 2 == 1 ? a[lo.last()]
: ((double) a[lo.last()] + a[hi.first()]) / 2;
}
return out;
}
static void check(boolean ok) { if (!ok) throw new AssertionError(); }
public static void main(String[] args) {
check(kadane(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}) == 6);
check(kadane(new int[] {-3, -1, -2}) == -1);
int[] w = {1, 3, -1, -3, 5, 3, 6, 7};
check(Arrays.equals(windowMax(w, 3), new int[] {3, 3, 5, 5, 6, 7}));
check(Arrays.equals(windowMedian(w, 3),
new double[] {1, -1, -1, 3, 5, 6}));
check(Arrays.equals(windowMedian(new int[] {5, 5, 5, 1}, 2),
new double[] {5, 5, 3}));
int big = Integer.MAX_VALUE;
check(windowMedian(new int[] {big, big}, 2)[0] == big);
System.out.println("arrays ok");
}
}Cost. Kadane O(n) time, O(1) space; window maximum O(n), since each index enters and leaves the deque once; window median O(n log k). Traps. Kadane: starting best at 0 returns 0 for an all-negative array; the sums are long. Window maximum: the deque holds indexes, not values, so the front's expiry is one comparison; a heap is the O(n log n) fallback. Window median: the two TreeSets order indexes by value and then by index, so equal values stay distinct and the leaving one is removed in O(log k); this is the follow-up's ordered-set route. The two middle values are averaged in double, so two Integer.MAX_VALUEs do not overflow.
Drills 10 and 11: online booking, Islands II
Drill 10 (row 6, with a sorted map). Accept a booking only if it overlaps nothing accepted, answering each as it arrives. Keep accepted bookings in a TreeMap keyed by start. A new [s, e) can clash only with the last booking starting at or before s (does it run past s?) or the first starting at or after s (does it start before e?); floorEntry and ceilingEntry fetch both in O(log n).
Code, 25 lines
import java.util.TreeMap;
class Booker {
private final TreeMap<Integer, Integer> byStart = new TreeMap<>();
/** Half-open [s, e). True and stored if it overlaps nothing booked. */
boolean book(int s, int e) {
if (s >= e) return false; // empty or backwards
var before = byStart.floorEntry(s); // last start <= s
if (before != null && before.getValue() > s) return false;
var after = byStart.ceilingEntry(s); // first start >= s
if (after != null && after.getKey() < e) return false;
byStart.put(s, e);
return true;
}
public static void main(String[] args) {
Booker b = new Booker();
check(b.book(10, 20) && b.book(20, 30)); // touching ends are fine
check(!b.book(15, 25) && !b.book(5, 11) && !b.book(7, 7));
check(b.book(0, 10) && !b.book(0, 40));
System.out.println("booker ok");
}
static void check(boolean ok) { if (!ok) throw new AssertionError(); }
}Cost. O(log n) per booking, O(n) space, where a list scan is O(n) per booking. Traps. Ranges are half-open, so [10, 20) then [20, 30) is accepted; whether empty or backwards bookings are rejected (as here) is a question for the interviewer. The run compared 3,000 random sequences of twelve bookings with a linear scan. Follow-up (up to two overlaps): two neighbours no longer decide it; keep +1 at each start and -1 at each end in a sorted map, add the booking, walk the running count and undo if it passes 2: O(n) per booking (named, not coded here).
Drill 11 (row 11, union-find). A flood fill after each added cell costs the whole grid each time. A new cell starts one island and merges with up to four neighbours, so add one for the cell and subtract one for every union that joins two different islands. The parent array doubles as the grid: -1 is water.
Code, 44 lines
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Islands2 {
private static int find(int[] p, int x) {
while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } // path halving
return x;
}
/** Island count after each land cell is added; repeats are harmless. */
static List<Integer> counts(int h, int w, int[][] adds) {
int[] p = new int[h * w];
Arrays.fill(p, -1); // -1 means still water
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int islands = 0;
List<Integer> out = new ArrayList<>();
for (int[] a : adds) {
if (a[0] < 0 || a[0] >= h || a[1] < 0 || a[1] >= w)
throw new IllegalArgumentException("cell off the grid");
int id = a[0] * w + a[1];
if (p[id] == -1) {
p[id] = id;
islands++; // new island, then merge
for (int[] d : dirs) {
int r = a[0] + d[0], c = a[1] + d[1];
if (r < 0 || c < 0 || r >= h || c >= w || p[r * w + c] == -1)
continue;
int x = find(p, id), y = find(p, r * w + c);
if (x != y) { p[x] = y; islands--; }
}
}
out.add(islands);
}
return out;
}
public static void main(String[] args) {
int[][] adds = {{0, 0}, {0, 1}, {1, 2}, {2, 1}, {1, 1}};
if (!counts(3, 3, adds).equals(List.of(1, 1, 2, 3, 1)))
throw new AssertionError("sample");
System.out.println("islands ok");
}
}Cost. O(h × w) to set up, then m additions in O(m log(h × w)) at worst with path halving alone, near linear in practice; adding union by size (lesson 6's Dsu) makes each call near O(1). Traps. A repeated cell must not count twice; compare roots, not neighbours. The run replayed 2,000 random sequences, repeats included, against a fresh flood fill after every step. Follow-up (a cell turns back into water): union-find cannot split a set. If every operation is known in advance, process them backwards so removals become additions (offline); online, rebuild from the grid per removal. Name these; do not code them unless asked.
Follow-ups to drills 3 and 4: merge k lists, validate without recursion
Each method goes inside a drill class above: mergeK in ListDrills, isBstLoop in TreeDrills. The first needs imports of Comparator, List and PriorityQueue; the second, ArrayDeque and Deque.
Code, 11 lines
static Node mergeK(List<Node> lists) { // drill 3 follow-up
PriorityQueue<Node> pq =
new PriorityQueue<>(Comparator.comparingInt((Node n) -> n.val));
for (Node n : lists) if (n != null) pq.add(n); // one head each
Node dummy = new Node(0), tail = dummy;
while (!pq.isEmpty()) {
tail = tail.next = pq.poll(); // smallest head of all
if (tail.next != null) pq.add(tail.next);
}
return dummy.next;
}Cost. O(N log k) for N nodes in k lists, since the heap never holds more than k heads; O(k) extra space. Traps. Skip empty lists before adding; compare with comparingInt, not a.val - b.val. Checked against sorting all the values on 3,000 random sets of lists.
Code, 11 lines
static boolean isBstLoop(T root) { // drill 4 follow-up
Deque<T> st = new ArrayDeque<>();
long prev = Long.MIN_VALUE; // below every int value
for (T n = root; n != null || !st.isEmpty(); n = n.r) {
for (; n != null; n = n.l) st.push(n); // walk down the left edge
n = st.pop();
if (n.val <= prev) return false; // inorder must rise
prev = n.val;
}
return true;
}Cost. O(n) time, O(h) space for the explicit stack, which lives on the heap: a 200,000-node chain runs (checked), where plain recursion overflowed at 50,000 levels in the author's run. Traps. An inorder walk of a BST must strictly rise; prev starts below every int, so a node holding Integer.MIN_VALUE passes. Checked against the recursive isBst on 20,000 random small trees.