Part 15 · Lesson 60 · read
Your Revision Plan
A cheat sheet to spot patterns, a week-by-week plan and a checklist to test your memory.
On this page
How to use this lesson
You have 59 lessons behind you. The risk now is not that you lack knowledge. The risk is that the knowledge is spread over many pages, and when you feel pressure you cannot find the right one. Think of a cupboard with many drawers. This lesson is the label on each drawer, plus a schedule that helps you keep using them.
Read the cheat sheet once now. Then use it the way it was made: start from the words of a problem, find the row that sounds like it, and go to that lesson. The last part of this page has five mock interviews. In each one you must name the pattern before you see any code. Seeing the pattern is most of what an interview tests.
Constraints tell you the target speed
Before you choose a pattern, look at the size limits in the problem (lesson 12). A simple rule of thumb says a computer does about 10⁸ (100 million) simple steps in one second. So the biggest allowed input tells you how much work you can afford for each element. Use it as a hint, not as a strict law.
| Constraint | What is probably expected | Target |
|---|---|---|
| n up to about 20 | Try every possibility: subsets, permutations, backtracking (try, undo, try again) | O(2ⁿ) or O(n!) |
| n up to about 500 | Three loops inside each other are still fine | O(n³) |
| n up to about 5,000 | Two loops inside each other are fine | O(n²) |
| n up to 100,000 or 1,000,000 | Sort, heap, binary search, or one pass with a Map | O(n log n) or O(n) |
| n up to about 10¹² (a very large number) | Maths. A loop up to √n (about 10⁶ steps) is fine, a loop that runs n times is too slow | O(√n) |
| n up to 10¹⁸ | Maths or binary search. Even √n (10⁹ steps) is too slow here | O(log n) |
Example: “n ≤ 100,000, find a pair with a given sum” rules out two loops inside each other (10 billion steps). It points to a Map or to sorting.
The pattern cheat sheet
Every table has the same four columns. Each technique name is explained in the lesson you can click, so use the table to find the lesson, not to learn the term. The first is the wording you will see. The second is the technique it points to. The third is the lesson (click the number). The fourth is the usual time and memory. In a graph, V is the number of vertices (points) and E is the number of edges (links). R × C is a grid with R rows and C columns. h is the height of a tree. Together, the tables cover every lesson from 1 to 60.
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Predict or trace what some code prints | Dry run: a table with one column per variable | 1 | — |
| Store a value, convert between text and numbers, remainder and whole division | Variables, operators, % and Math.floor | 2 | O(1) |
| Different answer for different cases (even or odd, leap year, boundaries) | if / else-if, && and ||, test the boundary values | 3 | O(1) |
| Do something n times; sum, product, count; Fizz Buzz | for loop with an accumulator | 4 | O(n) time, O(1) space |
| Take a number apart digit by digit; repeat until a condition changes | while loop with n % 10 and Math.floor(n / 10) | 5 | O(digits) = O(log n) |
| Print a shape; count pairs; go through a grid | Nested loops: rows outside, columns inside | 6 | O(n²) |
| Package logic; answer must be returned, not printed | Functions, early return, helper functions | 7 | — |
| A list of values; running total, largest, search | Array loop: accumulate, best so far, count, search | 8 | O(n) |
| Characters of a text; palindrome; reverse | String as an array of characters; build a new string | 9 | O(n) |
| Count items, remove duplicates, look something up by name | Map for counts, Set for "seen" | 10 | O(n) average |
| Unclear statement or too many details | Inputs, outputs, constraints, examples, edge cases, then code | 11 | — |
| "How fast must it be?" | Count the steps; read the constraints (table above) | 12 | — |
| Divisors, primes, gcd, "modulo 10⁹+7", x to the power n | √n loops, sieve, Euclid, fast exponentiation | 13 | O(√n); sieve O(n log log n); gcd and power O(log n) |
| The problem contains a smaller copy of itself | Recursion: base case plus a smaller call | 14 | O(depth) stack space |
| "How many times does each value appear?" | Counting array (fixed range) or Map | 15 | O(n) time |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Sort a small list and explain how; nearly sorted data | Selection, bubble or insertion sort (insertion is O(n) on nearly sorted input) | 16 | O(n²) time, O(1) space |
| Sort with a guaranteed O(n log n); merge two sorted lists; count inversions | Merge sort (divide, sort halves, merge) | 17 | O(n log n) time, O(n) space |
| k-th largest or smallest; partition around a value; sort numbers or objects in JavaScript | Quickselect, quick sort, .sort with a comparator | 18 | Quickselect O(n) average; .sort O(n log n) |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| In place: remove, rotate, move zeroes, merge sorted | Read pointer and write pointer; reverse in three steps | 19 | O(n) time, O(1) space |
| Sum of a range, many range queries, product except self, "subarray sums to k" | Prefix sums (plus a Map of earlier prefix sums) | 20 | O(n) to build, O(1) per query |
| Sorted array and a pair; reverse; remove duplicates; triplets; container with most water | Two pointers, from both ends or in the same direction | 21 | O(n); 3Sum O(n²) |
| Maximum sum or average of every block of exactly k | Fixed sliding window: add the new, drop the old | 22 | O(n) time, O(1) space |
| Longest or shortest contiguous part with a condition; "at most k distinct" | Variable sliding window: grow right, shrink left | 23 | O(n) time |
| Maximum sum of a contiguous subarray; best day to buy and sell | Kadane: best ending here, best overall | 24 | O(n) time, O(1) space |
| Grid: transpose, rotate, spiral, set zeroes, sorted matrix search | Index arithmetic on rows and columns; layers | 25 | O(R × C) |
| Find a pair or an earlier value that matches; duplicates within distance k; longest consecutive run | Hash Map or Set of what you have seen | 26 | O(n) time, O(n) space |
| Anagrams, most frequent, majority element, isomorphic strings | Frequency map; a good key; bucket idea; Boyer–Moore vote | 27 | O(n) (sorting each key adds a log) |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Sorted input, or "find in O(log n)"; first or last position; rotated sorted array | Binary search with a template and lower or upper bound | 28 | O(log n) time |
| "Minimum … such that it still works" or "maximise the smallest"; the answer is a number in a range | Binary search on the answer plus a feasibility check | 29 | O(n log range) |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Palindromes, common prefix, Roman numerals, compress, rotate | Two pointers, expand around the centre, scan with a pointer | 30 | O(n); longest palindrome O(n²) |
| Substring with no repeats, replace at most k, permutation or anagram of a pattern, minimum window | String sliding window with a count map | 31 | O(n) time, O(alphabet) space |
| Calls that branch; fast power; the work repeats | Draw the recursion tree; count its nodes | 32 | Fibonacci tree O(2ⁿ) before memoisation |
| "All subsets, permutations, combinations" | Pick or skip; swap or use a used-array | 33 | O(2ⁿ × n); permutations O(n! × n) |
| "All ways" under rules: combination sum, partitions, word search, N-Queens | Backtracking: choose, explore, undo | 34 | Exponential; pruning helps |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Nodes and pointers; insert or delete in a list | Linked list with a dummy head | 35 | O(1) at the head, O(n) to find |
| Reverse a list or part of it; middle; is it a palindrome; is there a cycle | Three-pointer reversal; fast and slow pointers | 36 | O(n) time, O(1) space |
| Merge sorted lists; where a cycle starts; n-th from the end; add two numbers; intersection | Dummy head; gap pointers; Floyd's algorithm | 37 | O(n) time |
| Matching brackets, undo, nested structure, evaluate an expression, decode | Stack (last in, first out) | 38 | O(n) time, O(n) space |
| First in, first out; queue from stacks; sliding window maximum | Queue with a head index; deque of indices | 39 | O(n) total |
| "Next greater or smaller", days until warmer, histogram, trapped water | Monotonic stack | 40 | O(n): each item pushed and popped once |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Visit every node in an order; depth; invert; same tree | Preorder, inorder, postorder with recursion or a stack | 41 | O(n) time, O(h) space |
| Level by level; right side view; zigzag; minimum depth | BFS with a queue, one level per round | 42 | O(n) time, O(width) space |
| Height, balanced, diameter, path sum, maximum path sum, symmetric | DFS that returns a value up the tree | 43 | O(n) time |
| Binary search tree: search, insert, delete, validate, k-th smallest | Use the left < node < right property; inorder is sorted | 44 | O(h): O(log n) balanced, O(n) skewed |
| Lowest common ancestor; rebuild a tree from traversals; serialise | Recursion on the shape; a Map of inorder positions | 45 | O(n) time |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| k-th largest, top k, k closest, merge k lists, running median | Heap (priority queue) of size k, or two heaps | 46 | O(n log k) time, O(k) space |
| Best choice now is also best overall: jump game, gas station, assign cookies | Greedy: choose locally, prove it never hurts | 47 | O(n), or O(n log n) with a sort |
| Overlapping ranges: merge, insert, fewest to remove, minimum arrows | Sort by start (or end), then one sweep | 48 | O(n log n) time |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Cities and roads, friends, dependencies, a grid of cells | Model it as a graph: adjacency list; cells as vertices | 49 | O(V + E) to build |
| Islands, regions, reachable?, flood fill, number of provinces, clone | DFS or BFS with a visited set | 50 | O(V + E); grid O(R × C) |
| Fewest steps or moves in an unweighted graph or grid; spreading from many sources | BFS (multi-source BFS: start with all sources in the queue) | 50, 52 | O(V + E) |
| Prerequisites, order the tasks, can all be completed, detect a cycle (directed) | Topological sort: Kahn's algorithm or DFS colours | 51 | O(V + E) |
| Cheapest or shortest route with weights; at most k stops | Dijkstra with a heap; Bellman–Ford for k limits | 52 | Dijkstra O((V + E) log V) |
| Are these two connected?; merge groups; redundant edge; connect everything at minimum cost | Union-find; Kruskal's minimum spanning tree | 53 | Almost O(1) per operation; Kruskal O(E log E) |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Count the ways, minimum cost or maximum value, and the same sub-problems keep coming back | Dynamic programming: define the state, memoise or tabulate | 54 | States × work per state |
| Choose or skip along a line: house robber, fewest coins, decode ways, word break, longest increasing subsequence | 1-D DP: dp[i] depends on earlier entries | 55 | O(n) to O(n × amount); LIS O(n²) |
| Grid paths, subset sum, knapsack, coin combinations | 2-D DP; roll the table to one row if you can | 56 | O(R × C); knapsack O(n × W) |
| Two strings: longest common subsequence, edit distance, palindromic subsequence | DP table indexed by prefixes of both strings | 57 | O(m × n) time |
| The wording says… | Technique | Lesson | Time / space |
|---|---|---|---|
| Prefix lookups, autocomplete, dictionary with wildcards | Trie (prefix tree) | 58 | O(length) per operation |
| Single number, power of two, count set bits, all subsets by bitmask | XOR, AND, shifts; n & (n - 1) | 58 | O(1) or O(bits) |
| The 45 minutes: how to behave, what to say, JavaScript traps | Clarify, examples, brute force, code, test, complexity | 59 | — |
| Which lesson to review and when | This lesson: cheat sheet, plan, spaced repetition | 60 | — |
An eight-week practice plan
The plan assumes about 90 minutes on five days a week, plus a longer session at the weekend. Read a lesson, redo its examples without looking, then solve a few problems. The total is about 100 LeetCode problems. This is realistic, and it lets you see every pattern in this series more than once. You do not need 500 problems. You need to practise the same few patterns until they feel automatic.
| Week | Lessons | Focus | Problems | Suggested LeetCode numbers (all appear in the lessons) |
|---|---|---|---|---|
| 1 | Lessons 11, 12, 13, 14, 15, 16, 17, 18. Skim lessons 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 only if anything feels shaky. | Reading problems, Big-O, hashing basics, sorting | 10 | 217, 242, 268, 1512, 349, 283, 26, 88, 977, 75 |
| 2 | Lessons 19, 20, 21, 22, 23, 24, 25 | Prefix sums, two pointers, windows, Kadane, matrices | 14 | 189, 724, 238, 560, 167, 15, 11, 643, 209, 3, 53, 121, 54, 48 |
| 3 | Lessons 26, 27, 28, 29, 30, 31 | Hash patterns, binary search, strings | 14 | 128, 49, 347, 169, 704, 34, 33, 153, 875, 1011, 5, 424, 567, 438 |
| 4 | Lessons 32, 33, 34, 35, 36, 37 | Recursion, backtracking, linked lists | 12 | 78, 46, 39, 79, 131, 206, 876, 141, 21, 142, 19, 2 |
| 5 | Lessons 38, 39, 40, 41, 42, 43, 44, 45 | Stacks, queues, monotonic stack, trees, BSTs, LCA | 14 | 20, 155, 150, 739, 84, 104, 102, 199, 543, 124, 98, 230, 236, 105 |
| 6 | Lessons 46, 47, 48, 49, 50, 51, 52, 53 | Heaps, greedy, intervals, graphs, shortest paths, union-find | 14 | 703, 973, 23, 55, 134, 56, 435, 200, 994, 133, 207, 743, 547, 684 |
| 7 | Lessons 54, 55, 56, 57, 58 | Dynamic programming, tries, bits | 14 | 70, 746, 198, 213, 322, 91, 139, 300, 62, 64, 416, 72, 1143, 208 |
| 8 | Lessons 59, 60, plus the weak spots in your mistake log | Timed mock interviews on problems you have not seen; review | 10 | Two mocks of 45 minutes, each on a mixed pair (one Easy, one Medium): 4 problems. Then 6 problems from your mistake log. |
Total: 10 + 14 + 14 + 12 + 14 + 14 + 14 + 10 = 102 problems. Mix easy and medium problems. If a hard one takes a whole hour, mark it for later and move on.
A weekly routine that works: Monday to Wednesday, read a lesson and solve its easier problems. Thursday, solve a medium problem with a 30-minute timer and explain it out loud as in lesson 59. Friday, look at your log (next section). Weekend, do one longer session: the harder problem of the week, plus a fresh re-solve of two problems from earlier weeks.
Spaced repetition: 1, 3, 7 and 21 days
You forget a large part of what you learn within a few days, unless you pull it out of memory again. The trick is to do this just as the memory starts to fade. Do it soon at first, then with longer and longer gaps. This is called spaced repetition. A good schedule is 1, 3, 7 and 21 days after you solve a problem. It is easy to remember and it works well:
- 1 day: after one night's sleep the details are already blurry. A short re-solve now makes the memory strong.
- 3 days: by now you may have forgotten the trick, but you remember that there is one. That is the right level of difficulty.
- 7 days: a problem from a week ago should come back quickly. The time it takes shows what you really remember.
- 21 days: after a long gap, solving it shows that it is in your long-term memory. If you pass, you are finished with this problem.
If you fail a review, do not worry. Put the problem back on the 1-day step. A review means solving the problem again from a blank page. It does not mean reading the solution again. The effort of remembering is what builds the memory.
| When | What you do | Why |
|---|---|---|
| Day 0 (Monday) | Solve it. Keep the solution closed if you can. | Write one line in the mistake log: the pattern and the key idea. |
| Day 1 (Tuesday) | First review: solve it again from a blank page, 10 minutes. | Memory fades fastest in the first day. This review catches it. |
| Day 3 (Thursday) | Second review: solve it again, then say the complexity out loud. | If you get stuck, the problem goes back to day 1. |
| Day 7 (next Monday) | Third review: solve it in half the time, and explain it out loud as in lesson 59. | Now it should feel like a habit you own. |
| Day 21 (three weeks later) | Final review: treat it as a new interview question. | If you pass, you are finished with this problem. If you fail, start the steps again. |
The schedule is simple, so you can write it as code. This function turns the date you solved a problem into its four review dates:
// Given the day you solved a problem, when should you look at it again? Dates are plain "YYYY-MM-DD" text.const GAPS = [1, 3, 7, 21]; // days after solvingfunction addDays(isoDate, days) { const d = new Date(isoDate + "T00:00:00Z"); // the Z means UTC, so time zones cannot shift the date d.setUTCDate(d.getUTCDate() + days); return d.toISOString().slice(0, 10);}function reviewDates(solvedOn) { return GAPS.map((gap) => addDays(solvedOn, gap));}console.log(reviewDates("2026-10-05")); // [ '2026-10-06', '2026-10-08', '2026-10-12', '2026-10-26' ]console.log(reviewDates("2026-12-30")); // [ '2026-12-31', '2027-01-02', '2027-01-06', '2027-01-20' ]With a few more lines you get a small review list. Record each problem with the day you solved it and how many reviews you passed. Then ask which problems are due today. A paper notebook or a spreadsheet works just as well. What matters is that something tells you what to review, so you never have to decide.
// A mistake log as data: which problems are due for review today?const GAPS = [1, 3, 7, 21];function addDays(isoDate, days) { const d = new Date(isoDate + "T00:00:00Z"); d.setUTCDate(d.getUTCDate() + days); return d.toISOString().slice(0, 10);}function dueToday(log, today) { return log .filter((entry) => entry.reviewsDone < GAPS.length) // retired after the 21-day review .filter((entry) => addDays(entry.solvedOn, GAPS[entry.reviewsDone]) <= today) // "YYYY-MM-DD" text compares in date order .map((entry) => entry.problem);}const log = [ { problem: "560 Subarray Sum Equals K", pattern: "prefix sum + Map", solvedOn: "2026-10-05", reviewsDone: 0 }, { problem: "33 Search in Rotated Sorted Array", pattern: "binary search", solvedOn: "2026-10-05", reviewsDone: 1 }, { problem: "347 Top K Frequent Elements", pattern: "Map + bucket", solvedOn: "2026-10-07", reviewsDone: 0 }, { problem: "70 Climbing Stairs", pattern: "DP", solvedOn: "2026-09-01", reviewsDone: 4 },];console.log(dueToday(log, "2026-10-07")); // [ '560 Subarray Sum Equals K' ]console.log(dueToday(log, "2026-10-08")); // [ '560 Subarray Sum Equals K', '33 Search in Rotated Sorted Array', '347 Top K Frequent Elements' ]Keep a mistake log
Do not log the problems you solved easily. Log the ones that went wrong, and write why. Each entry takes less than a minute. It has seven fields: the date, the problem, the pattern, what went wrong, the type of mistake, the fix in one sentence, and the next review date. Here are three example rows:
| Date | Problem | Pattern | What went wrong | Category | Fix | Review |
|---|---|---|---|---|---|---|
| 10-05 | 560 Subarray Sum Equals K | Prefix sum + Map | Started with an empty map, so subarrays that start at index 0 were missed | Edge case | Seed the map with {0: 1} before the loop | 10-06 |
| 10-06 | 33 Search in Rotated Sorted Array | Binary search | Used < where <= was needed when comparing with the left end | Off-by-one | Write the range of the sorted half on paper and test with two elements | 10-07 |
| 10-07 | 347 Top K Frequent Elements | Map + bucket | Used a sort and said O(n), but it is O(n log n) | Complexity | Say the slowest step out loud before giving the total | 10-08 |
The category column is the most useful one. After a few weeks, count each category. Your top two are your real weak spots, and they are rarely the algorithms you were afraid of. Use these categories:
| Category | What it looks like | Remedy |
|---|---|---|
| Pattern | Did not see which technique the words pointed to. | Add the words to the cheat sheet, in your own words. |
| Edge case | Empty input, one element, duplicates, negatives, zero. | Add it to your own list of edge cases. |
| Off-by-one | Wrong use of < or <=, an index that is 1 too big or too small, or wrong loop limits. | Do a dry run on the smallest inputs (size 0, 1, 2). |
| Complexity | Got the time or memory wrong, or forgot the memory that recursion uses. | Do the analysis again, using the steps from lesson 59. |
| JavaScript | sort() default order, rows shared by fill, -0, NaN, shift(). | Add the trap to a short list and read the list again every week. |
| Communication | Went quiet, skipped the clarifying questions, did not test. | Record yourself in the next mock interview and listen to it. |
Mock interviews
Solving alone and solving while someone watches are two different skills. A mock interview is a practice interview. Start them in week 5 (one each week), and do two in week 8.
- Pick a problem you have not seen. Best is one that a friend picks, or a random one from a list sorted by difficulty. Choose one Medium problem, or an Easy one as a warm-up followed by a Medium one.
- Set a 45-minute timer and follow the steps from lesson 59: clarify, examples, brute force, code, test, complexity.
- Talk out loud the whole time. If you have no partner, speak to a rubber duck (a toy you explain things to) or record yourself. Then listen for silences and filler words like “um”.
- Write in a plain editor with no autocomplete and no running, the way many interviews are done. Do a dry run by hand instead of running the code.
- Score yourself on four things: Did I ask clarifying questions? Did I say a brute force? Did I test with an edge case? Did I give the complexities without being asked?
- Afterwards, add anything that went wrong to the mistake log. Solve the problem again the next day.
Mock interviews: spot the pattern first
These five use a different order from the usual one. For each one, read only the problem and write down the pattern, the complexity you are aiming for, and the first question you would ask. Then open the solutions. The green box at the end of each one is a script of what to say. It starts with the moment you see the pattern, and then goes through the plan, the code, the test and the complexity.
Given an array of integers nums (it may contain negative numbers and zeros) and an integer k, return the total number of contiguous subarrays (pieces with no gaps) whose sum equals k.
Hint 1
Hint 2
prefix[j] - prefix[i]. For a fixed j, which earlier prefix value are you looking for?Hint 3
Show all 2 solutions with explanations
For each start index, move the end one step at a time and keep a running sum. Add 1 to the count each time the sum equals k.
function subarraySum(nums, k) { let count = 0; for (let start = 0; start < nums.length; start++) { let sum = 0; for (let end = start; end < nums.length; end++) { sum += nums[end]; if (sum === k) count++; // do not stop: later elements may bring the sum back to k } } return count;}console.log(subarraySum([1, 1, 1], 2)); // 2console.log(subarraySum([1, 2, 3], 3)); // 2console.log(subarraySum([1, -1, 0], 0)); // 3O(n²) time, O(1) memory. Do not stop at the first match. With negatives and zeros, a longer subarray can also add up to k.
Keep a running total called prefix. A subarray that ends here adds up to k exactly when some earlier prefix equals prefix - k. Store how many times each prefix has appeared. Start the Map with prefix 0 appearing once (the empty start).
function subarraySum(nums, k) { const seen = new Map([[0, 1]]); // the empty prefix, so subarrays starting at index 0 are counted let prefix = 0, count = 0; for (const x of nums) { prefix += x; count += seen.get(prefix - k) ?? 0; // every earlier prefix of this value starts a valid subarray seen.set(prefix, (seen.get(prefix) ?? 0) + 1); } return count;}console.log(subarraySum([1, 1, 1], 2)); // 2console.log(subarraySum([1, 2, 3], 3)); // 2console.log(subarraySum([1, -1, 0], 0)); // 3O(n) time, O(n) memory. Dry run (follow the code by hand) on [1,-1,0], k = 0. The Map starts as {0:1}. x = 1: prefix 1, look up 1 → 0 found, store 1. x = -1: prefix 0, look up 0 → 1 found (count is 1), store 0 (it has now appeared twice). x = 0: prefix 0, look up 0 → 2 found (count is 3). The answer is 3.
Spot the pattern (from the words only). "Contiguous plus sum equals k makes me think of two ideas: a sliding window, or prefix sums. A window works when adding an element can only make the sum bigger, because then I know when to shrink it. This problem allows negative numbers, so that breaks and I cannot use a window. Also, I must count all such subarrays, and not find the longest one. That fits prefix sums with a hash map, as in lesson 20."
Clarify. "Can the numbers be negative or zero? Is the answer small enough for a normal number? How long can the array be? Is an empty subarray counted?" (Suppose the answers are: yes to negatives and zeros, up to 20,000 elements, and subarrays cannot be empty.)
Plan. "Brute force: try all pairs of start and end with a running sum. That is O(n²). It would pass for 20,000, but I can do better. A subarray from i+1 to j has the sum prefix[j] minus prefix[i]. So for each j I need the number of earlier prefixes equal to prefix[j] minus k. A map from prefix value to count gives me that in O(1)."
Code and test. "The map starts with 0 mapped to 1. This stands for the empty prefix, so a subarray that starts at index 0 is found. For each element I update the prefix, add the count for prefix minus k, and then record the prefix. I do the lookup before the store, so a subarray cannot be empty. Test on 1, -1, 0 with k = 0: the count goes 0, then 1, then 3. And 3 is the expected answer."
Complexity. "O(n) time and O(n) memory for the map. A window would use O(1) memory, but it would be wrong with negatives." (LeetCode 560.)
Trees stand in a row, and fruits[i] is the type of fruit on tree i. You pick fruit from a run of trees next to each other. You have only two baskets, and each basket holds one type. Return the largest number of fruits you can pick.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
For each start tree, walk to the right and keep the different types in a Set. Stop when a third type appears. Keep the longest stretch.
function totalFruit(fruits) { let best = 0; for (let start = 0; start < fruits.length; start++) { const kinds = new Set(); let end = start; while (end < fruits.length) { kinds.add(fruits[end]); if (kinds.size > 2) break; end++; } best = Math.max(best, end - start); } return best;}console.log(totalFruit([1, 2, 1])); // 3console.log(totalFruit([0, 1, 2, 2])); // 3console.log(totalFruit([1, 2, 3, 2, 2])); // 4console.log(totalFruit([])); // 0O(n²) time in the worst case (a long run of two types), O(1) memory because the Set never holds more than 3 values. It is correct, but it repeats a lot of work.
Move the right edge forward. Keep a Map from type to count for the window. When the Map has more than two types, move the left edge to the right. Lower the counts, and delete a type when its count reaches zero. After each step the window is valid, so record its length.
function totalFruit(fruits) { const counts = new Map(); // type -> how many in the window let left = 0, best = 0; for (let right = 0; right < fruits.length; right++) { counts.set(fruits[right], (counts.get(fruits[right]) ?? 0) + 1); while (counts.size > 2) { // too many kinds: shrink from the left const type = fruits[left]; counts.set(type, counts.get(type) - 1); if (counts.get(type) === 0) counts.delete(type); left++; } best = Math.max(best, right - left + 1); } return best;}console.log(totalFruit([1, 2, 1])); // 3console.log(totalFruit([0, 1, 2, 2])); // 3console.log(totalFruit([1, 2, 3, 2, 2])); // 4console.log(totalFruit([])); // 0O(n) time, because each index enters the window once and leaves at most once. O(1) memory, because the Map holds at most 3 types. The delete when a count reaches zero is important. Without it, counts.size would never go down.
Spot the pattern. "The words are longest, consecutive trees, and a limit on the number of different kinds: at most two. This is the sliding window with a changing size from lesson 23, with a count map to track the kinds. In the last problem, negative numbers broke the window. Here the window only holds counts that are zero or more, so it is safe to shrink it."
Clarify. "So I must pick a stretch with no gaps, and I can hold only two types? Can the array be empty? How long can it be? Are the types small integers?" (Suppose the answers are: empty returns 0, n up to 100,000.)
Plan. "Brute force: from every start, go on until a third type appears. That is O(n²), which is too slow for 100,000. The wasted work is that when I move the start by one, I scan almost the same stretch again. A window keeps its state instead. I grow it to the right. When there are three types, I shrink it from the left until there are two again."
Code and test. "I use a map of counts, and left starts at zero. For each right index I add the fruit. While the map has more than two entries, I remove one fruit from the left. When a count reaches zero, I delete the key. Then I update the best length. Test on 1, 2, 3, 2, 2: at index 2 the map has three types, so I remove the 1 and left becomes 1. The window 2, 3 has length 2. Then 2 and 2 make it 2, 3, 2, 2, with length 4. Edge case: empty input, the loop never runs, the answer is 0."
Complexity. "O(n) time, because left and right only move forward. O(1) memory, because the map never holds more than three entries." (LeetCode 904.)
A conveyor belt carries packages with the given weights. They must be shipped in order within days days. Each day the ship is loaded in order, and the load must not go over the ship's weight capacity. Return the smallest capacity that ships every package within days days.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Start at the heaviest package (a smaller capacity could never carry it) and test each capacity in turn. Load the packages in order. Start a new day when the next package does not fit. Then count the days.
function daysNeeded(weights, capacity) { let days = 1, load = 0; for (const w of weights) { if (load + w > capacity) { days++; load = 0; } // this package starts a new day load += w; } return days;}function shipWithinDays(weights, days) { const heaviest = Math.max(...weights); const total = weights.reduce((a, b) => a + b, 0); for (let capacity = heaviest; capacity <= total; capacity++) { if (daysNeeded(weights, capacity) <= days) return capacity; } return total;}console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)); // 15console.log(shipWithinDays([3, 2, 2, 4, 1, 4], 3)); // 6console.log(shipWithinDays([1, 2, 3, 1, 1], 4)); // 3There are up to (sum − max) capacities, and each one takes O(n) to test, so the time is O(n × sum). It is far too slow when the weights are large. But it gives the exact answer that the faster version must match.
The answer is between the heaviest package and the total weight. Check the middle capacity. If it ships on time, the answer is this capacity or a smaller one. If not, the answer must be bigger. Keep the smallest capacity that works.
function daysNeeded(weights, capacity) { let days = 1, load = 0; for (const w of weights) { if (load + w > capacity) { days++; load = 0; } load += w; } return days;}function shipWithinDays(weights, days) { let low = Math.max(...weights); // anything smaller cannot carry the heaviest package let high = weights.reduce((a, b) => a + b, 0); // everything in one day always works while (low < high) { const mid = Math.floor((low + high) / 2); if (daysNeeded(weights, mid) <= days) high = mid; // mid works: try smaller, but keep mid as a candidate else low = mid + 1; // mid fails: the answer is larger } return low;}console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)); // 15console.log(shipWithinDays([3, 2, 2, 4, 1, 4], 3)); // 6console.log(shipWithinDays([1, 2, 3, 1, 1], 4)); // 3O(n log(sum − max)) time, O(1) memory. There are about log₂(sum) rounds, and each round is an O(n) check. The loop uses low < high with high = mid, so the range always gets smaller. It ends with low === high, which is the smallest capacity that works.
Spot the pattern. "Smallest capacity so that something still works. The answer is itself a number in a range. If capacity c is enough, then c + 1 is also enough. When the answer changes from no to yes only once, it is a sign for binary search on the answer, lesson 29. The check is a simple loop that loads the packages and counts the days."
Clarify. "Must the packages be loaded in the given order, so that each day's load is a group with no gaps? Can a package be split? Can the number of days be more than the number of packages? How big are the weights and the array?" (Suppose the answers are: the order is fixed, no splitting, 1 ≤ days ≤ n ≤ 50,000, weights up to 500.)
Plan. "Brute force: try capacities from the heaviest package upward. That is O(n × sum). The key point is that the answer changes from no to yes only once, so I can cut the range in half each time. The lowest value is the heaviest single package. The highest value is the sum of all weights. For one capacity, I act it out: load in order and start a new day when the next package does not fit. If the days needed are within the limit, the capacity works."
Code and test. "I write a helper called daysNeeded, then the binary search with low < high. If mid works, I set high to mid, and not to mid minus 1, because mid itself may be the answer. Test on 3, 2, 2, 4, 1, 4 with 3 days: low is 4 and high is 16. mid 10 needs 2 days, so high becomes 10. mid 7 needs 3 days, so high becomes 7. mid 5 needs 4 days, so low becomes 6. mid 6 needs 3 days, so high becomes 6. Then I stop with 6. This matches the expected answer."
Complexity. "O(n log S), where S is the sum of the weights, and O(1) extra memory." (LeetCode 1011.)
You are given coin values coins (you have unlimited coins of each value) and a target amount. Return the fewest coins that add up to exactly amount, or -1 if it is impossible.
Hint 1
Hint 2
amount - c. What does that tell you about the answer for smaller amounts?Hint 3
best[a] be the fewest coins for amount a. Write it using best[a - coin].Show all 2 solutions with explanations
The fewest coins for a is 1 plus the smallest of the answers for a - c, over every coin c. Save the answer for each amount (this is called memoisation, or memoization: remembering a result so it is not worked out again), so you work it out only once.
function coinChange(coins, amount) { const memo = new Map(); function fewest(a) { if (a === 0) return 0; if (a < 0) return Infinity; // overshot: this path is impossible if (memo.has(a)) return memo.get(a); let best = Infinity; for (const c of coins) best = Math.min(best, 1 + fewest(a - c)); memo.set(a, best); return best; } const answer = fewest(amount); return answer === Infinity ? -1 : answer;}console.log(coinChange([1, 2, 5], 11)); // 3console.log(coinChange([2], 3)); // -1console.log(coinChange([1, 3, 4], 6)); // 2console.log(coinChange([1], 0)); // 0Without saved answers, the recursion tries an exponential number of paths, which means the work doubles again and again. With them, there are amount + 1 states and coins.length steps for each. That is O(amount × coins) time and O(amount) memory. The recursion can go as deep as the amount, which matters if the amount is large.
Build best[0..amount] from the smallest amount. best[0] = 0. Each other amount is 1 plus the smallest best[a - c] over the coins that fit.
function coinChange(coins, amount) { const best = new Array(amount + 1).fill(Infinity); best[0] = 0; // zero coins make amount zero for (let a = 1; a <= amount; a++) { for (const c of coins) { if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1); } } return best[amount] === Infinity ? -1 : best[amount];}console.log(coinChange([1, 2, 5], 11)); // 3console.log(coinChange([2], 3)); // -1console.log(coinChange([1, 3, 4], 6)); // 2console.log(coinChange([1], 0)); // 0The time is the same O(amount × coins) and the memory is O(amount). There is no recursion, so there is no risk of running out of call stack. Dry run on [1,3,4], 6: best = [0,1,2,1,1,2,2]. For a = 6: with coin 3 → best[3] + 1 = 2, with coin 4 → best[2] + 1 = 3, with coin 1 → best[5] + 1 = 3. The smallest is 2.
Spot the pattern. "Fewest coins, unlimited supply, an exact amount. We must find the best choice, and the same smaller amounts come up again and again. That looks like dynamic programming, lesson 55. First let me rule out the greedy method. With coins 1, 3, 4 and amount 6, taking the largest coin first gives 4 + 1 + 1, which is three coins. But 3 + 3 is only two. So greedy is wrong, and I need to try every coin."
Clarify. "Do I have unlimited coins of each value? What should I return when the amount cannot be made? What about amount zero? How big can the amount be?" (Suppose the answers are: unlimited, -1 if impossible, 0 for amount 0, amount up to 10,000.)
Plan. "Brute force: try every combination with recursion. That is exponential. The state is just the amount that is left, and the choice is the last coin. So best of a equals 1 plus the smallest best of a minus c, over the coins. There are only amount plus one different states. So I can either save the answers in the recursion (memoise), or fill a table from 0 upward. With amounts up to 10,000 I prefer the table, because deep recursion in JavaScript can be risky."
Code and test. "I make an array of size amount plus one, filled with Infinity, and best at zero is zero. For each amount and each coin that fits, I take the smallest value. At the end, if the result is still Infinity, I return -1. Test: coins 2, amount 3. best[1] is Infinity, best[2] is 1, and best[3] is best[1] plus 1, which is still Infinity, so the answer is -1. Coins 1, 3, 4 with 6 gives 2, as we followed earlier. Amount 0 gives 0."
Complexity. "Time O(amount × number of coins), memory O(amount)." (LeetCode 322.)
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Assume the answer is unique.
Hint 1
Hint 2
Hint 3
Show all 2 solutions with explanations
Count with a Map. Turn the entries into an array. Sort it by count, from biggest to smallest. Take the first k values.
function topKFrequent(nums, k) { const counts = new Map(); for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1); return [...counts.entries()] .sort((a, b) => b[1] - a[1]) // highest count first .slice(0, k) .map(([value]) => value);}console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [ 1, 2 ]console.log(topKFrequent([1], 1)); // [ 1 ]console.log(topKFrequent([4, 4, 4, 6, 6, 7, 7, 7, 7], 1)); // [ 7 ]O(n) to count, plus O(u log u) to sort the u different values. That is O(n log n) in the worst case. The memory is O(u). It is simple and often good enough.
A count is between 1 and n. Make an array of n + 1 buckets (small lists). Put each value in the bucket that has the same number as its count. Walk through the buckets from the highest to the lowest, and collect values until you have k.
function topKFrequent(nums, k) { const counts = new Map(); for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1); const buckets = Array.from({ length: nums.length + 1 }, () => []); // buckets[f] = values that appear f times for (const [value, f] of counts) buckets[f].push(value); const result = []; for (let f = buckets.length - 1; f >= 1 && result.length < k; f--) { for (const value of buckets[f]) { if (result.length < k) result.push(value); } } return result;}console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [ 1, 2 ]console.log(topKFrequent([1], 1)); // [ 1 ]console.log(topKFrequent([4, 4, 4, 6, 6, 7, 7, 7, 7], 1)); // [ 7 ]O(n) time and O(n) memory. Counting is one pass, bucketing visits each different value once, and the scan visits at most n + 1 buckets. Use Array.from with a function, so every bucket is its own separate array (lesson 59).
Spot the pattern. "This has two parts. How often does each value appear needs a frequency map, lesson 27. The k most is a top-k choice, which could use a heap (lesson 46), a sort, or buckets. I will say all three options with their costs, and then choose."
Clarify. "Is the answer unique, or what if two values tie at place k? Can I return the values in any order? Is k always at most the number of different values? How big is the array?" (Suppose the answers are: the answer is unique, any order, 1 ≤ k ≤ number of different values, n up to 100,000.)
Plan. "I count with a Map in O(n). Then I have three choices. Sorting the entries is O(u log u), where u is the number of different values. A min-heap of size k is O(u log k), which is good when k is small. Buckets numbered by frequency give O(n) overall, because no value can appear more than n times. I would first write the sort version, because it is the shortest and correct. I would mention the heap. Then I would offer the buckets if you want linear time."
Code and test. "For the bucket version I make n plus one empty arrays with Array.from, and not with fill, so the buckets do not share one array. Test on 1, 1, 1, 2, 2, 3 with k = 2. The counts are 1→3, 2→2, 3→1. So buckets[3] = [1], buckets[2] = [2], buckets[1] = [3]. I walk from the top, collect 1 and 2, and stop. A single element returns that element."
Complexity. "Buckets: O(n) time and O(n) memory. Sorting: O(n log n) time, O(u) memory. Heap: O(n log k) time, O(u) memory." (LeetCode 347.)
The final checklist
Read this list the night before an interview, and again just before it starts:
- I can write these from memory: binary search, BFS with a queue, DFS with recursion, a sliding window, a Map counter, and the merge of two sorted arrays.
- I know the time cost of the main tools: Map and Set lookups, sort, heap push and pop, BFS and DFS, binary search.
- For every problem I will clarify, give examples, say the brute force, then make it faster.
- I will use clear names, handle the special cases first, and keep the code short.
- I will do a dry run of one normal case and one edge case before I say I am done.
- I will say the time and memory cost, and what n is, without being asked.
- I know the JavaScript traps: sort() with a comparator, rows shared by fill, -0, NaN, 2^53, recursion depth, shift().
- If I am stuck for five minutes, I will say what I tried and ask for a hint.
- I have slept, I have eaten, and I have tested my setup (editor, camera, microphone, internet).
- I have two questions ready for the end.
Make it stick
- Without looking, say which technique each of these points to: “contiguous, with negatives, sums to k”, “minimum such that it still works”, “prerequisites”, “fewest coins”.
- Write the table “input limit → algorithm” from memory (n ≤ 20, 5,000, 100,000, 10¹⁸).
- Explain what 1, 3, 7 and 21 mean in your spaced repetition schedule. Say what to do when a review fails.
- Write the first entry of your mistake log, using the seven fields.
- Pick three problems that you have never seen, and name their patterns using the cheat sheet.
- Put your first mock interview in your calendar now, with a friend or with a timer.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
This is the last lesson of the series. From here, the work is practice, not reading. Here are three places to go next:
- The practice plan. Start at week 1 today, and put the first review dates in your calendar. Use the glossary when you forget a word, and the cheat sheet when a problem looks new.
- The other interview series on this site. Add to your preparation with System Design, Step by Step, JavaScript Core Mastery (the language behind every sample here), and the senior-engineer interview series: The Browser Contract, Backend in Depth, Scenario Debugging, Practical Design Problems and Senior Frontend Depth. When you are ready to put what you build online for real users, DevOps, From Zero follows the code into production (the live system).
- Real problems. The LeetCode lists in the lessons are your first source of problems. After them, pick a topic from the cheat sheet where your mistake log says you are weakest.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series