The last-night sheet

If you see this → think that

One trigger per pattern chapter. Read the left side, say the right side before you look.

"Find two/k items that add up to / match something"

HashMap of what you've seen (or sort + two pointers) Mindset

A loop variable that halves or doubles (i /= 2, i *= 2, lo..hi shrinking by half)

O(log n) Big-O

The answer for n is defined using the answer for n − 1, n / 2, or a sub-part

Write the recurrence first, then the base case Recursion

"The answer may be large, return it modulo 10⁹+7"

Reduce after every + and ×, use long for products, divide with Fermat's inverse Math & Numbers

"Contiguous subarray" with the max/min sum

Kadane: extend or restart at each index Arrays & Strings

"Spiral order", "layer by layer", "ring"

Four shrinking walls, with guards for a single leftover row or column Matrices

The array is sorted and you need a pair / triplet with some sum

Opposite-ends pointers Two Pointers

"Contiguous subarray" or "substring" + longest / shortest / maximum / minimum

Variable sliding window Sliding Window

"Find a pair / complement" in an unsorted array, return indices

HashMap value → index, look up target − x before storing x Hashing

"Middle of the list", "split in half", "palindrome list"

slow / fast pointers (fast moves 2) Linked Lists

Brackets, tags or anything that opens and closes and can nest

Push openers; a closer must match the top Stacks

"Process in the order they arrive", "first come first served", task scheduling

Plain FIFO queue (ArrayDeque) Queues

Input is sorted (or each row of a matrix is) and you need O(log n)

Classic binary search or lower/upper bound Binary Search

Intervals, meetings, schedules — anything with start/end

Sort by start (or end), then sweep once Sorting

"Implement atoi", "parse this number", "is this a valid number"

A small state machine: spaces → sign → digits (→ '.' → exponent), with an overflow guard Parsing

"Level", "row", "zigzag", "right side view", "average of each level"

BFS with size = queue.size() per round Traversals

"Maximum/minimum depth", "height", "is balanced"

Postorder: return the height up; use −1 or a record for "invalid" Tree Recursion

The input is a BST and you need sorted order

Inorder traversal (iterative with a stack if you need to stop early) BST

"k largest", "k smallest", "k closest", "top k frequent"

Size-k heap in the opposite direction (or quickselect / buckets) Heaps

"prefix", "starts with", "autocomplete", "suggestions", "typeahead"

Trie — walk to the prefix node Tries

"Minimum number of steps / moves / transformations" with all moves costing the same

BFS from the start; level = answer Graphs

"Minimum cost / time / distance" with weighted edges

Dijkstra (if no negative weights) Shortest Paths

"Groups", "connected", "same component", "friends of friends", "merge accounts"

Union-Find (or DFS) over the connection relation Union-Find & MST

"prerequisites", "depends on", "must happen before", "build order"

Directed graph + topological sort Topo Sort

"Use every ticket / edge / domino exactly once"

Euler path: degree check + Hierholzer (add when stuck, reverse) Advanced Graphs

"Return all …" (subsets, permutations, combinations, partitions, valid strings)

Backtracking — the output itself is exponential, so nothing faster exists Backtracking

"Can you reach the end?" / "fewest jumps"

Furthest reach; BFS levels without a queue Greedy

"Merge", "insert", "union of ranges"

Sort by start, extend the last group Intervals

"Every element appears twice except one"

XOR everything: pairs cancel Bits

"Count the number of ways…"

Counting DP: dp[state] = sum of ways of the smaller states it comes from Dynamic Programming

Buy and sell with a cooldown, a fee, or at most k trades

State-machine DP: one variable per mode, one max() per arrow DP Patterns

"insert, delete and getRandom, all in O(1)"

HashMap value → index + ArrayList; delete by swapping with the last element Design DS

Many range-sum queries, no updates

Prefix sums (Hashing & Prefix Sums chapter) — don't overbuild Range Queries & Strings

Complexity budget

Find the biggest n in the constraints. Its row tells you how fast your idea must be (about 10⁸ simple steps a second).

The 45-minute plan, in brief

You never have to wonder what comes next. The full version, with what to say: the 45-minute plan.

1. 3 minClarifyMake sure you are solving the right problem.
2. 2 minExamplesTurn the words into one small, concrete case.
3. 3 minBrute forcePut a correct answer on the table, even a slow one.
4. 4 minOptimiseFind the slow part and fix it with the right data structure.
5. 18 minCodeTranslate the agreed plan into clean Java, talking as you go.
6. 8 minTestFind your own bugs before the interviewer does.
7. 7 minComplexity & follow-upsShow you know what your solution costs and how it would change.

Java traps that fail hidden tests

Each one passes the small examples and fails the big hidden ones. The fix is the habit to keep.

• == on Integer Compare wrappers with .equals(), or unbox to int first. Never == on Integer.
• Comparing HashMap counts count.get(a).equals(count.get(b)), or Objects.equals(x, y) if a value can be null.
• int overflow Use long when a sum can pass about 2 × 10⁹, or Math.addExact to fail loudly.
• Binary search mid Write int mid = lo + (hi - lo) / 2; in every binary search. Bas itna yaad rakho.
• char + 1 When you want a letter, cast: (char) (c + 1).
• Digit char to int c - '0' for a digit, c - 'a' for a letter's index.
• Arrays.asList then add new ArrayList<>(Arrays.asList(1, 2, 3)) when the list must grow.
• Arrays.asList(int[]) Box it: Arrays.stream(nums).boxed().collect(Collectors.toList()), or start from an Integer[].
• Reassign vs mutate To give back a new array, return it. To change the caller's data, change the object, not the variable.
• result.add(path) Add a copy: result.add(new ArrayList<>(path));

One trap per chapter

The mistake each chapter warns about most. If one feels new, that's your five minutes tomorrow morning.

• 01 · Java Memory == on objects compares references. Use equals for String/Integer and Arrays.equals for arrays. Literals only look safe because they are pooled.
• 02 · Java Arrays & Strings arr.length · s.length() · list.size(). And == on arrays or strings compares references — use Arrays.equals / equals.
• 03 · Java OOP Override equals without hashCode and HashSet/HashMap stop finding equal keys. Override both, from the same fields.
• 04 · I/O & Debugging PrintWriter without flush() prints nothing → WA. nextInt() then nextLine() returns "". Debug prints on stdout → WA.
• 05 · Java Toolkit Integer == compares references: true for −128..127 (the cache), false for 128 on a default JVM. Use equals, or unbox to int.
• 06 · Mindset Coding before understanding. Most wrong answers solve a slightly different problem. Restate it and run one example by hand first.
• 07 · Big-O Hidden loops: list.contains, list.remove(0), substring, s += x are O(n). Inside a loop they quietly make O(n²).
• 08 · Recursion No reachable base case → frames pile up → StackOverflowError. Java has no tail-call optimization, so depth 10⁴–10⁵ is risky.
• 09 · Math & Numbers (a * b) % M with ints overflows before the %. Write (long) a * b % M.
• 10 · Arrays & Strings s += c in a loop is O(n²): every += copies the whole string. Build with StringBuilder, call toString() once.
• 11 · Matrices Writing cells while you still read their old values breaks Game of Life and Set Zeroes. Freeze a copy, or keep old + new in one cell.
• 12 · Two Pointers l <= r pairs an element with itself. Pair problems use l < r.
• 13 · Sliding Window Negative numbers break sum windows: removing one can raise the sum. Use prefix sums + a HashMap instead.
• 14 · Hashing Override equals without hashCode (or change a key after put) and the entry is lost: lookups go to the wrong bucket.
• 15 · Linked Lists Overwriting curr.next before saving it loses the rest of the list. Forgetting tail.next = null after splitting creates a cycle.
• 16 · Stacks pop() on an empty ArrayDeque throws; peek() returns null. Check isEmpty() first — and check the stack is empty at the end.
• 17 · Queues head == tail means both empty and full — keep a size. Stepping left? (head − 1 + k) % k, because Java's % can be negative.
• 18 · Binary Search (lo + hi) / 2 overflows past 2³¹ − 1. Write lo + (hi − lo) / 2 — the JDK itself carried this bug for about nine years.
• 19 · Sorting (a, b) -> a - b overflows: MIN_VALUE - 1 wraps to a big positive. Use Integer.compare(a, b) or Comparator.comparingInt.
• 20 · Parsing Overflow: check result > (MAX - d) / 10 before result * 10 + d. After the multiply it has already wrapped.
• 21 · Traversals for (int i = 0; i < queue.size(); i++) mixes levels — the queue grows inside the loop. Freeze size first.
• 22 · Tree Recursion Returning the answer instead of what the parent needs: Diameter returns the height and records left + right — never returns the bend.
• 23 · BST Checking only left.val < node.val < right.val misses grandchildren. Pass (low, high) bounds down — as null/long, never Integer.MIN_VALUE sentinels.
• 24 · Heaps Printing or iterating a PriorityQueue is NOT sorted — only repeated poll() returns values in order.
• 25 · Tries search must check isEnd at the last node — otherwise "app" is "found" after inserting only "apple".
• 26 · Graphs Mark visited when you enqueue, not when you poll — or the same vertex is queued many times.
• 27 · Shortest Paths Dijkstra + a negative edge = wrong answers. "Polled means final" only holds when no edge can shrink a path later.
• 28 · Union-Find & MST parent[a] == parent[b] is not "same set" — compare find(a) == find(b). And link roots: parent[find(a)] = find(b).
• 29 · Topo Sort [course, pre] means the arrow goes pre → course. Draw one edge on paper before you code.
• 30 · Advanced Graphs Greedy "smallest next airport" can hit a dead end. Add an airport only when it's STUCK, then reverse — that splices the loops in.
• 31 · Backtracking result.add(path) stores a reference that ends up empty. Always result.add(new ArrayList<>(path)).
• 32 · Greedy Coins {1, 3, 4}, amount 6: biggest-first pays 4+1+1 (3 coins), but 3+3 is 2. Test 2–3 tiny inputs before trusting greedy.
• 33 · Intervals Touching rules differ: [1,4]+[4,5] merge in LC 56, but [1,2] and [2,3] live together in LC 435 and meeting rooms. One < vs <=.
• 34 · Bits == binds tighter than &: write (x & m) != 0. And (x & m) == 1 is only right for bit 0.
• 35 · Dynamic Programming 0/1 knapsack in 1D: loop capacity DOWN. Going up lets an item be reused — that's unbounded knapsack.
• 36 · DP Patterns Never read a state you already changed today: save prev values first. Holding starts at −∞ (MIN_VALUE / 2), never 0.
• 37 · Design DS Swap-with-last: update the moved element's index, and remove val from the map last — or deleting the last element breaks.
• 38 · Range Queries & Strings Fenwick index 0 never moves (0 & -0 == 0) — stay 1-based. update sets a value: add val - nums[i], not val.

Tomorrow

Laptop charged, internet tested with a hotspot as backup, a quiet room, water, a pen and paper. The full checklist: the day before and the day of.

You don't need to know everything. You need to think out loud, start simple, and keep going. You have practised exactly that. Bas, ab so jao.