Introduction

A hands-on workbook for mastering data structures and algorithms from first principles. Each topic is a fill-in-yourself lecture page (concept → complexity → implementation walkthrough) paired with a Java skeleton, JUnit 5 tests, and a problem set. Everything ships blank: you implement the skeletons until the tests pass and grind the problems until the patterns are automatic.

🗺️ Roadmap

Work the modules in this order — each phase assumes the vocabulary of the ones above it. Inside a phase, order is flexible.

graph TD
    F["00 · Foundations"]
    F --> A["01 · Arrays"]
    F --> LL["02 · Linked Lists"]
    F --> SQ["03 · Stacks & Queues"]
    F --> HT["12 · Hash Tables"]
    A --> RC["04 · Recursion &<br/>Divide and Conqueror"]
    RC --> SS["05 · Searching & Sorting"]
    SS --> TR["06 · Trees"]
    TR --> HE["07 · Heaps"]
    TR --> TRI["16 · Tries"]
    TR --> SPT["08 · Spatial Trees"]
    HT --> DSU["09 · Disjoint Sets"]
    TR --> DSU
    DSU --> GF["10 · Graph Fundamentals"]
    GF --> GA["11 · Graph Algorithms"]
    SS --> DP["13 · Dynamic Programming"]
    SS --> GR["14 · Greedy"]
    TRI --> STR["15 · String Algorithms"]
    HE --> ADV["17 · Advanced"]
    GA --> ADV
    DP --> ADV

The path

How to work a module / topic

Best done with an AI coding agent as a tutor — see Learning with AI for the full setup. Per topic:

1. Learn it section by section — /teach <topic> (or “teach me <topic>”). The agent teaches one section, then stops until you understand it and have written that section’s notes in your own words.
2. Implement the code/ skeleton until the tests/concepts tests go green.
3. Grind the problem set — Foundational first (write them cold), then Applied (recognize the pattern, no peeking). They self-grade via tests, and LeetCode ones link out.
4. Drill more when you want extra reps — /extra-practice <module> generates fresh problems + stubs + tests in the same format.

The agent never hands over answers — it teaches, grades, and drills; you write every note, skeleton, and solution.

Pacing and Checkpoints

• ~1 module/week solo. Don’t advance until the Foundational problems are automatic; re-do a few old Applied ones weekly so earlier patterns stay sharp.
• After Phase 2 → most easy/medium array & sorting problems are comfortable.
• After Phase 4 → you can model and solve graph problems (a major interview gate).
• After Phase 5 → DP isn’t scary; you derive recurrences yourself.
• After Phase 7 → ready for competitive programming and the hardest interviews.

Learning This Workbook with AI

This workbook is meant to be worked with an AI coding agent — Claude Code, Cursor, Copilot, Codex, Gemini CLI, Windsurf, Aider — but in a very specific way. Used right, the AI is the fastest tutor you have ever had. Used wrong, it is the fastest way to learn nothing.

The one rule: the AI never gives you the answer. You write every note, implement every skeleton, and solve every problem yourself. The AI teaches the concepts, checks your work, and drills you — it never fills anything in.

This repo ships guard files that put any cooperating agent into tutor mode by default. Ask one to fill a note, implement a stub, or solve a problem and it will decline and coach you instead. The guard is for your benefit — don’t fight it.

Why so strict? Reading a handed-over solution feels like progress and produces almost none. Mastery comes from retrieval — pulling the answer out of your own head — and from practice. The AI’s job is to make retrieval and practice faster, not to skip them.

Setup — any agent works

1. Get your own copy — use “Use this template” (or fork/clone) so you have a repo to fill in.
2. Open it in your agent — the guard and teaching protocol load automatically. Every agent reads its own instructions file (CLAUDE.md, AGENTS.md, .cursor/rules/, GEMINI.md, …), all of which point at the canonical AGENTS.md. Zero setup.
3. (Optional) Turn on the tool layer — the repo ships a zero-dependency MCP server in mcp/. If your agent supports MCP, approve the dsa-workbook server when prompted (no install, nothing to run). It adds push-button teach_topic and generate_extra_practice tools. See mcp/README.md.

The same workflow reaches you three ways — you don’t choose, they just work:

• Instruction files — zero setup, every agent, plain English (“teach me stacks”).
• MCP tools — approve once, deterministic (real section lists, problem numbering).
• Claude Code skills — /teach, /extra-practice slash commands (Claude Code only).

The loop — repeat for every topic

1. Learn it — section by section

Ask your agent to teach the topic:

• Claude Code: /teach stacks
• Any other agent: “teach me stacks” — it follows the same protocol.

You get a gated lecture: the agent teaches one section, then stops — you explain it back and fill that section’s notes/ prompts in your own words before it continues. It grades what you wrote; it never writes it for you. That repeats, section by section, until the topic is done.

2. Write your notes

This happens inside the gate above. Each notes/ page is a list of italic questions; you answer them in your own words as you are taught. Don’t move on until a section’s notes hold up under the agent’s grading.

3. Implement the code

Read your own notes, fill the code/ skeleton, and run the module’s tests until they pass:

./gradlew test_03-stacks-queues

Skeletons throw UnsupportedOperationException until you implement them — red is the starting line, green is the goal.

4. Get your code reviewed

“Tests pass on my Stack — review it for edge cases and complexity I missed. Point them out, don’t fix them.”

Green tests are necessary, not sufficient.

5. Drill the problem set

Work the module’s PROBLEM_SET.md: Foundational problems cold (write them with no help), then Applied. They self-grade via tests, and LeetCode ones link out.

6. Get more reps

When you want extra practice — or you’re back for spaced review:

• Claude Code: /extra-practice stacks
• Any agent: “give me more problems on stacks”

It generates fresh problems into src/03-stacks-queues/extra-practice/ — markdown problems, stubs, and failing tests in the same format as the shipped set. Solve them until ./gradlew test_03-stacks-queues is green again.

7. Space it out

A few days later: “quiz me on what I struggled with last week.” Spaced repetition is what makes earlier topics stick.

One line: /teach (gated) → write notes → implement → review → drill → /extra-practice → space it out.

What the AI is for

Tutor mode is not “no help.” Lean on it for:

• Explaining concepts, complexity, and worked examples other than the assigned problem.
• Debugging your code — pointing at the bug, not rewriting it.
• Setup, Gradle, tooling, and navigating the repo.
• Generating extra practice on your weak spots.

Prompts worth keeping

The trap

The moment you type “just write it for me,” you have stopped learning. If you are tempted, that is exactly the rep that matters — ask for a hint, not the answer. The guard will nudge you back anyway.

Asymptotic Analysis

Why We Measure Growth, Not Wall-Clock Time

Argue why “this loop took 3ms on my laptop” is a useless way to compare algorithms — what variables (CPU, language, input) does wall-clock confound that asymptotics removes?

What “Input Size” Actually Means

Pin down \( n \) for different problems: array length, number of bits in an integer, vertices vs edges in a graph — how can choosing the wrong \( n \) make an analysis silently wrong?

Counting the Operations That Matter

Pick the dominant operation in a function and explain why you count it instead of every machine instruction — what gets folded into the constant factor, and why is that safe asymptotically?

The Cost Model You’re Assuming

Spell out the unit-cost (RAM) model: which operations you treat as \( O(1) \) — arithmetic, array indexing, comparisons — and where that assumption breaks (big integers, string compares, hashing).

Big-O as an Upper Bound

Describe Big-O as a “no worse than, up to a constant, for large enough \( n \)” promise, then connect that intuition to the \( \exists c, n_0 \) definition without proving anything.

Reading Big-O Off Real Code

Given nested loops and sequential blocks, walk through how you’d eyeball the Big-O — what do you do with constants, lower-order terms, and a loop that runs a fixed number of times?

The Role of \( c \) and \( n_0 \)

Explain what the witness constant \( c \) and threshold \( n_0 \) are doing — why is it fine that a “slower” Big-O algorithm wins for small \( n \)?

Omega and Theta: Lower and Tight Bounds

Explain what \( \Omega \) promises and what makes \( \Theta \) a “the growth is exactly this” statement — when can you NOT give a single \( \Theta \) for an algorithm?

Little-o and Little-omega

Contrast the strict \( o \) and \( \omega \) with \( O \) and \( \Omega \) using “strictly grows slower/faster” — how does the quantifier flip from “exists \( c \)” to “for all \( c \)”?

The Growth-Class Ladder

Order \( 1, \log n, n, n\log n, n^2, n^3, 2^n, n! \) and describe, for each rung, what code structure lands you there.

How One Class Dominates the Next

For an adjacent pair (say \( n\log n \) vs \( n^2 \)), describe the intuition for why the gap grows without bound — and roughly where the crossover sits in practice.

How Constants and Lower-Order Terms Vanish

Justify why \( 3n^2 + 100n + 7 \) collapses to \( n^2 \) — at what size does the \( n^2 \) term dominate, and why don’t we care about that crossover?

Combining Bounds: Sequential vs Nested Code

State the rule for adding costs (sequential blocks) vs multiplying them (nesting), and try it on a snippet with a loop after a doubly-nested loop — which term survives?

The Limit and Ratio Method

Show how \( \lim_{n\to\infty} f(n)/g(n) \) landing on \( 0 \), a positive constant, or \( \infty \) classifies the bound — when is this cleaner than juggling \( c \) and \( n_0 \) by hand?

Best, Worst, and Average Case

For one algorithm (try linear search or quicksort), predict all three and explain what input triggers each.

Which Case Does Big-O Describe?

Clear up the conflation: is Big-O the same as worst case? Explain how you can put a Big-O on the best case too.

Time Complexity

Define what you’re bounding when you say an algorithm is \( O(f(n)) \) in time — count of dominant operations as a function of \( n \), independent of hardware.

Per-Operation vs Whole-Algorithm Cost

Distinguish the cost of one method call from running the whole algorithm — when is it more honest to report per-operation cost (e.g. for a data structure’s API)?

Best / Average / Worst and Their Triggers

For a chosen algorithm, name the exact input shapes that trigger each case — why does average case usually require an assumption about the input distribution?

Why the Bound Holds (Intuition)

Take a doubly-nested loop and reason informally to \( O(n^2) \): how many times does the inner body run in total, and why does the summation come out quadratic?

Constant Factors That Actually Matter

Discuss when two \( O(n) \) algorithms differ enough in constant factor to matter — number of passes, cache behavior — and why Big-O hides this.

Space Complexity

Define space complexity as extra memory used as a function of \( n \) — what counts, and does the input array itself count?

Auxiliary Space vs Total Space

Separate “in-place” (\( O(1) \) auxiliary) from algorithms that allocate \( O(n) \) scratch — why is auxiliary space the number people usually quote?

Call-Stack Space: Iterative vs Recursive

Explain why recursion can cost \( O(\text{depth}) \) space with no explicit allocation — how deep is the stack for a balanced recursion vs a degenerate one, and how does converting to iteration change it?

Time–Space Tradeoffs

Give the intuition that you can buy speed with memory (memo tables, hashing) or save memory by recomputing — what question decides which side to favor?

Common Misconceptions and Traps

Collect classic mistakes: “Big-O means worst case”, “lower Big-O is always faster in practice”, reporting a loose \( O \) as tight, ignoring stack space — pick two and explain the fix.

Why This Is the Language of the Whole Course

Explain how every later topic gets summarized in this notation — what does it let you predict about an algorithm before you ever run it?

Implementation Walkthrough

Plan a tiny harness that empirically checks an asymptotic guess by operation-counting across growing \( n \) — sketch the shape of the code before writing it.

Setup and State

Decide what you’ll vary (the sizes of \( n \)) and what you’ll record (operation count or elapsed time) — what holds the results?

Generating Inputs per Size

Figure out how to build a representative input for each \( n \), and how to force best/worst case when you want to observe them.

The Measurement Loop

Work out how to run the algorithm under test for each \( n \) and capture its cost — where do you reset counters, and why warm up first if timing?

Inferring the Growth Class

Decide how you’d read the table of (\( n \), cost) pairs to guess the Big-O — what does the ratio of successive costs tell you when \( n \) doubles?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Recurrence Relations

What a Recurrence Is and Why Recursion Needs One

Explain why you can’t just “look at” a recursive function’s runtime the way you do a loop — what role does the recurrence play in describing the call structure?

Turning Code Into \( T(n) \)

Take a recursive routine and identify the three pieces: number of subcalls, subproblem size, and the non-recursive work — how does each map into the recurrence equation?

Reading the Three Parameters Off Code

For a given function, locate where \( a \) (branch factor), \( b \) (shrink factor), and \( f(n) \) (combine/split work) each live in the source — which is easiest to miscount?

Don’t Forget the Base Case

Explain why the base case matters for correctness even though it usually costs \( O(1) \) — when can a bad base case change the asymptotic answer?

The Recursion-Tree Method

Draw the tree for \( T(n) = 2T(n/2) + n \): label per-node cost, count nodes per level, and describe how summing levels gives the total.

Per-Level Cost and Tree Height

Reason about the two quantities that drive the total: how much work per level, and how many levels until the base case — what sets the height?

Where the Work Lives

Compare a tree with constant work per level, one dominated by the root, and one dominated by the leaves — how does the “shape of the work” predict the answer?

The Substitution Method

Describe the guess-then-verify-by-induction loop — what is the guess based on, and how do you check it holds for all \( n \)?

Why You Subtract a Lower-Order Term

Explain the classic trap where an off-by-a-constant guess fails the induction, and how strengthening the hypothesis (subtracting a term) fixes it.

The Master Theorem: The Cheat Sheet

State the comparison between \( n^{\log_b a} \) and \( f(n) \), and describe the three cases in words — which side “wins” in each?

Applying It Mechanically

Walk through extracting \( a \), \( b \), and \( f(n) \), then picking the case — what’s the most common extraction mistake?

When the Master Theorem Does NOT Apply

List what it can’t handle (non-polynomial gap, unequal subproblems, non-constant \( a \)) — how do you recognize each from the recurrence?

Common Divide-and-Conquer Recurrences

Match \( T(n)=2T(n/2)+n \), \( T(n)=2T(n/2)+1 \), and \( T(n)=T(n/2)+1 \) to algorithms and answers — what does each shape “feel” like?

Subtract-and-Conquer Recurrences

Contrast \( T(n)=T(n-1)+n \) with the divide-style ones — why does shrinking by a constant instead of a fraction blow up the cost?

Changing Variables to Tame a Recurrence

Show how a substitution like \( m = \log n \) can turn an awkward recurrence into a familiar linear one — what’s the signal this trick will help?

Time Complexity

Explain how solving the recurrence yields the time bound — why is the closed form of \( T(n) \) exactly the time complexity you quote?

Reading Time Off the Tree

Given the recursion tree, describe how total work = (work per level) × (number of levels) in the balanced case, and when that shortcut fails.

Best vs Worst Case via Different Recurrences

Show how the SAME algorithm can have two recurrences (e.g. quicksort’s balanced \( T(n/2) \) split vs degenerate \( T(n-1) \) split) — what input drives each?

Why the Bound Holds (Intuition)

For \( 2T(n/2)+n \), argue informally why the \( n \) work repeated over \( \log n \) levels gives \( n\log n \) — no formal induction required.

Space Complexity

Explain why a recurrence describes time, but the recursion ALSO costs memory — what determines that cost?

Call-Stack Depth

Reason about peak stack depth from the recurrence: for \( T(n/2) \)-style splits the depth is \( O(\log n) \), for \( T(n-1) \) it’s \( O(n) \) — why does the shrink factor set the depth?

Auxiliary Space Beyond the Stack

Separate stack space from arrays/buffers a divide-and-conquer routine allocates per call (e.g. mergesort’s merge buffer) — how do these combine into the total?

From Recurrence Back to Big-O

Explain how the closed form becomes the Big-O you quote — and why mergesort’s \( \Theta(n\log n) \) is “obvious” once you have the recurrence.

Implementation Walkthrough

Plan a recursive routine (e.g. mergesort) whose runtime you can analyze with a recurrence — sketch its parts before coding.

Setup and State

Decide the function signature and what bounds it receives — what’s the smallest input the recursion should stop on?

The Base Case

Work out the termination condition and why it must be reached on every path — what happens to \( T(n) \) if it’s wrong?

The Divide and Recurse Step

Figure out how the input is split into subproblems and how many recursive calls fire — this is the \( a \) and \( b \) of your recurrence.

The Combine Step

Determine the non-recursive work done per call (the \( f(n) \)) and where it happens relative to the recursion — does it dominate or get dominated?

Tracing the Recurrence to a Bound

Decide how you’d instrument the code (count calls, measure depth) to confirm the recurrence and bound you predicted.

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Proof Techniques

Why Algorithms Need Proofs, Not Just Tests

Explain what a proof of correctness buys you that a passing test suite never can — what category of bug do finite tests structurally miss?

Anatomy of a Claim

Break a statement like “for all sorted arrays, binary search returns the target if present” into its quantifier, hypothesis, and conclusion — what exactly must you establish?

Universal vs Existential Claims

Contrast “for all” and “there exists” claims — how does the burden of proof (and the way to disprove) flip between them?

Direct Proof

Describe chaining from hypothesis to conclusion using definitions and known facts — how do you decide the first thing to write down?

Proof by Contrapositive

Explain why proving \( \lnot Q \Rightarrow \lnot P \) settles \( P \Rightarrow Q \), and give the gut-check for when the contrapositive is the easier direction.

Proof by Contradiction

Describe assuming the negation and chasing it to an absurdity — what makes a claim a good candidate for this technique?

Contradiction vs Contrapositive

These feel similar — pin down the difference in what you assume and what you conclude, and when each reads more cleanly.

Mathematical Induction: The Engine

Lay out base case and inductive step as a “domino” argument — what is the inductive hypothesis actually letting you assume?

Weak vs Strong Induction

Compare assuming just \( k \) versus all of \( 1..k \) — describe a problem (proving a recursive routine correct) where you genuinely need the strong form.

Structural Induction

Explain induction over recursively-defined structures (trees, lists) — how does the base case become “the leaf/empty case” and the step become “assume children correct”?

Induction Pitfalls

Collect the classic failures: forgetting the base case, a base case that doesn’t connect to the step, assuming what you’re proving — pick one and show how it sneaks in.

Loop Invariants: Induction for Iterative Code

State the initialization, maintenance, and termination pattern — explain how it’s just induction over loop iterations in disguise.

Designing an Invariant

Given a loop (try insertion sort’s outer loop), describe how you’d find an invariant strong enough to imply correctness at termination.

Initialization, Maintenance, Termination

For your chosen loop, lay out what each of the three steps must show — which one most often reveals an off-by-one bug?

Counterexamples

Explain why a single counterexample destroys a “for all” claim, and how hunting for one is a debugging strategy before you commit to a proof.

Proof by Cases (Exhaustive Reasoning)

Describe when you must split into cases and what “exhaustive” requires — what’s the risk if your cases overlap or leave a gap?

Reasoning About Complexity Claims

Explain how proof technique underpins a complexity statement — when you assert an algorithm is \( O(n\log n) \), what is the implicit “for all inputs of size \( n \)” claim, and how would induction or an invariant justify it?

Time-Bound Arguments via Invariants

Show how a loop invariant about “work done so far” can prove a running-time bound, not just correctness — what quantity would the invariant track?

Space-Bound Arguments via Induction

Reason about proving a recursive routine never exceeds \( O(\log n) \) stack depth — how does induction on the recursion depth give that bound?

Connecting Proofs to Real Algorithm Analysis

Map each technique to where it shows up later: invariants for iterative algorithms, induction for recursion, contradiction for greedy/optimality, counterexamples for disproving a heuristic — which would you reach for first on a greedy proof?

Implementation Walkthrough

Plan code that DEMONSTRATES a proof technique — e.g. a function whose loop invariant you can assert and check at runtime — sketch its parts first.

Setup and State

Decide what state the loop maintains and what invariant you claim about it — where will you assert it?

The Main Loop and Its Invariant

Work out where in the loop body the invariant is temporarily broken and where it’s restored (maintenance) — what assertion catches a violation?

Termination and the Conclusion

Figure out the loop’s exit condition and what the invariant guarantees at that moment — how does it yield the correctness conclusion?

Turning the Argument Into a Test

Decide how you’d encode the invariant as runtime checks or property-based tests so the proof and the code agree.

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Logarithms And Summations

Logarithms as “How Many Times Can I Halve?”

Give the intuition that \( \log_2 n \) counts halvings (or doublings) — connect it to a number’s digit/bit count before any formula.

The Identities You Actually Use

List the product, quotient, power, and change-of-base rules, and flag the two or three that come up constantly — which one lets you swap bases freely?

Change of Base in Practice

Show how \( \log_b n = \log_k n / \log_k b \) turns any base into another times a constant — why does that constant disappear in Big-O?

Why the Log Base Doesn’t Matter in Big-O

Explain why \( \log_2 n \), \( \log_{10} n \), and \( \ln n \) are all \( \Theta(\log n) \) — what swallows the conversion constant, and when DOES the base matter (inside an exponent)?

Where Logs Come From in Code

Identify the two classic sources of a log factor: repeatedly halving the input, and tree height in a balanced structure — what do they share?

Logs in Divide and Conquer

Connect halving the problem size to \( \log_2 n \) levels of recursion — why is that the height of the recursion tree?

Logs from Balanced Tree Height

Reason about why a balanced binary tree on \( n \) nodes has height \( \Theta(\log n) \) — and why an unbalanced one degrades to \( \Theta(n) \).

Summations Show Up Whenever You Loop

Explain why analyzing a loop with varying per-iteration cost becomes a summation — give the translation from a for loop to \( \sum \).

Arithmetic Series

Recall the closed form for \( \sum_{i=1}^{n} i \) and describe where the \( n^2 \) in a nested loop secretly comes from this sum.

Geometric Series

Give the closed form for \( \sum_{i=0}^{n} r^i \) and the key insight: when \( r \neq 1 \), the sum is \( \Theta \) of its largest term — why does that make doubling/halving sums easy?

Increasing vs Decreasing Geometric

Contrast a sum dominated by its last term (growing) vs its first term (shrinking) — how does this explain why “last level dominates” in some recursion trees?

The Harmonic Series

Explain why \( \sum_{i=1}^{n} 1/i \approx \ln n \), and name an analysis (the cost of building something incrementally, or quicksort’s average case) where this \( \log \) sneaks in.

Bounding Sums With Integrals

Describe the picture: a monotone sum sandwiched between two integrals — how does this give a quick \( \Theta \) when no closed form is handy?

Telescoping Sums

Explain when consecutive terms cancel and only the endpoints survive — try spotting it in a sum that came from a recurrence.

Time Complexity

Explain why summations ARE the time-complexity calculation for loop-based code — what does \( \sum \) of per-iteration costs literally measure?

From Loop Shape to Summation

For a nested loop where the inner bound depends on the outer index, write the summation that counts inner-body executions — what closed form does it reduce to?

Why a Geometric Loop Is Often \( \Theta(n) \), Not \( \Theta(n\log n) \)

Reason about a loop whose work halves each round: why does the geometric sum collapse to a constant times the first term, keeping total work linear?

Why a Log Factor Appears

Take a loop that runs \( \log n \) times with \( O(n) \) work each (or \( n \) times with \( O(\log n) \) work) — explain how the product gives \( n\log n \).

Space Complexity

Connect logs and sums to memory: when does a structure need \( O(\log n) \) space and when \( O(n) \)?

Logarithmic Space from Recursion Depth

Explain why a balanced recursive routine holds \( O(\log n) \) frames on the stack — tie it back to the tree-height argument.

Summing Allocations Across a Build

Reason about the total memory when a structure grows in stages (e.g. doubling): why does the SUM of allocation sizes stay \( \Theta(n) \) rather than \( \Theta(n\log n) \)?

Putting It Together in Analysis

Take a doubly-nested loop where the inner bound depends on the outer index, set up the summation, and describe how you’d reduce it to a clean Big-O.

Implementation Walkthrough

Plan code that computes a series (e.g. partial sums of harmonic or geometric) and lets you observe its growth — sketch the parts first.

Setup and State

Decide what accumulator(s) you keep and what \( n \) you iterate to — what type avoids overflow or precision loss?

The Accumulation Loop

Work out the loop that adds each term — for a geometric series, how do you update the running term without recomputing a power each step?

Handling Edge Cases

Figure out the degenerate cases (\( r = 1 \), \( n = 0 \), the harmonic divide) and why each needs special thought.

Verifying Against the Closed Form

Decide how you’d compare the loop’s result to the closed-form formula to confirm your derivation.

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Amortized Analysis

The Problem: Worst-Case per Operation Lies

Explain why quoting the single most expensive operation overstates the real cost of a long sequence — what question does amortized analysis answer instead?

Amortized Is Not Average-Case

Clarify the difference: amortized makes no probability assumptions and holds for ANY sequence — why is this a stronger guarantee than “average over random inputs”?

The Mental Model: Spreading Cost Over Time

Describe the core intuition of “saving up” for an expensive operation across many cheap ones — what real-world analogy (prepaying, subscriptions) captures it?

The Aggregate Method

Explain the recipe: bound the total cost of \( n \) operations, then divide by \( n \) — what makes this the simplest method, and what’s its weakness?

Worked Setup: Dynamic Array Doubling

Set up the aggregate argument for \( n \) appends with table doubling — where do the expensive copies happen and what do the copy costs sum to?

The Accounting (Banker’s) Method

Describe assigning each operation a charge that may differ from its real cost, banking the surplus as credit — what invariant must the stored credit always satisfy?

Choosing the Right Charge

Explain how you pick a per-operation charge so credit never goes negative — what’s the trial-and-error feel of getting it right?

Mapping Credit to Real Objects

Reason about WHERE credit physically lives (e.g. on each array element) — why does tying credit to objects make the “never negative” check concrete?

The Potential Method

Define a potential function \( \Phi \) and the amortized cost \( \hat{c_i} = c_i + \Phi_i - \Phi_{i-1} \) — what properties must \( \Phi \) have for the bound to be valid?

Intuition for Potential

Explain \( \Phi \) as “stored energy” or “messiness” of the structure — how does an expensive operation correspond to a big drop in \( \Phi \)?

Picking \( \Phi \) for a Structure

Describe how you’d choose a potential for a dynamic array (relate it to how full the array is) — what makes a candidate \( \Phi \) work or fail?

Case Study: Dynamic Arrays (ArrayList Growth)

Walk through why each append is \( O(1) \) amortized despite occasional \( O(n) \) resizes — and why doubling, not adding a constant, is what makes it work.

Why Growth-by-Constant Breaks It

Reason about resizing by adding a fixed chunk instead of doubling — why does the amortized cost degrade to \( O(n) \) per append?

Case Study: A Stack With Multipop

Analyze a stack supporting push, pop, and multipop(k); argue why a sequence is cheap amortized even though one multipop can be \( O(n) \).

Case Study: A Binary Counter

Take incrementing a binary counter and show why the total bit-flips over \( n \) increments is \( O(n) \), making each increment \( O(1) \) amortized.

Time Complexity

Pin down what “amortized \( O(1) \)” actually claims about TIME over a sequence — and how it differs from a per-call worst-case bound.

Amortized vs Worst-Case per Operation

For the dynamic array, contrast the \( O(n) \) single-operation worst case with the \( O(1) \) amortized cost — which one matters for a tight loop of \( n \) appends, and why?

Why the Amortized Bound Holds (Intuition)

Argue informally why doubling makes the total copy work across \( n \) appends sum to \( O(n) \) — what geometric series is hiding in the resize costs?

When Amortized Isn’t Good Enough

Reason about a latency-sensitive setting where one \( O(n) \) resize spike is unacceptable even if amortized cost is \( O(1) \) — what does this push you toward (incremental resizing)?

Space Complexity

Explain the memory side of these structures — why does amortized time often come WITH some wasted space?

Wasted Space from Doubling

Reason about how much capacity sits unused right after (and right before) a resize — what’s the worst-case fraction of allocated space that’s empty?

Time–Space Tradeoff in the Growth Factor

Discuss how the growth factor (2× vs 1.5×) trades amortized time against wasted memory — why might a library pick a smaller factor?

Pitfalls and How to Sanity-Check

Collect common errors: confusing amortized with average, a potential that can go negative, forgetting initial potential — how would you catch each?

Where It Shows Up Later

Name structures whose advertised bounds are amortized (dynamic arrays, hash-table resizing, union-find, splay trees, Fibonacci heaps) — why does the field rely on this so heavily?

Implementation Walkthrough

Plan a dynamic array (or binary counter) from scratch so you can measure its amortized behavior — sketch the parts first.

Setup and State

Decide the fields you need: backing array, size, capacity — what’s the initial capacity and why does it matter for the first few appends?

The Append / Increment Operation

Work out the fast path that’s usually \( O(1) \) — what condition triggers the slow path?

The Resize / Carry Step

Figure out what the expensive branch does (allocate, copy, swap; or ripple-carry the bits) and why it runs rarely — how does its cost relate to the current size?

Instrumenting to Observe Amortization

Decide what to count (total copies or flips across \( n \) operations) and how you’d divide by \( n \) to confirm the amortized bound empirically.

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Foundations: Problem Set

Computational warm-ups on growth rates, operation counting, and the closed forms behind summations and recurrences. Every problem returns a single number — fill in the stub in problemset/ and make its test in tests/problemset/ pass.

Foundational

Problem 1: Nested Loop Operation Count

Description

A doubly nested loop runs the inner index j from the outer index i up to n (inclusive on i, exclusive on n):

for i in 0..n-1:
    for j in i..n-1:
        op()      // count this

Given an integer n, return the exact number of times op() executes. This is the triangular number n(n+1)/2.

Examples

Example 1:

Input:  n = 4
Output: 10

The inner loop runs 4, 3, 2, 1 times for i = 0, 1, 2, 3, summing to 10.

Example 2:

Input:  n = 1
Output: 1

Example 3:

Input:  n = 0
Output: 0

Constraints

• 0 <= n <= 100000

Problem 2: Geometric Series Sum

Description

Given a first term a, an integer ratio r, and a count k, return the sum of the geometric series a + a*r + a*r^2 + ... + a*r^(k-1), i.e. sum over i=0..k-1 of a*r^i. Handle the r = 1 case (the sum is a*k).

Examples

Example 1:

Input:  a = 1, r = 2, k = 4
Output: 15

1 + 2 + 4 + 8 = 15.

Example 2:

Input:  a = 3, r = 1, k = 5
Output: 15

With ratio 1 every term is 3, so the sum is 3 * 5 = 15.

Example 3:

Input:  a = 2, r = 3, k = 3
Output: 26

2 + 6 + 18 = 26.

Constraints

• 1 <= k <= 30
• 1 <= r <= 10
• the result fits in a 64-bit signed integer

Problem 3: Floor of Log Base 2

Description

Given an integer n >= 1, return floor(log2(n)) using only integer operations (no floating point). This equals the index of the highest set bit, or the number of times you can halve n before reaching 1.

Examples

Example 1:

Input:  n = 1
Output: 0

2^0 = 1 <= 1 < 2.

Example 2:

Input:  n = 8
Output: 3

2^3 = 8 <= 8 < 16.

Example 3:

Input:  n = 100
Output: 6

2^6 = 64 <= 100 < 128.

Constraints

• 1 <= n <= 2000000000

Problem 4: Harmonic Number

Description

Given an integer n >= 0, return the n-th harmonic number H_n = sum over i=1..n of 1/i as a double, with H_0 = 0.

Examples

Example 1:

Input:  n = 0
Output: 0.0

Example 2:

Input:  n = 1
Output: 1.0

Example 3:

Input:  n = 4
Output: 2.0833333333333335

1 + 1/2 + 1/3 + 1/4 = 25/12.

Constraints

• 0 <= n <= 1000000

Problem 5: Sum of First N Squares

Description

Given an integer n >= 0, return sum over i=1..n of i^2, which has the closed form n(n+1)(2n+1)/6.

Examples

Example 1:

Input:  n = 3
Output: 14

1 + 4 + 9 = 14.

Example 2:

Input:  n = 0
Output: 0

Example 3:

Input:  n = 5
Output: 55

1 + 4 + 9 + 16 + 25 = 55.

Constraints

• 0 <= n <= 1000000

Applied Problems

Problem 6: Dynamic Array Doubling Copy Cost

Description

A dynamic array starts with capacity 1 and doubles its capacity whenever a push would overflow. Each doubling copies all currently stored elements into the new buffer. Simulate n pushes and return the total number of element copies performed across all resizes.

Examples

Example 1:

Input:  n = 1
Output: 0

The first push fits in the initial capacity-1 buffer; no copy.

Example 2:

Input:  n = 4
Output: 3

Resizes happen at the 2nd, 3rd, and 5th push; for n = 4 we copy 1 + 2 = 3 elements (capacity grows 1 -> 2 -> 4).

Example 3:

Input:  n = 5
Output: 7

Capacity grows 1 -> 2 -> 4 -> 8, copying 1 + 2 + 4 = 7 elements.

Constraints

• 0 <= n <= 1000000

Problem 7: Sum of All Subarray Sums

Description

Given an array a of length m, return the sum of the sums of every contiguous subarray. Element a[i] appears in (i+1)*(m-i) subarrays, so the answer is sum over i of a[i]*(i+1)*(m-i) — computable in linear time.

Examples

Example 1:

Input:  a = [1, 2, 3]
Output: 20

Subarrays: [1]=1, [2]=2, [3]=3, [1,2]=3, [2,3]=5, [1,2,3]=6, totaling 20.

Example 2:

Input:  a = [4]
Output: 4

Example 3:

Input:  a = [1, 1]
Output: 4

[1]=1, [1]=1, [1,1]=2, totaling 4.

Constraints

• 1 <= m <= 100000
• the result fits in a 64-bit signed integer

Problem 8: Trailing Zeros of a Factorial

Description

Given an integer n >= 0, return the number of trailing zeros in n! in base 10. This equals floor(n/5) + floor(n/25) + floor(n/125) + ..., counting factors of 5.

Examples

Example 1:

Input:  n = 5
Output: 1

5! = 120 ends in one zero.

Example 2:

Input:  n = 25
Output: 6

floor(25/5) + floor(25/25) = 5 + 1 = 6.

Example 3:

Input:  n = 3
Output: 0

3! = 6 has no trailing zero.

Constraints

• 0 <= n <= 2000000000

Problem 9: Reduce a Fraction

Description

Given a numerator and a nonzero denominator, reduce the fraction to lowest terms using the Euclidean algorithm. Return a two-element array [num, den] with the sign normalized so that den is always positive.

Examples

Example 1:

Input:  numerator = 6, denominator = 8
Output: [3, 4]

Example 2:

Input:  numerator = -4, denominator = -2
Output: [2, 1]

Both negatives cancel; gcd(4, 2) = 2.

Example 3:

Input:  numerator = 3, denominator = -9
Output: [-1, 3]

The sign moves to the numerator.

Constraints

• -1000000000 <= numerator <= 1000000000
• 1 <= |denominator| <= 1000000000

Problem 10: Log Factorial Cost

Description

Given an integer n >= 0, return log2(n!) computed as sum over i=1..n of log2(i) as a double. This summation grows as Theta(n log n) and equals 0.0 for n = 0 or n = 1.

Examples

Example 1:

Input:  n = 1
Output: 0.0

log2(1) = 0.

Example 2:

Input:  n = 2
Output: 1.0

log2(1) + log2(2) = 0 + 1 = 1.

Example 3:

Input:  n = 4
Output: 4.584962500721156

log2(2) + log2(3) + log2(4) = 1 + 1.585 + 2.

Constraints

• 0 <= n <= 1000000

Problem 11: Recursion Tree Total Work

Description

For a power-of-two n, the recurrence T(n) = 2*T(n/2) + n builds a recursion tree where each level contributes exactly n work and there are log2(n) + 1 levels. Given such an n, return the total work summed across every node, which equals n*(log2(n) + 1).

Examples

Example 1:

Input:  n = 1
Output: 1

A single node of work 1; log2(1) + 1 = 1 level.

Example 2:

Input:  n = 8
Output: 32

8 * (3 + 1) = 32.

Example 3:

Input:  n = 4
Output: 12

4 * (2 + 1) = 12.

Constraints

• n is a power of two, 1 <= n <= 1073741824

Problem 12: Binary Counter Bit Flips

Description

Starting from zero, perform k increments on a binary counter. Each increment flips a run of trailing 1s to 0 and then sets one 0 to 1, flipping every bit it touches. Return the total number of bit flips performed across all k increments. The amortized cost approaches 2 flips per increment.

Examples

Example 1:

Input:  k = 1
Output: 1

0 -> 1 flips one bit.

Example 2:

Input:  k = 4
Output: 7

Flips: 1 + 2 + 1 + 3 = 7 to reach 100.

Example 3:

Input:  k = 8
Output: 15

Constraints

• 0 <= k <= 1000000000

Problem 13: Digit Power Summation

Description

For every integer from 1 to n, raise each of its decimal digits to the power p and accumulate. Return the total sum of all those digit-powers across the whole range.

Examples

Example 1:

Input:  n = 11, p = 2
Output: 288

Numbers 1..9 contribute their digit squared, summing to 1+4+9+…+81 = 285; 10 adds 1^2+0^2 = 1; 11 adds 1^2+1^2 = 2, for 288 total.

Example 2:

Input:  n = 9, p = 1
Output: 45

Each number 1..9 is a single digit; raising to power 1 leaves it unchanged, summing to 45.

Example 3:

Input:  n = 10, p = 2
Output: 286

1^2 + 2^2 + … + 9^2 = 285, plus 10 contributes 1^2 + 0^2 = 1, totaling 286.

Constraints

• 1 <= n <= 100000
• 1 <= p <= 6

Problem 14: Collatz Step Counter

Description

Starting at a positive integer n, repeatedly halve it when even or replace it with 3n + 1 when odd. Return the number of steps required to first reach 1.

Examples

Example 1:

Input:  n = 1
Output: 0

Already at 1.

Example 2:

Input:  n = 6
Output: 8

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 is 8 steps.

Example 3:

Input:  n = 7
Output: 16

Constraints

• 1 <= n <= 1000000

Problem 15: Triangular Layer Budget

Description

A triangular stack places i crates in layer i, so the first k layers need k(k+1)/2 crates. Given a crate budget, return the largest number of complete layers k such that k(k+1)/2 <= crates.

Examples

Example 1:

Input:  crates = 10
Output: 4

1+2+3+4 = 10 fits exactly; a 5th layer would need 15.

Example 2:

Input:  crates = 0
Output: 0

Example 3:

Input:  crates = 11
Output: 4

10 used by 4 layers; the 5th needs 15, which exceeds 11.

Constraints

• 0 <= crates <= 2000000000

Problem 16: Exponential Overtakes Polynomial

Description

Return the smallest positive integer n such that 2^n > n^k for a given exponent k. This shows concretely that 2^n eventually dominates any fixed polynomial n^k. Compare in a way that avoids overflow (e.g. logarithms or careful big-integer style growth).

Examples

Example 1:

Input:  k = 1
Output: 1

2^1 = 2 > 1^1 = 1.

Example 2:

Input:  k = 2
Output: 5

2^5 = 32 > 5^2 = 25, and no smaller n works (2^4 = 16 < 16 is not strictly greater).

Example 3:

Input:  k = 3
Output: 10

2^10 = 1024 > 10^3 = 1000.

Constraints

• 1 <= k <= 10

Problem 17: Tribonacci Modulo

Description

Evaluate the recurrence T(k) = T(k-1) + T(k-2) + T(k-3) with T(0) = 0, T(1) = 1, T(2) = 1, and return T(k) mod 1000000007. Iterate to stay within machine integers.

Examples

Example 1:

Input:  k = 0
Output: 0

Example 2:

Input:  k = 4
Output: 4

T(3) = 0+1+1 = 2, T(4) = 1+1+2 = 4.

Example 3:

Input:  k = 10
Output: 149

Constraints

• 0 <= k <= 1000000

Memory Model

What an Array Is & When to Reach for One

What problem does a fixed, indexable block of same-typed elements solve, and when is it the obvious first choice over a map or a list?

The Mental Model: One Labeled Ruler

Picture memory as a long ruler of numbered slots — what does it buy you to demand that all your data sit on one unbroken stretch of that ruler?

Contiguous Allocation

What does it mean for all elements to sit back-to-back in one block, and why must the runtime know the element size up front to allocate it?

Why Same-Typed Elements

Why does every slot having identical size make the indexing trick possible, and what would break if element sizes varied?

Stack vs Heap Placement

Where does the block physically come from for a local fixed array versus a heap-allocated one, and how does that affect lifetime?

The Base Pointer & Element Stride

Where does the array “live” as a single starting address, and what is the stride that separates one element’s start from the next?

Address Arithmetic

How is the address of element \( i \) computed from base and stride, and why is it pure multiply-and-add with no scanning?

Why Indexing Never “Looks Through” Earlier Elements

Why does the CPU never visit elements 0..i-1 to reach element \( i \) — what does it compute directly instead?

Zero-Based Indexing

Why does counting from 0 make the offset formula cleanest, and what does index 0 mean in terms of the base address?

Constant-Time Random Access

Why does reaching element one million cost the same as element 0, while a linked structure cannot promise that?

Cache Lines & Locality

How does a sequential walk ride the CPU cache line-by-line, and what makes a strided or random walk fall off a performance cliff even at the same Big-O?

Spatial vs Temporal Locality

What is the difference between reusing nearby addresses and reusing the same address, and which does a forward array scan exploit?

When Stride Hurts

Why can jumping by a large stride defeat the cache even though each individual access is still \( O(1) \)?

Fixed Size & Why Arrays Don’t Grow

Once the block is allocated, why can’t you append in place, and what does “the array is full” actually force you to do?

Bounds & Out-of-Range Access

What lives just past index \( n-1 \), who is responsible for the check, and how do Java’s checked access and C’s unchecked access differ?

The Invariant a Valid Index Must Hold

What condition must every index satisfy before use, and why is violating it either a thrown exception or silent corruption depending on the language?

Value vs Reference Element Types

What does each slot hold when elements are primitives versus objects, and where does the real object data actually live?

Time Complexity

Reason about the cost of every fundamental array operation and what makes each bound hold.

Index Read / Write

Why is access or assignment by index \( O(1) \) in all cases with no best/worst split — what single computation does it reduce to?

Search by Value

Why is finding an unknown value \( O(n) \) worst case, what is the best case (first slot) and the average case, and how would a sorted array change the picture?

Insert or Delete at an Index

Why does editing the middle cost \( O(n) \) from shifting, why is the front the worst case, and why is the tail the cheap case?

Why Constant Factors Still Matter

Two \( O(n) \) scans can differ widely in wall-clock time — how do cache behavior and stride change the hidden constant?

Space Complexity

Reason about how much memory an array occupies and what extra space its operations need.

The Array Itself

Why is the storage \( O(n) \) for \( n \) elements, and what fixed overhead (length field, header) rides along?

Operating In Place

Why do read, write, and search need only \( O(1) \) auxiliary space, and what does “in place” really mean here?

Iterative vs Recursive Traversal

Why does an iterative scan use \( O(1) \) extra space while a naive recursive walk can cost \( O(n) \) on the call stack — and what sits in those stack frames?

Common Bugs & Edge Cases

Off-by-one at the boundaries, the empty array, uninitialized/default values, signed-index mistakes, assuming a fixed array can grow — which trip people up most?

Real-World & Interview Uses

Where does the raw array hide under the hood — strings, buffers, matrices, hash-table backing stores — and which interview patterns lean on \( O(1) \) indexing?

Implementation Walkthrough

Before writing code, break the problem into the pieces you must get right.

State & Setup

What fields must your array wrapper hold (backing storage, length), and what must be true the instant it is constructed?

The Access Path

What does get(i) / set(i, v) do step by step, and where exactly does the bounds check belong relative to the offset computation?

The Traversal Loop

How is the scan loop structured, what are its start and stop conditions, and what invariant holds about every index already visited?

Termination & Return

How does each operation decide it is done, and what does it hand back (value, nothing, or a thrown error) in the success and out-of-bounds cases?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Dynamic Arrays

What It Is & When to Use It

Why wrap a fixed array in a structure that “grows,” and when do you pick this over a linked list or a plain array?

The Mental Model: A Resizable Wrapper

How is a dynamic array really a fixed array plus bookkeeping that lies about its size — what illusion does it maintain for the caller?

Capacity vs Size

What is the difference between how many elements exist and how many slots are allocated, and why must you track both as separate numbers?

The Core Invariant

What relationship between size and capacity must always hold, and what does each append or remove do to preserve it?

The Backing Array

How does the structure hold a private fixed array behind the scenes, and what stays the same when only size changes but capacity does not?

Append: The Central Operation

Why is push-to-end the operation that defines this structure, and what are its two distinct paths?

Append at the End (Room to Spare)

Walk the happy path — where does the new element go, what increments, and why is no copy involved?

Append When Full

What ordered sequence fires when capacity is exhausted: allocate a bigger block, copy the old elements, swap the reference, then write the new one?

Geometric Growth

Why multiply capacity by a factor (often 2 or 1.5) instead of adding a fixed chunk, and what would fixed-increment growth cost you over many appends?

Why a Factor, Not a Constant

What is the mental picture for why doubling makes resizes exponentially rarer as the array grows?

Insert & Delete at an Index

Why does inserting or removing in the middle force a shift of everything after it, which direction does each shift go, and when can a resize also be triggered?

Shrinking Policy

When should the backing array contract, why shrink at quarter-full rather than half-full, and how does that gap avoid grow/shrink thrashing at the boundary?

Iterator Invalidation & Mutation During Iteration

Why can a resize or a mid-loop removal leave a saved index, pointer, or iterator referring to the wrong slot or a freed block?

Time Complexity

Reason about per-operation cost, including why one operation needs the amortized lens.

Index Access & Update

Why are get and set flat \( O(1) \) just like a plain array, regardless of size?

Amortized Append

Why is a single append \( O(n) \) in the worst case (the resize) yet \( O(1) \) amortized — what is the intuition for spreading the rare expensive copy across the many cheap appends? State the bound; don’t formally derive it.

Insert / Delete at Index

Why is editing position \( k \) \( O(n - k) \), making the front \( O(n) \) and the tail \( O(1) \), and how does a triggered resize fold into that?

Search

Why is unsorted search \( O(n) \), and what changes if the contents are sorted?

Space Complexity

Reason about the memory the structure holds versus the data it stores.

Storage and Slack

Why is space \( O(n) \) yet potentially up to ~2x the live data because of unused capacity — and when is that slack at its worst?

Resize Transients

Why does a grow momentarily hold both the old and new backing arrays, and what is the peak extra space during the copy?

Auxiliary Space of Operations

Why do append, insert, and delete each need only \( O(1) \) auxiliary space beyond any resize copy?

Trade-offs vs Linked List

Random access and cache friendliness vs cheap middle insertion and no resize cost — when does each structure win?

Common Bugs & Edge Cases

Forgetting to null out removed slots (leaks), growing from capacity 0, integer overflow on the new capacity, copying size vs capacity elements — which bite hardest?

Real-World & Interview Uses

Where does this back the standard library (ArrayList, vector, Python list), and which interview patterns assume an \( O(1) \) amortized push?

Implementation Walkthrough

Before writing code, break the problem into the pieces you must get right.

State & Setup

What fields does the structure carry (backing array, size, capacity), and what should an empty or default-constructed instance look like?

The Grow Routine

What does the private resize do step by step — compute new capacity, allocate, copy each live element, reassign — and what must be true when it returns?

Append Threading Through Grow

How does add decide whether to call grow first, and in what order must the size increment and the element write happen?

Shifting for Insert and Delete

Which way do you copy elements to open or close a gap, and why does the copy direction matter to avoid overwriting data you still need?

Termination & Return

How does each operation signal success, bounds errors, or the new size, and what invariant must hold on every exit?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Multidimensional Arrays

What They Model & When to Use One

Grids, matrices, images, game boards — when is a 2D+ array the natural fit versus a map keyed by coordinates?

The Mental Model: A Shape Laid Over a Line

Memory is one-dimensional — what does it mean to impose a 2D “shape” on a single line of cells, and why is the shape just an interpretation of offsets?

Flattening a Grid into Linear Memory

What does it mean to “flatten” a rectangular grid into one unbroken run of cells, and why does flattening even happen under the hood?

Row-Major vs Column-Major Layout

Two ways to order the cells: walk a full row before dropping down, or walk a full column. Which does Java use, which do Fortran and NumPy default to?

Index Flattening Formula

How do you turn a coordinate \( (i, j) \) into one linear offset given the column count, and why does the number of columns appear in the formula?

Reading Back a Coordinate

Given a flat offset, how do you recover the row and column using divide and modulo, and which operand is the column count?

Strides for Higher Dimensions

Generalize the offset to 3D and beyond — what is a per-axis stride, and how do the strides chain so each index contributes its own multiplied term?

The Stride of Each Axis

Why does the innermost axis have stride 1 while each outer axis’s stride is the product of the sizes inside it?

Jagged (Array-of-Arrays) vs Rectangular

When are rows separate sub-arrays each with their own length and address versus one solid contiguous block? What does Java’s int[][] actually give you?

Memory Layout Consequences

Why does a jagged array scatter rows across the heap (extra pointer hop, worse locality) while a true rectangular block stays contiguous?

Traversal Order & Locality

Why can swapping the inner and outer loop over the same matrix change runtime dramatically, even though you touch every cell exactly once?

Matching Loop Order to Layout

Why should the innermost loop vary the axis with stride 1, and what cache penalty appears when it doesn’t?

Allocation & Initialization Patterns

How do you allocate a rectangular block, a jagged structure, or a single flat array you index by hand — and what are the default cell values in each?

Common Operations

Transpose, row/column sums, neighbor lookups on a board — how does each map onto the indexing scheme?

Time Complexity

Reason about the cost of grid operations in terms of rows R and columns C.

Cell Access

Why is reading or writing a single cell \( O(1) \) regardless of grid size, even with the flattening math?

Full Traversal

Why is visiting every cell \( O(R \cdot C) \), and why is that bound the same no matter the loop order even when wall-clock time differs?

Row Scan vs Column Scan

Why are both a single row scan \( O(C) \) and a single column scan \( O(R) \) in Big-O, yet one can be far slower in practice on a row-major layout?

Space Complexity

Reason about the memory a grid occupies and what extra space operations need.

Storing the Grid

Why is the data \( O(R \cdot C) \), and what extra overhead does a jagged array carry (one pointer and length per row) over a flat block?

In-Place vs Allocating Operations

Why can a row sum run in \( O(1) \) extra space while a transpose into a new grid needs \( O(R \cdot C) \), and when can transpose be done in place?

Recursive Grid Walks

Why can a recursive flood-fill or DFS over a grid use up to \( O(R \cdot C) \) call-stack space in the worst case?

Common Bugs & Edge Cases

Swapped \( i \) and \( j \), mismatched row lengths in a jagged array, off-by-one on the last row/column, assuming rectangularity that isn’t there.

Real-World & Interview Uses

Image buffers, matrices, dynamic-programming tables, grid/maze problems — which interview patterns live on a 2D array?

Implementation Walkthrough

Before writing code, break the problem into the pieces you must get right.

State & Setup

What does your structure store (a flat backing array plus row/column counts, or nested arrays), and what defines a valid newly-allocated grid?

The Coordinate-to-Offset Step

What does get(i, j) / set(i, j, v) compute, where do the two bounds checks go, and how does the offset formula appear in code?

The Nested Traversal

How are the outer and inner loops ordered, and what invariant holds about all cells already visited at any point in the walk?

Termination & Return

How does each operation finish, and what does it return or throw for a valid coordinate versus an out-of-range one?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Prefix & Suffix Sums and Products

What It’s For & Why It Matters

Why precompute cumulative totals once so that any range query becomes \( O(1) \) instead of re-scanning the subarray every time, and where do range queries dominate the workload?

The Core Idea

How does storing “the answer for every prefix” let you recover the answer for any interval by subtracting two stored values, turning repeated work into a single lookup?

The Mental Model

How do you picture the prefix-sum array as a running odometer, where the cost of a stretch of road is just the difference of two readings?

The Prefix-Sum Array

If \( P[i] \) is the sum of the first \( i \) elements, what does \( P \) let you compute, and why is the length usually \( n+1 \) with \( P[0] = 0 \)?

Building It

Why is each entry just the previous entry plus one new element, and why does that make construction a single left-to-right pass?

Range Sum in O(1)

Why does the sum of \( a[lo..hi] \) equal \( P[hi+1] - P[lo] \), and how does the \( P[0]=0 \) sentinel make the edge case \( lo = 0 \) just work?

Off-by-One Discipline

What goes wrong if you mix up inclusive vs. exclusive bounds, and how does fixing one convention (half-open) avoid the bugs?

Suffix Sums

What changes when you accumulate from the right instead of the left, and when is a suffix sum the natural tool rather than a prefix sum?

Prefix × Suffix Products

For “product of the array except self,” why does multiplying a prefix-product (everything before \( i \)) by a suffix-product (everything after \( i \)) give the answer without ever dividing?

Why Avoid Division

Why is the prefix·suffix approach preferable to “total product ÷ a[i],” especially when the array can contain a zero?

Difference Arrays (the Inverse Trick)

If prefix sums turn point values into range queries, why does a difference array do the opposite — turning many range updates into a single prefix-sum pass at the end?

One Update in O(1)

Why does adding delta at lo and subtracting it just past hi mark a whole range, and why does the final prefix-sum pass “spread” those marks back into actual values?

2-D Prefix Sums

How does inclusion–exclusion extend the idea to a grid so any axis-aligned rectangle sum is \( O(1) \), and why are there four terms in the query?

Building the Table

Why does each table cell combine the cell above, the cell to the left, and a subtracted overlap, and why is the table sized \( (R+1)\times(C+1) \)?

The Four-Corner Query

Why does a rectangle sum add two corners and subtract two, and which corner is the doubly-removed overlap that gets added back?

Implementation Walkthrough

Before writing code, decide each part.

Setup & Sizing

Why allocate \( n+1 \) (or \( (R+1)\times(C+1) \)) slots with a zero sentinel, and what invariant does \( P[0]=0 \) guarantee about every later entry?

The Build Loop

How does the single accumulation pass maintain “P[i] holds the sum of the first i elements” as it advances, and what is true of all entries to the left at each step?

The Query Step

How does a range or rectangle query reduce to a constant number of array reads and one subtraction (or inclusion–exclusion), with the bounds checks placed before the arithmetic?

Termination & Return

What does each operation return — a freshly built array/table from a build, a single number from a query — and what does it throw for an out-of-range interval?

Time Complexity

Separate the one-time build cost from the per-query cost.

Build Cost

Why is building the prefix array \( O(n) \) (or \( O(R \cdot C) \) in 2-D) — a single pass that touches each element once?

Query Cost

Why is each range or rectangle query \( O(1) \) regardless of how wide the interval is, since it reads only a fixed number of precomputed cells?

When the Trade Pays Off

Why does the up-front build only beat naive re-summing once you make enough queries, and how do you reason about the crossover point?

Space Complexity

Reason about the memory beyond the input.

The Stored Table

Why does the prefix array cost \( O(n) \) extra space (or \( O(R \cdot C) \) for a 2-D table), and what does that extra space buy you per query?

In-Place vs Allocating

When can a difference array or prefix pass be done in place over the input, and when must you allocate a separate \( n+1 \) array to keep the sentinel?

Common Bugs & Edge Cases

What breaks with integer overflow on large ranges (why long?), with the \( n+1 \) sizing, with an empty array, with a zero in product-except-self, or with forgetting the final prefix pass on a difference array?

Real-World & Interview Uses

Where do range-sum queries, “subarray with given sum,” running balances, image integral tables, and batch range-update problems rely on these techniques?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Arrays: Problem Set

Drill the core array techniques — two pointers, prefix sums, Kadane, matrix transforms, Boyer–Moore voting, and sliding windows. Foundational problems build the moves you should write cold; Applied Problems weave interview-style (LeetCode) and competitive-programming-style (Codeforces / Advent of Code / Codyssi) challenges, roughly easy to hard.

Foundational

Problem 1: Reverse In Place

LeetCode: 344. Reverse String

Description

You are given an int[] array. Reverse its elements in place using O(1) extra space — swap from both ends toward the middle — and return the same array reference.

Examples

Example 1:

Input:  [1, 2, 3, 4]
Output: [4, 3, 2, 1]

Two-pointer swaps: (1,4) then (2,3).

Example 2:

Input:  [1, 2, 3]
Output: [3, 2, 1]

Example 3:

Input:  []
Output: []

Constraints

• 0 <= n <= 10^5
• Must use O(1) extra space.

Problem 2: Rotate Array Left

LeetCode: 189. Rotate Array

Description

Rotate the array nums to the left by k positions, in place. k may exceed n, so reduce it modulo n first. The element at index i moves to index (i - k mod n + n) mod n.

Examples

Example 1:

Input:  nums = [1, 2, 3, 4, 5], k = 2
Output: [3, 4, 5, 1, 2]

The first two elements wrap around to the end.

Example 2:

Input:  nums = [1, 2, 3], k = 0
Output: [1, 2, 3]

Example 3:

Input:  nums = [1, 2, 3, 4], k = 6
Output: [3, 4, 1, 2]

6 mod 4 = 2.

Constraints

• 1 <= n <= 10^5
• 0 <= k <= 10^9

Problem 3: Two Sum II (Sorted)

LeetCode: 167. Two Sum II - Input Array Is Sorted

Description

Given a sorted (ascending) array a and a target, return the two 0-based indices [i, j] with i < j whose values sum to target. If no such pair exists, return [-1, -1]. Use the two-pointer technique in O(n).

Examples

Example 1:

Input:  a = [2, 7, 11, 15], target = 9
Output: [0, 1]

2 + 7 = 9.

Example 2:

Input:  a = [2, 3, 4], target = 6
Output: [0, 2]

Example 3:

Input:  a = [1, 2, 3], target = 100
Output: [-1, -1]

Constraints

• 2 <= n <= 10^4
• At most one valid pair.

Problem 4: Merge Sorted Arrays

LeetCode: 88. Merge Sorted Array

Description

Given two sorted (ascending) arrays a and b, merge them into a single new sorted array and return it. Use a two-pointer merge in O(a.length + b.length).

Examples

Example 1:

Input:  a = [1, 3, 5], b = [2, 4]
Output: [1, 2, 3, 4, 5]

Example 2:

Input:  a = [], b = [1, 2]
Output: [1, 2]

Example 3:

Input:  a = [1, 1, 2], b = [1, 3]
Output: [1, 1, 1, 2, 3]

Constraints

• 0 <= a.length, b.length <= 10^5

Problem 5: Maximum Subarray

LeetCode: 53. Maximum Subarray

Description

Return the maximum sum of any contiguous, non-empty subarray of a, using Kadane’s algorithm in O(n). At each index keep the best sum ending there: cur = max(a[i], cur + a[i]).

Examples

Example 1:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

The subarray [4, -1, 2, 1] sums to 6.

Example 2:

Input:  [-3, -1, -2]
Output: -1

All negative — the single largest element wins.

Example 3:

Input:  [5, 4, -1, 7, 8]
Output: 23

Constraints

• 1 <= n <= 10^5
• -10^4 <= a[i] <= 10^4

Problem 6: Remove Duplicates from Sorted Array

LeetCode: 26. Remove Duplicates from Sorted Array

Description

Given a sorted array, compact it in place so each value appears once, preserving order. Return the new logical length k; the first k slots must hold the unique values. Use a slow/fast two-pointer write index.

Examples

Example 1:

Input:  [0, 0, 1, 1, 2]
Output: 3

The array begins [0, 1, 2, ...].

Example 2:

Input:  [1, 1, 1]
Output: 1

Example 3:

Input:  [1, 2, 3]
Output: 3

Constraints

• 0 <= n <= 3 * 10^4
• Input is sorted ascending.

Applied Problems

Problem 7: Move Zeroes

LeetCode: 283. Move Zeroes

Description

Move all 0s in nums to the end while preserving the relative order of the non-zero elements. Do it in place with O(1) extra space, then return the array.

Examples

Example 1:

Input:  [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Example 2:

Input:  [0, 0, 1]
Output: [1, 0, 0]

Example 3:

Input:  [1, 2, 3]
Output: [1, 2, 3]

Constraints

• 1 <= n <= 10^4
• In place, O(1) extra space.

Problem 8: Majority Element

LeetCode: 169. Majority Element

Description

Return the element that appears more than n/2 times (guaranteed to exist). Use the Boyer–Moore voting algorithm in O(n) time and O(1) space: track a candidate and a count.

Examples

Example 1:

Input:  [3, 2, 3]
Output: 3

Example 2:

Input:  [2, 2, 1, 1, 1, 2, 2]
Output: 2

Example 3:

Input:  [7]
Output: 7

Constraints

• 1 <= n <= 5 * 10^4
• A majority element always exists.

Problem 9: Glacier Survey

Description

A drone records ice thickness t[i] over n days. A thaw streak is a maximal run of consecutive days where each day is strictly thinner than the previous one. Return the length of the longest thaw streak. A single day counts as a streak of length 1; an empty array returns 0.

Examples

Example 1:

Input:  [5, 3, 2, 4, 1]
Output: 3

The run 5, 3, 2 is strictly decreasing.

Example 2:

Input:  [1, 2, 3]
Output: 1

No two consecutive days decrease.

Example 3:

Input:  []
Output: 0

Constraints

• 0 <= n <= 10^5

Problem 10: Container With Most Water

LeetCode: 11. Container With Most Water

Description

Given vertical line heights h, find two lines that with the x-axis form a container holding the most water. Return the maximum area min(h[i], h[j]) * (j - i) over all pairs. Use two pointers in O(n).

Examples

Example 1:

Input:  [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

Lines at indices 1 and 8: min(8,7) * 7 = 49.

Example 2:

Input:  [1, 1]
Output: 1

Example 3:

Input:  [4, 3, 2, 1, 4]
Output: 16

Constraints

• 2 <= n <= 10^5
• 0 <= h[i] <= 10^4

Problem 11: Relay Towers

Description

n towers stand in a row with heights h[i]. Looking from the far left, a tower is visible if it is strictly taller than every tower before it (the first tower is always visible). Return the count of visible towers.

Examples

Example 1:

Input:  [3, 1, 4, 1, 5]
Output: 3

Towers 3, 4, 5 are each a new running maximum.

Example 2:

Input:  [5, 4, 3]
Output: 1

Example 3:

Input:  [1, 2, 3, 4]
Output: 4

Constraints

• 1 <= n <= 10^5

Problem 12: Best Time to Buy and Sell Stock

LeetCode: 121. Best Time to Buy and Sell Stock

Description

Given daily prices, return the maximum profit from buying on one day and selling on a strictly later day. If no profit is possible, return 0. Track the running minimum price in one O(n) pass.

Examples

Example 1:

Input:  [7, 1, 5, 3, 6, 4]
Output: 5

Buy at 1, sell at 6.

Example 2:

Input:  [7, 6, 4, 3, 1]
Output: 0

Prices only fall.

Example 3:

Input:  [2, 4, 1]
Output: 2

Constraints

• 1 <= n <= 10^5
• 0 <= prices[i] <= 10^4

Problem 13: Product of Array Except Self

LeetCode: 238. Product of Array Except Self

Description

Return an array out where out[i] is the product of all elements of a except a[i]. Do it without division in O(n) using prefix and suffix products.

Examples

Example 1:

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Example 2:

Input:  [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Example 3:

Input:  [2, 3]
Output: [3, 2]

Constraints

• 2 <= n <= 10^5
• The full product fits in a 64-bit integer.

Problem 14: Ledger Audit

Description

Given n daily balance changes d[i] and q range queries (l, r), return an array whose j-th entry is the net change over days l..r inclusive. Answer all queries in O(n + q) using a prefix-sum array.

Examples

Example 1:

Input:  d = [1, -2, 3, 4], queries = [[0,1], [1,3], [0,3]]
Output: [-1, 5, 6]

d[0..1] = -1, d[1..3] = 5, d[0..3] = 6.

Example 2:

Input:  d = [5], queries = [[0,0]]
Output: [5]

Example 3:

Input:  d = [2, 2, 2], queries = [[0,2], [1,1]]
Output: [6, 2]

Constraints

• 1 <= n, q <= 10^5
• 0 <= l <= r < n

Problem 15: Spiral Matrix

LeetCode: 54. Spiral Matrix

Description

Given an r x c matrix, return all its elements in clockwise spiral order, starting from the top-left. Walk right, down, left, up while shrinking the four boundaries.

Examples

Example 1:

Input:  [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Example 2:

Input:  [[1, 2], [3, 4]]
Output: [1, 2, 4, 3]

Example 3:

Input:  [[1, 2, 3, 4]]
Output: [1, 2, 3, 4]

Constraints

• 1 <= r, c <= 100

Problem 16: Caravan Fuel (Gas Station)

LeetCode: 134. Gas Station

Description

On a circular route of n stations, station i provides gas[i] fuel and driving to the next station burns cost[i]. Starting with an empty tank, return the index of the first station from which you can complete a full loop, or -1 if impossible. Solve in one O(n) pass.

Examples

Example 1:

Input:  gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3

Starting at station 3 completes the loop.

Example 2:

Input:  gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1

Example 3:

Input:  gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]
Output: 4

Constraints

• 1 <= n <= 10^5
• The answer is unique if it exists.

Problem 17: Rotate Image

LeetCode: 48. Rotate Image

Description

Rotate an n x n matrix 90° clockwise, in place, then return it. Standard approach: transpose the matrix, then reverse each row.

Examples

Example 1:

Input:  [[1, 2], [3, 4]]
Output: [[3, 1], [4, 2]]

Example 2:

Input:  [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Example 3:

Input:  [[1]]
Output: [[1]]

Constraints

• 1 <= n <= 20
• Rotate in place.

Problem 18: Seismic Peaks

Description

Given seismograph readings a[i], a peak is an index i with 0 < i < n-1 satisfying a[i-1] < a[i] > a[i+1]. Return the number of peaks (endpoints can never be peaks).

Examples

Example 1:

Input:  [1, 3, 2, 4, 1]
Output: 2

Peaks at index 1 (value 3) and index 3 (value 4).

Example 2:

Input:  [1, 2, 3]
Output: 0

Example 3:

Input:  [5, 1, 5, 1, 5]
Output: 1

Constraints

• 1 <= n <= 10^5

Problem 19: Find Pivot Index

LeetCode: 724. Find Pivot Index

Description

Return the leftmost pivot index i where the sum of elements strictly to its left equals the sum strictly to its right. If none exists, return -1. Use a total sum and a running left sum in O(n).

Examples

Example 1:

Input:  [1, 7, 3, 6, 5, 6]
Output: 3

Left of index 3 sums to 11; right of it sums to 11.

Example 2:

Input:  [1, 2, 3]
Output: -1

Example 3:

Input:  [2, 1, -1]
Output: 0

Left of index 0 is empty (0); right is 1 + (-1) = 0.

Constraints

• 1 <= n <= 10^4
• -1000 <= a[i] <= 1000

Problem 20: Report Repair

Description

From Advent of Code: given an expense report a of integers, find the two distinct entries that sum to target and return their product. Exactly one such pair exists. A hash set or two-pointer scan over the sorted array both work in O(n).

Examples

Example 1:

Input:  a = [1721, 979, 366, 299, 675, 1456], target = 2020
Output: 514579

1721 + 299 = 2020, and 1721 * 299 = 514579.

Example 2:

Input:  a = [10, 20, 30], target = 50
Output: 600

20 * 30 = 600.

Example 3:

Input:  a = [1010, 1010, 5], target = 2020
Output: 1020100

Constraints

• 2 <= n <= 10^5
• Exactly one valid pair exists.

Problem 21: Trapping Rain Water

LeetCode: 42. Trapping Rain Water

Description

Given bar heights h, compute how much water is trapped after raining. Water above each bar is min(maxLeft, maxRight) - h[i]. Use two pointers in O(n) time and O(1) extra space.

Examples

Example 1:

Input:  [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Example 2:

Input:  [4, 2, 0, 3, 2, 5]
Output: 9

Example 3:

Input:  [1, 2, 3]
Output: 0

Constraints

• 0 <= n <= 2 * 10^4
• 0 <= h[i] <= 10^5

Problem 22: Subarray Sum Equals K

LeetCode: 560. Subarray Sum Equals K

Description

Return the number of contiguous subarrays whose elements sum to exactly k. Use prefix sums with a hash map counting how many times each running sum has been seen, in O(n).

Examples

Example 1:

Input:  nums = [1, 1, 1], k = 2
Output: 2

Subarrays [0..1] and [1..2].

Example 2:

Input:  nums = [1, 2, 3], k = 3
Output: 2

[1, 2] and [3].

Example 3:

Input:  nums = [1, -1, 0], k = 0
Output: 3

Constraints

• 1 <= n <= 2 * 10^4
• -10^7 <= k <= 10^7

Problem 23: Warehouse Forklift

Description

A row of n crates has weights w[i]. A forklift moves left to right carrying a running load; whenever adding the next crate would exceed capacity L, it drops its current load (always able to carry at least one crate) and starts fresh with that crate. Return the total number of drops needed to clear all crates. The final non-empty load also counts as a drop.

Examples

Example 1:

Input:  w = [2, 3, 1, 5], L = 5
Output: 3

Loads [2,3], [1], [5] — three drops.

Example 2:

Input:  w = [1, 1, 1], L = 5
Output: 1

All three fit in one load.

Example 3:

Input:  w = [4, 4, 4], L = 4
Output: 3

Constraints

• 1 <= n <= 10^5
• 1 <= w[i] <= L <= 10^9

Problem 24: Maximum Sum of Window Size K

LeetCode: 643. Maximum Average Subarray I

Description

Given an array a and an integer k, return the maximum sum of any contiguous subarray of length exactly k. Slide a fixed-size window: add the entering element, subtract the leaving one, in O(n).

Examples

Example 1:

Input:  a = [1, 12, -5, -6, 50, 3], k = 4
Output: 51

Window [-5, -6, 50, 3] sums to 42… the best window [12, -5, -6, 50] sums to 51.

Example 2:

Input:  a = [5, 5, 5], k = 1
Output: 5

Example 3:

Input:  a = [-1, -2, -3, -4], k = 2
Output: -3

Window [-1, -2].

Constraints

• 1 <= k <= n <= 10^5

Singly Linked List

What It Is & When to Use It

A chain of nodes where each points only forward — when does this beat an array, and when does it lose badly?

The Mental Model: A Treasure Hunt

Why is a linked list less like a numbered shelf and more like a trail of clues where each node only knows where the next one is?

Node Layout

What does one node hold — a payload plus a single next reference — and why is there no contiguity guarantee between consecutive nodes?

Nodes Scattered Across the Heap

Why can two adjacent-in-the-list nodes sit far apart in memory, and what does that cost you in cache behavior versus an array?

Head Pointer & the Null Terminator

Where does the list begin, what marks the end, and why is the empty list simply head == null?

The Structural Invariant

Following next repeatedly from a non-cyclic head must end in null — why is preserving that the heart of every edit?

Traversal

How do you walk node-to-node with a moving cursor, why can you only ever go forward, and why is there no way to “back up” without restarting?

Core Operations

The everyday verbs — split each into its own pointer dance.

Insert at Head

Why is prepending the cheapest possible write, and what two assignments make it work and in what order?

Insert at Tail

Why does appending cost a full walk unless you keep a tail pointer, and what does maintaining a tail pointer buy and cost you?

Insert After a Given Node

Which links rewire to splice a new node between two existing ones, and in what order so you never lose the rest of the chain?

Delete a Node

Why do you need the node before the target, and how does the predecessor’s next jump over the victim to unlink it?

Search by Value

Why is finding an element inherently a linear scan with no shortcut, even when the data happens to be sorted?

Reversal

How do you flip every next pointer in a single pass using three cursors (prev, curr, next), and where does the old head end up?

Why You Need Three Pointers

Why does saving curr.next before rewiring it prevent you from severing the unvisited remainder of the list?

Cycle Detection

How do fast and slow pointers (tortoise and hare) reveal a loop, and what does it mean structurally when they meet?

Time Complexity

Reason about each operation and exactly what makes it cheap or costly.

Head Operations

Why are insert-at-head and delete-head \( O(1) \) — what work is bounded no matter how long the list is?

Tail Operations

Why is insert-at-tail \( O(n) \) without a tail pointer but \( O(1) \) with one, and why is delete-tail still \( O(n) \) even with a tail pointer?

Search & Index Access

Why are search and “get the k-th element” \( O(n) \) worst case, what is the best case, and why is there no \( O(1) \) random access at all?

Reversal & Cycle Detection

Why are both single-pass \( O(n) \) walks, and why does the two-pointer cycle check stay \( O(n) \) despite the hare moving twice as fast?

Space Complexity

Reason about per-node overhead and the extra space operations consume.

Per-Node Pointer Overhead

Why does each node cost its payload plus one reference, making total space \( O(n) \) with a real constant the array doesn’t pay?

In-Place Operations

Why do insert, delete, search, and iterative reversal all need only \( O(1) \) auxiliary space?

Recursive vs Iterative Traversal

Why does a recursive traversal or recursive reversal use \( O(n) \) call-stack space while the iterative version uses \( O(1) \) — and what risk does that create on a long list?

Trade-offs vs Arrays

No random access and poor cache behavior vs \( O(1) \) splicing and no resize cost — when does each win?

Pointer-Surgery Bugs & Edge Cases

Losing the tail by reassigning next too early, dropping the last reference (leak), one-element and empty-list cases, deleting the head — which are the classic traps?

Real-World & Interview Uses

Stacks, adjacency lists, LRU chains, undo stacks, and the many “reverse/merge/detect-cycle” interview staples.

Implementation Walkthrough

Before writing code, break the problem into the pieces you must get right.

State & Setup

What fields does the list hold (head, optional tail, optional size), and what does a freshly constructed empty list look like?

The Traversal Cursor

How do you set up and advance a walking pointer, and what is the loop’s stop condition so you don’t dereference null?

The Pointer-Rewire Step

For insert and delete, in what order must you read-then-write the next links so no part of the chain is orphaned mid-edit?

Edge-Case Branches

Which special cases (empty list, single node, operating on the head) need their own branch, and what must each branch update?

Termination & Return

How does each operation decide it is done, and what does it return — a value, the new head, a boolean, or nothing?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Doubly Linked List

What It Is & When to Use It

Each node links both ways — what does the backward pointer unlock that a singly linked list can’t offer?

The Mental Model: A Two-Way Street

Why is a doubly linked list like a street with signs pointing both directions at every house, and what new movements does that enable?

Node Layout (prev / next)

What three fields does a node carry now, and what invariant ties a.next == b to b.prev == a?

The Mutual-Link Invariant

Why must every forward link have a matching backward link, and how does breaking that symmetry corrupt the whole list?

Head, Tail & Sentinel Nodes

Why keep both a head and a tail pointer, and how do dummy sentinel nodes erase the special cases at the boundaries?

Life Without Sentinels

What boundary checks does every insert and delete need when head and tail can be null, and which bugs does that breed?

Life With Sentinels

How does ringing the list with permanent dummy head and tail nodes mean a real node always has non-null neighbors?

Bidirectional Traversal

How does holding both links let you walk forward from the head or backward from the tail with the same code shape?

Core Operations

Every edit touches more pointers than in a singly list — break them out.

Insert at Head / Tail

With a tail pointer or tail sentinel, why are both ends now symmetric \( O(1) \) inserts, and which links update at each end?

Insert Between Two Nodes

Which four pointers change when you splice a new node between a left and right neighbor, and in what safe order so no link is read after it’s overwritten?

Delete Given a Node

Why can you remove a node in constant time when you already hold a reference to it — no predecessor search needed — and which two links bridge the gap left behind?

Search by Value

Why is finding by value still a linear scan despite the extra pointer, and can searching from both ends help in the worst case?

Sentinels vs Null Checks

How does ringing the list with dummy head/tail nodes turn every insert and delete into the same uniform four assignments with no branching?

Time Complexity

Reason about what the backward pointer makes cheap and what it leaves unchanged.

Insert / Delete at a Known Node

Why is splicing in or removing a node you already hold strictly \( O(1) \), and why is this the single biggest win over a singly list?

Head & Tail Operations

Why are insert and delete at both ends \( O(1) \) here, when a singly list could only cheaply delete at the head?

Search & Index Access

Why are search and “get the k-th node” still \( O(n) \), and how does bidirectional access only halve the constant, not the order?

Space Complexity

Reason about the cost of the second pointer.

Two Pointers Per Node

Why is total space \( O(n) \) but with a larger constant than a singly list, and when does that overhead actually matter?

Sentinel Overhead

Why do the dummy head and tail add only \( O(1) \) fixed space while removing branching from every operation?

Auxiliary Space of Operations

Why do all insert, delete, and search operations need only \( O(1) \) extra space, and why is a recursive traversal still \( O(n) \) on the stack?

Trade-offs vs Singly Linked

Two pointers per node means more memory and more links to keep consistent — when is the backward link worth that overhead?

Pointer-Surgery Bugs & Edge Cases

Updating next but forgetting the matching prev, breaking the a.next/b.prev invariant, single-node and empty cases, deleting head or tail without sentinels.

Real-World & Interview Uses

LRU caches (the canonical use), browser history, text-editor buffers, deques, and java.util.LinkedList under the hood.

Implementation Walkthrough

Before writing code, break the problem into the pieces you must get right.

State & Setup

What does the list hold (head/tail pointers or two sentinels, plus size), and how do you wire the sentinels together at construction so the empty list is valid?

The Four-Pointer Splice

For insert between neighbors, name the four assignments and the order that keeps both the new node’s and the neighbors’ links consistent.

The Unlink Step

For delete, which two links must you redirect to bypass the node, and what should you do to the removed node’s own pointers?

Edge-Case Branches (or Their Absence)

Which boundary cases need special handling without sentinels, and why do sentinels let you delete those branches entirely?

Termination & Return

How does each operation finish, and what does it return — a value, a boolean, or the affected node?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Skip Lists

What It Is & When to Use It

A sorted linked list with stacked “express lanes” — when do you reach for this instead of a balanced tree, and why is it loved for concurrency?

The Mental Model: Express Lanes Over Local Stops

Why is a skip list like a subway map where higher levels are express trains skipping many stops, and how does dropping to a slower line near your destination mirror the search?

The Layered Structure

How do stacked sorted lists sit on top of a full base list, and what does each higher level skip over relative to the level below it?

The Base Level Holds Everything

Why must the bottom level contain every element in sorted order, and why is correctness anchored there?

Node Towers

What does it mean for one node to exist on several levels at once, and what does a node’s array of forward pointers look like?

Height of a Tower

What determines how tall a given node’s tower is, and what does a node of height 1 versus height 4 participate in?

Probabilistic Levels

Why use a coin flip to decide each node’s height instead of strictly balancing, and roughly what fraction of nodes reach each successive level?

Why Randomness Replaces Rebalancing

What does the coin flip buy you that lets you skip the rotations a balanced tree needs, and what do you give up in exchange?

Search

How does a query start at the top-left, move right until the next node would overshoot the target, then drop a level — and why does that feel like a balanced-tree descent?

Tracking the Update Path

Why must search remember the rightmost node it stopped at on every level, and how is that saved path reused by insert and delete?

Insertion & Tower Building

How do you find the slot via the update path, flip coins to pick the new node’s height, and splice it into each level it reaches?

Growing the List’s Level

What happens when a new tower is taller than any existing one, and how must the head and the recorded level adjust?

Deletion

How do you unlink a node from every level it appears on, why is the update path again the key, and when should the list’s top level shrink back?

Time Complexity

Reason about why the randomized structure behaves like a logarithmic one.

Why Search Is Expected \( O(\log n) \)

Why does halving (roughly) the candidates at each level make the expected number of levels about \( \log n \), and why is the work per level expected constant?

Insert & Delete

Why do insert and delete share search’s \( O(\log n) \) expected cost plus an expected-constant amount of splicing across the touched levels?

Worst Case vs Expected

Why is the worst case \( O(n) \) (every tower the same height), why is “expected” the honest word, and why does it rarely bite in practice?

Space Complexity

Reason about the cost of all those extra pointers.

Expected Tower Heights

Why does the average tower height stay constant, making total pointer space expected \( O(n) \) rather than \( O(n \log n) \)?

Tuning with the Probability Factor

How does the coin’s probability \( p \) trade pointer space against search speed, and what does a smaller \( p \) do to both?

Search Auxiliary Space

Why does a search need only \( O(1) \) working space, while remembering the update path for insert/delete costs \( O(\log n) \) expected?

Trade-offs vs Balanced Trees

Simpler code and no rotations vs randomized (not worst-case) guarantees — when does a skip list win over a red-black or AVL tree?

Common Bugs & Edge Cases

Forgetting to update every level, an empty or single-node list, growing the head’s level when a tall tower appears, an unseeded RNG making the structure degenerate.

Real-World & Interview Uses

Redis sorted sets, ConcurrentSkipListMap, LevelDB-style stores, and ranked leaderboards — where the ordered, lock-friendly structure shines.

Implementation Walkthrough

Before writing code, break the problem into the pieces you must get right.

State & Setup

What does the structure hold (a head with an array of forward pointers, a current level, a max level, the probability \( p \)), and what does the empty list look like?

The Random-Level Routine

How does the coin-flip loop decide a new node’s height, what caps it, and how should the RNG be seeded to avoid degenerate runs?

The Search-and-Record Loop

How do you descend from the top level, move right while the next key is smaller than the target, and store the stop node per level into the update array?

Splicing Across Levels

Using the update array, how do you rewire forward pointers at each level the new node reaches, and how does this mirror singly-linked insertion repeated per level?

Termination & Return

How does each operation finish, when do you raise or lower the list’s current level, and what does each return (found value, success boolean)?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Linked Lists: Problem Set

Work these in order. Every problem is an implementation task: fill in the stub in problemset/ and make its test in tests/problemset/ pass. The Foundational problems drill the core pointer-rewiring moves; the Applied problems weave interview classics together with contest-style challenges, ramping from easy to hard. All share the ListNode helper and are verified the same way. No solutions are provided.

Foundational

Problem 1: Reverse a Singly Linked List

LeetCode: 206. Reverse Linked List

Description

Given the head of a singly linked list, reverse the list and return the head of the reversed list. Do it iteratively in \( O(n) \) time and \( O(1) \) extra space by rewiring the next pointers as you walk.

Examples

Example 1:

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

Every link is flipped to point at the previous node.

Example 2:

Input:  7
Output: 7

A single node is its own reverse.

Example 3:

Input:  (empty)
Output: (empty)

An empty list reverses to an empty list.

Constraints

• The number of nodes is in the range \( [0, 5000] \).
• \( -5000 \le \text{Node.val} \le 5000 \).

Problem 2: Find the Middle Node

LeetCode: 876. Middle of the Linked List

Description

Given the head of a non-empty singly linked list, return the middle node. If the list has an even number of nodes, return the second of the two middle nodes. Use a single pass with the slow/fast two-pointer technique.

Examples

Example 1:

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 3 -> 4 -> 5

The middle of five nodes is the third node.

Example 2:

Input:  1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 4 -> 5 -> 6

For six nodes the second middle (the fourth node) is returned.

Example 3:

Input:  1
Output: 1

A single node is its own middle.

Constraints

• The number of nodes is in the range \( [1, 100] \).
• \( 1 \le \text{Node.val} \le 100 \).

Problem 3: Detect a Cycle

LeetCode: 141. Linked List Cycle

Description

Given the head of a singly linked list, return true if the list contains a cycle and false otherwise. A cycle exists if some node can be reached again by continuously following next. Use \( O(1) \) extra space (Floyd’s slow/fast pointers).

Examples

Example 1:

Input:  3 -> 2 -> 0 -> -4, tail connects back to node index 1 (value 2)
Output: true

Following next from the tail re-enters the list at the node with value 2.

Example 2:

Input:  1 -> 2, tail connects back to node index 0 (value 1)
Output: true

The two-node list loops on itself.

Example 3:

Input:  1 -> 2 -> 3 -> 4 (no cycle)
Output: false

The tail’s next is null, so traversal terminates.

Constraints

• The number of nodes is in the range \( [0, 10^4] \).
• \( -10^5 \le \text{Node.val} \le 10^5 \).

Problem 4: Merge Two Sorted Lists

LeetCode: 21. Merge Two Sorted Lists

Description

You are given the heads of two singly linked lists, a and b, each sorted in ascending order. Splice their nodes together into one ascending sorted list and return its head. The result should be made by reusing the existing nodes, not by allocating new ones.

Examples

Example 1:

Input:  a = 1 -> 2 -> 4, b = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Nodes are interleaved in non-decreasing order.

Example 2:

Input:  a = (empty), b = (empty)
Output: (empty)

Two empty lists merge to an empty list.

Example 3:

Input:  a = (empty), b = 0
Output: 0

Merging with an empty list returns the other list.

Constraints

• The number of nodes in both lists is in the range \( [0, 50] \).
• \( -100 \le \text{Node.val} \le 100 \).

Problem 5: Remove Duplicates from a Sorted List

LeetCode: 83. Remove Duplicates from Sorted List

Description

Given the head of a sorted singly linked list, delete all nodes that have duplicate values so that each value appears exactly once. Return the head of the modified list, which must remain sorted.

Examples

Example 1:

Input:  1 -> 1 -> 2
Output: 1 -> 2

The second 1 is dropped.

Example 2:

Input:  1 -> 1 -> 2 -> 3 -> 3
Output: 1 -> 2 -> 3

Each run of equal values collapses to one node.

Example 3:

Input:  (empty)
Output: (empty)

An empty list is unchanged.

Constraints

• The number of nodes is in the range \( [0, 300] \).
• \( -100 \le \text{Node.val} \le 100 \), and the list is sorted ascending.

Applied Problems

Problem 6: Remove the N-th Node From the End

LeetCode: 19. Remove Nth Node From End of List

Description

Given the head of a linked list, remove the n-th node from the end of the list and return its head. Do it in a single pass by advancing one pointer n steps ahead of another so the gap pinpoints the node to unlink.

Examples

Example 1:

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5

The 2nd-from-last node (value 4) is removed.

Example 2:

Input:  head = 1, n = 1
Output: (empty)

Removing the only node leaves an empty list.

Example 3:

Input:  head = 1 -> 2, n = 2
Output: 2

Removing the 2nd-from-last node (the head) leaves the tail.

Constraints

• The number of nodes is sz, with \( 1 \le sz \le 30 \).
• \( 1 \le n \le sz \).

Problem 7: Palindrome Linked List

LeetCode: 234. Palindrome Linked List

Description

Given the head of a singly linked list, return true if the sequence of values reads the same forwards and backwards. Aim for \( O(n) \) time and \( O(1) \) extra space (find the middle, reverse the second half, compare).

Examples

Example 1:

Input:  1 -> 2 -> 2 -> 1
Output: true

The values mirror around the center.

Example 2:

Input:  1 -> 2 -> 3 -> 2 -> 1
Output: true

An odd-length palindrome with a lone middle value.

Example 3:

Input:  1 -> 2
Output: false

Reversed it reads 2 -> 1, which differs.

Constraints

• The number of nodes is in the range \( [1, 10^5] \).
• \( 0 \le \text{Node.val} \le 9 \).

Problem 8: Odd-Even Linked List

LeetCode: 328. Odd Even Linked List

Description

Given the head of a singly linked list, group all nodes at odd positions together followed by the nodes at even positions, then return the reordered list. Positions are 1-based by index, not by value. Preserve the relative order within each group and use \( O(1) \) extra space.

Examples

Example 1:

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 5 -> 2 -> 4

Odd-position nodes (1,3,5) precede even-position nodes (2,4).

Example 2:

Input:  2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
Output: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4

Grouping is by position, so values stay in their original relative order.

Example 3:

Input:  1 -> 2
Output: 1 -> 2

With one node per group, the list is unchanged.

Constraints

• The number of nodes is in the range \( [0, 10^4] \).
• \( -10^6 \le \text{Node.val} \le 10^6 \).

Problem 9: Swap Nodes in Pairs

LeetCode: 24. Swap Nodes in Pairs

Description

Given the head of a linked list, swap every two adjacent nodes and return its head. You must change the node links rather than the values. If the list has an odd number of nodes, the final unpaired node stays in place.

Examples

Example 1:

Input:  1 -> 2 -> 3 -> 4
Output: 2 -> 1 -> 4 -> 3

Each adjacent pair is swapped.

Example 2:

Input:  1 -> 2 -> 3
Output: 2 -> 1 -> 3

The trailing odd node (value 3) keeps its position.

Example 3:

Input:  1
Output: 1

A single node has nothing to swap.

Constraints

• The number of nodes is in the range \( [0, 100] \).
• \( 0 \le \text{Node.val} \le 100 \).

Problem 10: Intersection of Two Linked Lists

LeetCode: 160. Intersection of Two Linked Lists

Description

Given the heads of two singly linked lists a and b, return the first node at which they intersect by reference, or null if they never intersect. Intersection means the two lists share the same tail nodes (same objects, not just equal values). Aim for \( O(m + n) \) time and \( O(1) \) extra space.

Examples

Example 1:

Input:  a = 4 -> 1 -> 8 -> 4 -> 5, b = 5 -> 6 -> 1 -> 8 -> 4 -> 5
        the "8 -> 4 -> 5" tail is the same shared nodes
Output: node with value 8

Both lists converge at the shared node holding value 8.

Example 2:

Input:  a = 1 -> 9 -> 1 -> 2 -> 4, b = 3 -> 2 -> 4 (shared tail 2 -> 4)
Output: node with value 2

The shared suffix begins at the node holding value 2.

Example 3:

Input:  a = 2 -> 6 -> 4, b = 1 -> 5 (no shared nodes)
Output: null

The lists are disjoint, so there is no intersection.

Constraints

• The number of nodes of each list is in the range \( [0, 3 \times 10^4] \).
• \( 1 \le \text{Node.val} \le 10^5 \).

Problem 11: Reorder List

LeetCode: 143. Reorder List

Description

Given the head of a singly linked list \( L_0 \to L_1 \to \dots \to L_n \), reorder it in place to \( L_0 \to L_n \to L_1 \to L_{n-1} \to \dots \) You may not modify the values, only the node links. Return the new head.

Examples

Example 1:

Input:  1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3

Front and back nodes are interleaved inward.

Example 2:

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

With odd length the middle node lands last.

Example 3:

Input:  1 -> 2
Output: 1 -> 2

A two-node list is already in reordered form.

Constraints

• The number of nodes is in the range \( [1, 5 \times 10^4] \).
• \( 1 \le \text{Node.val} \le 1000 \).

Problem 12: Add Two Numbers (Most-Significant First)

Description

Two non-negative integers are stored as singly linked lists of decimal digits in most-significant-digit-first order, so 7 -> 2 -> 4 represents 724. Given the heads a and b, return their sum as a new most-significant-first digit list with no leading zeros (except the single node 0 for a zero sum). Each list’s value fits in a long. This is the Advent-of-Code flavor of LeetCode’s “Add Two Numbers” with the digits running high-to-low.

Examples

Example 1:

Input:  a = 7 -> 2 -> 4, b = 5 -> 6   (724 + 56)
Output: 7 -> 8 -> 0                    (780)

Adding from the least-significant ends carries into the tens place.

Example 2:

Input:  a = 0, b = 0
Output: 0

A zero sum is the single node 0.

Example 3:

Input:  a = 9 -> 9, b = 1            (99 + 1)
Output: 1 -> 0 -> 0                  (100)

The carry extends the result by one digit.

Constraints

• Each list has between 1 and 18 digits.
• The leading digit is non-zero unless the number is the single node 0.

Problem 13: Rotate List Right

LeetCode: 61. Rotate List

Description

Given the head of a singly linked list, rotate the list to the right by k places, so the last k nodes move to the front. k may exceed the list length, in which case take it modulo the length. Return the new head; an empty list returns null.

Examples

Example 1:

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 4 -> 5 -> 1 -> 2 -> 3

The last two nodes wrap around to the front.

Example 2:

Input:  head = 0 -> 1 -> 2, k = 4
Output: 2 -> 0 -> 1

k = 4 modulo length 3 is an effective rotation of 1.

Example 3:

Input:  head = 1 -> 2 -> 3, k = 3
Output: 1 -> 2 -> 3

Rotating by the full length restores the original order.

Constraints

• The number of nodes is in the range \( [0, 500] \).
• \( -100 \le \text{Node.val} \le 100 \), and \( 0 \le k \le 2 \times 10^9 \).

Problem 14: Train Car Partition

Description

A freight train is a singly linked list of car weights, and the yard master picks a pivot weight x. Reorder the cars so every car with weight strictly less than x precedes every car with weight \ge x, preserving the relative order within each group. Mutate the links only, not the values. This is the contest framing of LeetCode’s “Partition List.”

Examples

Example 1:

Input:  cars = 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3
Output: 1 -> 2 -> 2 -> 4 -> 3 -> 5

Cars lighter than 3 (1,2,2) keep order ahead of the rest (4,3,5).

Example 2:

Input:  cars = 2 -> 1, x = 2
Output: 1 -> 2

The lighter car moves ahead of the pivot-weight car.

Example 3:

Input:  cars = 1 -> 2 -> 3, x = 0
Output: 1 -> 2 -> 3

No car is lighter than the pivot, so order is unchanged.

Constraints

• The number of cars is in the range \( [0, 200] \).
• \( -100 \le \text{weight} \le 100 \) and \( -200 \le x \le 200 \).

Problem 15: Reverse Nodes in k-Group

LeetCode: 25. Reverse Nodes in k-Group

Description

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list. k is a positive integer no larger than the list length. Nodes left over at the end (fewer than k) stay in their original order. Change only the links, not the values.

Examples

Example 1:

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 2 -> 1 -> 4 -> 3 -> 5

Each full pair is reversed; the lone node 5 stays put.

Example 2:

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5

The first three reverse; the trailing two are short of k.

Example 3:

Input:  head = 1 -> 2 -> 3 -> 4, k = 4
Output: 4 -> 3 -> 2 -> 1

The whole list is a single group and fully reverses.

Constraints

• The number of nodes is in the range \( [1, 5000] \).
• \( 0 \le \text{Node.val} \le 1000 \) and \( 1 \le k \le n \).

Problem 16: Copy List with Random Pointer

LeetCode: 138. Copy List with Random Pointer

Description

You are given the head of a RandomNode list where each node carries a next pointer and a random pointer that may point to any node in the list or be null. Return a deep copy: a brand-new list of RandomNode objects whose next and random structure mirrors the original, sharing no nodes with it. Aim for \( O(n) \) time.

Examples

Example 1:

Input:  vals = [7, 13, 11, 10, 1], random indices = [null, 0, 4, 2, 0]
Output: a new list with identical values and random targets, distinct objects

Node 13’s random points at node 7 in the copy, just as in the original.

Example 2:

Input:  vals = [1, 2], random indices = [1, 1]
Output: a new two-node list where both copies' random point at the copied node 2

Random pointers reference copied nodes, never the originals.

Example 3:

Input:  (empty)
Output: (empty)

An empty list copies to an empty list.

Constraints

• The number of nodes is in the range \( [0, 1000] \).
• \( -10^4 \le \text{Node.val} \le 10^4 \); random is null or points into the list.

Problem 17: Remove Duplicates From a Sorted List II

LeetCode: 82. Remove Duplicates from Sorted List II

Description

Given the head of a sorted singly linked list, delete every node that has a duplicate value, leaving only the values that were originally distinct. Return the new head, still sorted, in \( O(n) \) time. Framed as submarine depth readings, 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 compacts to 1 -> 2 -> 5.

Examples

Example 1:

Input:  1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Output: 1 -> 2 -> 5

Both 3s and both 4s are removed entirely.

Example 2:

Input:  1 -> 1 -> 1 -> 2 -> 3
Output: 2 -> 3

The whole run of 1s disappears, including the head.

Example 3:

Input:  (empty)
Output: (empty)

An empty list is unchanged.

Constraints

• The number of nodes is in the range \( [0, 300] \).
• \( -100 \le \text{Node.val} \le 100 \), and the list is sorted ascending.

Problem 18: Next Greater Node in Linked List

LeetCode: 1019. Next Greater Node In Linked List

Description

A relay team is a singly linked list of runner speeds. For each runner from front to back, report the speed of the next runner who is strictly faster, or 0 if no later runner is faster. Return the answers as an array indexed by 0-based position. Aim for \( O(n) \) time using a monotonic stack.

Examples

Example 1:

Input:  2 -> 1 -> 5
Output: [5, 5, 0]

The next strictly greater value after 2 and after 1 is 5; 5 has none.

Example 2:

Input:  2 -> 7 -> 4 -> 3 -> 5
Output: [7, 0, 5, 5, 0]

Each entry is the first later value that exceeds it, else 0.

Example 3:

Input:  1 -> 7 -> 5 -> 1 -> 9 -> 2 -> 5 -> 1
Output: [7, 9, 9, 9, 0, 5, 0, 0]

Values with no greater successor map to 0.

Constraints

• The number of nodes is in the range \( [1, 10^4] \).
• \( 1 \le \text{Node.val} \le 10^9 \).

Problem 19: Merge Zero Segments

LeetCode: 2181. Merge Nodes in Between Zeros

Description

A flight recorder is a singly linked list that begins and ends with a 0 node; between every pair of consecutive zeros lies one console reading’s values, and no two zeros are adjacent. Merge each maximal segment strictly between two zeros into a single node holding the sum of its values, then drop the zeros. Return the head of the compacted list.

Examples

Example 1:

Input:  0 -> 3 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0
Output: 4 -> 11

The first segment sums to 4 and the second to 11.

Example 2:

Input:  0 -> 1 -> 0 -> 3 -> 0 -> 2 -> 2 -> 0
Output: 1 -> 3 -> 4

Each between-zeros segment collapses to its sum.

Example 3:

Input:  0 -> 5 -> 0
Output: 5

A single segment yields a single node.

Constraints

• The number of nodes is in the range \( [3, 2 \times 10^5] \).
• \( 0 \le \text{Node.val} \le 1000 \); the list starts and ends with 0 and has no adjacent zeros.

Problem 20: Sort a Linked List

LeetCode: 148. Sort List

Description

Given the head of a singly linked list, return it sorted in ascending order. Aim for \( O(n \log n) \) time and, ideally, \( O(1) \) auxiliary space using a bottom-up merge sort over the links.

Examples

Example 1:

Input:  4 -> 2 -> 1 -> 3
Output: 1 -> 2 -> 3 -> 4

The nodes are relinked into ascending order.

Example 2:

Input:  -1 -> 5 -> 3 -> 4 -> 0
Output: -1 -> 0 -> 3 -> 4 -> 5

Negative and zero values sort correctly alongside positives.

Example 3:

Input:  (empty)
Output: (empty)

An empty list is already sorted.

Constraints

• The number of nodes is in the range \( [0, 5 \times 10^4] \).
• \( -10^5 \le \text{Node.val} \le 10^5 \).

Stacks

What It Is & When to Use It

What problems naturally call for “deal with the most recent thing first,” and what makes a stack the right fit over a list or queue?

LIFO Discipline

What does last-in-first-out mean for the order things leave, and how is that ordering a feature rather than a limitation?

The Mental Model

If you picture a stack of plates, which plate is reachable and which are trapped, and why?

The Single Access Point Invariant

Why does allowing access at exactly one end make the structure easier to reason about and to keep correct?

Core Operations

Which operations form the public contract, and what does each promise to the caller?

push

How do you add an element so it becomes the new top without disturbing what’s below?

pop

How do you remove and return the top, and what must be true before you’re allowed to?

peek / top

How do you read the top without removing it, and why is that distinct from pop?

isEmpty / size

How do you expose state so callers can guard their own pops without touching internals?

State and Invariants

What internal fields must always agree, and what relationship between them must hold after every operation?

The Top Index or Pointer

How does the top marker tell push and pop where to act, and what value marks “empty”?

Invariant Maintenance

After any push or pop, what must still be true about size, the top marker, and the stored elements?

Array-Backed vs Linked-List Backing

What changes about growth, pointers, cache locality, and worst-case spikes when you swap the underlying store?

Array Backing

How does a top index plus a contiguous array realize a stack, and what happens at the boundary when it fills?

Linked-List Backing

Why does pushing onto the head of a singly linked list give a clean O(1) with no resize ever needed?

Choosing Between Them

Which backing wins on memory overhead, which on predictable latency, and why?

Growth and Resizing

When an array stack fills, how do you grow it, and why is doubling the capacity the standard move rather than adding a fixed amount?

Why Doubling Amortizes

How does the cost of an occasional expensive copy get spread thin across many cheap pushes?

Time Complexity

What does each operation cost, and what in the implementation forces that bound?

push

Why is push constant time in the common case, and which case makes a single push expensive?

pop and peek

Why are these always constant time regardless of how full the stack is?

Amortized vs Worst-Case push

What is the difference between the cost of one unlucky push and the average over many, and what triggers the unlucky one?

Constant Factors

Where does array backing tend to beat linked backing in practice even when both are labeled O(1)?

Space Complexity

How much memory does the structure use beyond the elements themselves, and where does it come from?

Storage Overhead by Backing

Why does a linked stack pay per-element pointer overhead while an array stack may hold unused slack capacity?

Auxiliary Space of Operations

Why do push, pop, and peek need no extra space proportional to size?

Call-Stack Space When Used Recursively

If a stack is consumed by a recursive walk, how does the recursion’s own frame depth add to space cost?

Trade-offs vs Alternatives

When would you reach for a stack over a queue, a deque, or a plain dynamic list, and what do you give up?

Common Bugs & Edge Cases

What goes wrong on popping or peeking an empty stack, off-by-one on the top index, forgetting to null freed slots, or resizing at the wrong moment?

Real-World & Interview Uses

Where do call frames, undo, bracket matching, expression evaluation, and DFS rely on this exact shape?

Implementation Walkthrough

Before writing code, break the build into parts and decide each one.

State & Setup

What fields hold the elements, the capacity, and the top marker, and what are their initial values for an empty stack?

push Step by Step

In what order do you check capacity, possibly resize, place the element, and advance the top marker?

pop Step by Step

In what order do you check emptiness, read the top, shrink the marker, and optionally free the slot?

Resize Step

How do you allocate the bigger store and copy elements so the top marker still points correctly afterward?

Termination & Return

What does each operation return, and how do you signal an illegal pop on an empty stack?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Queues

What It Is & When to Use It

What problems need “serve in the order things arrived,” and what makes a queue the right fit over a stack or list?

FIFO Discipline

What does first-in-first-out mean for who gets served next, and why is fairness a natural consequence?

The Mental Model

If you picture a line at a counter, where do arrivals join and where do departures happen?

Two Ends, Two Roles

Why do the back and front play different roles, unlike a stack’s single end?

Core Operations

Which operations make up the contract, and what does each promise?

enqueue

How do you add an element at the back without disturbing the front?

dequeue

How do you remove and return the front, and what must hold before you may?

peek / front

How do you read the front without removing it, and why keep that separate from dequeue?

State and Invariants

What internal fields must always agree for the queue to stay correct?

Front and Rear Markers

How do two indices let you avoid shifting every element on each dequeue?

The Size or Count Field

Why is an explicit count often the cleanest way to keep the structure honest?

Circular Buffer Wraparound

How does modular arithmetic let a slot freed at the front be reused at the back of a fixed array?

Why a Ring Beats a Line

Without wraparound, why does a simple array queue “walk off” the end and waste space?

Distinguishing Full from Empty

Why does front == rear alone fail to tell full from empty, and what two fixes resolve it?

Array-Backed vs Linked-List Backing

What does each backing buy you for growth, wraparound bookkeeping, and pointer overhead?

Array Backing with a Ring

How do head, tail, and count cooperate to keep operations constant time?

Linked-List Backing

Why do head and tail node references give a clean queue with no wraparound math at all?

Growth and Resizing

When a circular array fills, how do you copy into a larger one without scrambling the logical order across the wrap point?

Time Complexity

What does each operation cost, and what forces that bound?

enqueue and dequeue

Why are both constant time once you have front and rear markers, even though elements never shift?

Amortized enqueue on a Growable Queue

What single enqueue becomes expensive, what triggers it, and why does the average stay constant?

peek

Why is reading the front always cheap regardless of length?

Space Complexity

How much memory beyond the elements, and where does it come from?

Slack Capacity vs Pointer Overhead

Why does a ring-buffer queue hold unused slots while a linked queue pays a reference per node?

Auxiliary Space of Operations

Why do the core operations need no extra space proportional to length?

Queue Space in a BFS

When a queue drives a breadth-first search, how large can it grow relative to the input, and what determines its peak?

Trade-offs vs Alternatives

When is a queue the right call over a stack, a deque, or a priority queue, and what do you sacrifice?

Common Bugs & Edge Cases

What breaks on dequeue-from-empty, the full/empty ambiguity, a missed modulo, or a resize that ignores the wrap point?

Real-World & Interview Uses

Where do BFS, task scheduling, buffering, and producer/consumer pipelines depend on this shape?

Implementation Walkthrough

Before writing code, settle each part.

State & Setup

What fields hold the buffer, capacity, front, rear, and count, and what are their empty-queue values?

enqueue Step by Step

In what order do you check fullness, possibly resize, place the element, advance rear with wraparound, and bump count?

dequeue Step by Step

In what order do you check emptiness, read the front, advance front with wraparound, and drop count?

The Wraparound Computation

How exactly does modular arithmetic turn “past the end” back to index zero for both markers?

Resize Step

How do you re-lay the elements in logical order when copying a wrapped buffer into a bigger one?

Termination & Return

What does each operation return, and how do you signal an illegal dequeue on an empty queue?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Deques

Open at Both Ends

What can a deque do that a plain stack or queue cannot, and why is that worth a more complex structure?

When to Use It

What problems want fast insertion and removal at both ends, and how do you recognize them?

The Mental Model

If you picture a double-ended line where people join and leave from either side, what stays symmetric and what does not?

Four Core Operations

What are the push/pop pairs at each end, and how do they mirror one another?

pushFront / pushBack

How do you add at the head versus the tail, and what marker moves in each case?

popFront / popBack

How do you remove at each end, and what must you check before each removal?

peekFront / peekBack

How do you read either end without removing, and why keep that separate?

State and Invariants

What internal fields must always agree, and what must hold about head, tail, and count after every operation?

Head and Tail Markers

How do two indices, moving in opposite directions, track both ends of the data?

The Count Field

Why does an explicit element count make the full and empty conditions unambiguous?

Circular Array Wraparound

How do head and tail indices move in opposite directions around a ring?

Wraparound Indexing

How does modular arithmetic keep both indices in bounds as they cross zero in either direction?

Distinguishing Full from Empty

Why can’t head and tail alone tell full from empty here, and how does a count resolve it?

Doubly-Linked Alternative

When is a node-based deque, with prev and next pointers, preferable to an array-based one?

Why Both Pointers Are Needed

What would break at popBack if each node only knew its successor and not its predecessor?

As a Stack and as a Queue

How does a deque subsume both by ignoring one end, and what restriction recovers each?

Time Complexity

What does each end operation cost, and what makes the bound hold?

The Four End Operations

Why are all four push/pop-at-an-end operations constant time once head, tail, and count exist?

Amortized Cost on a Growable Array Deque

Which operation occasionally triggers a resize, and why does the per-operation average stay constant anyway?

Array vs Linked Constant Factors

Where does the array deque’s contiguous memory beat the linked deque even when both are O(1)?

Space Complexity

How much memory beyond the elements, and where does it come from?

Slack vs Pointer Overhead

Why does the ring-buffer deque carry unused capacity while the linked deque pays two pointers per node?

Auxiliary Space of Operations

Why do the end operations need no scratch space proportional to size?

Sliding-Window Use

How does a monotonic deque maintain a window maximum in O(n) total work?

Why Each Index Enters and Leaves Once

What argument explains the linear total cost even though a single step can pop many elements?

Trade-offs vs Alternatives

When does the extra generality of a deque cost you versus a dedicated stack or queue?

Common Bugs & Edge Cases

What goes wrong with index underflow on popFront, full/empty ambiguity, a missed modulo in either direction, or stale window indices?

Real-World & Interview Uses

Where do work-stealing schedulers, undo/redo, palindrome checks, and sliding-window problems use deques?

Implementation Walkthrough

Before writing code, settle each part.

State & Setup

What fields hold the buffer, capacity, head, tail, and count, and what are their empty-deque values?

pushFront and pushBack Step by Step

In what order do you check fullness, possibly resize, place the element, and move the correct marker in the correct direction?

popFront and popBack Step by Step

In what order do you check emptiness, read the end, move the marker, and update count?

Wraparound in Both Directions

How do you compute the next index when advancing forward versus stepping backward past zero?

Resize Step

How do you copy a possibly-wrapped buffer into a larger one while preserving front-to-back order?

Termination & Return

What does each operation return, and how do you signal an illegal pop on an empty deque?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Monotonic Stack

What It Is & When to Use It

What class of problems — “for each element, find the nearest larger or smaller one” — collapses from \( O(n^2) \) to \( O(n) \) once you keep a stack in sorted order, and what signals that a problem is secretly a monotonic-stack problem?

How the Ordered Stack Works

As you scan the array, what does the stack hold at any moment, and why does keeping it strictly ordered let each new element instantly “answer” the elements it displaces?

The Mental Model of a Staircase

How do you picture the stack as a rising or falling staircase, and what does it mean physically when an incoming element knocks several steps off the top before settling?

The Push-While-Pop Invariant

Before pushing the new element, why do you pop everything that violates the order, and what stays true about the remaining stack after every step?

Increasing vs. Decreasing

How does the direction of monotonicity decide whether you are answering “next greater” versus “next smaller,” and how do left-to-right versus right-to-left scans change which neighbor (next vs. previous) you recover?

Storing Indices vs. Values

Why is it usually better to push indices rather than raw values, and what extra information (distance, span, width) does an index give you that a bare value cannot?

The Next Greater / Next Smaller Pattern

When you finally pop an element, why is the element currently being processed exactly its answer — and what do the indices left on the stack at the end (never popped) tell you about elements that have no greater or smaller neighbor?

Strict vs. Non-Strict Comparison on Ties

How does choosing < versus <= when popping decide whether equal elements count as “greater-or-equal” neighbors, and why must this match the problem’s definition exactly?

Span & Histogram Applications

How do “stock span” and “daily temperatures” reduce to a previous/next comparison, and in the Largest Rectangle in a Histogram, why does the moment you pop a bar reveal the widest rectangle that bar can be the minimum of?

Sentinels

Why does pushing a zero-height bar at the end (and/or a boundary at the start) flush the stack cleanly and remove an annoying “drain the leftovers” edge case?

Time Complexity

Why is the whole scan \( O(n) \) even though a single incoming element can trigger many pops in one step?

Best Case

When does the stack barely move — an already-monotonic input — and why is the per-element work still just a push and one comparison?

Worst & Average Case

Each index is pushed exactly once and popped at most once — why does that cap the total number of pops across the entire run at \( n \), making the amortized cost per element \( O(1) \) and the whole algorithm \( \Theta(n) \)?

Space Complexity

Why is the extra space \( O(n) \) in the worst case (a fully monotonic input that never pops), and what input shape forces the stack to hold every element at once?

Trade-offs vs. Brute Force & Other Structures

When is the naive \( O(n^2) \) double loop actually fine, and when would a different structure (segment tree, sparse table) be preferred over a monotonic stack?

Common Bugs & Edge Cases

Where do bugs creep in — wrong strict-vs-nonstrict comparison on ties, pushing values instead of indices, forgetting to drain the stack at the end, or mishandling an empty or single-element array?

Implementation Walkthrough

Break the technique into the parts you must get right before you write a line.

Setup

What do you initialize the stack and the answer array to, and how do you represent “no neighbor found”?

The Scan Loop

As you iterate, what is the pop condition that compares the incoming element to the stack top, and after popping, what do you record and then push?

The Tricky Step

At the instant you pop, how do you use both the popped index and the current index (and the new top) to compute the answer — the distance, the width, or the neighbor?

Termination & Draining

When the scan ends, what do leftover stack entries mean, and how do sentinels or a final pass assign their answers?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Stacks & Queues: Problem Set

Each problem is an implementation task: fill in the stub in problemset/ and make its test in tests/problemset/ pass. The problems are split into two groups. Foundational problems drill the core LIFO/FIFO mechanics — bracket matching, expression evaluation, and building one structure out of another. Applied Problems weave LeetCode and contest-style challenges in roughly increasing difficulty: monotonic stacks, parsing, scheduling, and queue simulation. Work them in order; later problems lean on patterns introduced earlier.

Foundational

Problem 1: Valid Parentheses

LeetCode: 20. Valid Parentheses

Description

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine whether the input string is valid. A string is valid when every open bracket is closed by a bracket of the same type, brackets close in the correct order, and every closing bracket has a corresponding open bracket of the same type. Solve it in O(n) time using a stack.

Examples

Example 1:

Input:  s = "()[]{}"
Output: true

Every opening bracket is immediately matched by the correct closing bracket.

Example 2:

Input:  s = "([)]"
Output: false

The brackets are not closed in the correct order: ) arrives while [ is still open.

Example 3:

Input:  s = "{[]}"
Output: true

Brackets are correctly nested.

Constraints

• 1 <= s.length <= 10^4
• s consists only of the characters ()[]{}.

Problem 2: Evaluate Reverse Polish Notation

LeetCode: 150. Evaluate Reverse Polish Notation

Description

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish (postfix) Notation. Evaluate the expression and return the resulting integer. The valid operators are +, -, *, and /. Each operand may be an integer or another expression. Division between two integers truncates toward zero. The input is always a valid expression. Use a stack to push operands and apply each operator to the two most recent operands.

Examples

Example 1:

Input:  tokens = ["2","1","+","3","*"]
Output: 9

This evaluates to ((2 + 1) * 3) = 9.

Example 2:

Input:  tokens = ["4","13","5","/","+"]
Output: 6

This evaluates to (4 + (13 / 5)) = 4 + 2 = 6.

Example 3:

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Constraints

• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator +, -, *, /, or an integer in the range [-200, 200].

Problem 3: Min Stack

LeetCode: 155. Min Stack

Description

Design a stack that supports push, pop, top, and retrieving the minimum element, all in constant time. Implement the Problem3 class with:

• Problem3() initializes an empty stack.
• void push(int val) pushes val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

Each operation must run in O(1) time. The trick is to maintain an auxiliary stack that tracks the running minimum alongside the value stack.

Examples

Example 1:

Input:  push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: -3, then 0, then -2

After pushing -2, 0, -3, the minimum is -3. After one pop, the top is 0 and the minimum is -2.

Example 2:

Input:  push(1), push(1), push(0), getMin(), pop(), getMin()
Output: 0, then 1

Duplicate minimums must be tracked so that popping one 0 still leaves the minimum correct.

Example 3:

Input:  push(7), top(), getMin()
Output: 7, then 7

Constraints

• -2^31 <= val <= 2^31 - 1
• pop, top, and getMin are only called on non-empty stacks.
• At most 3 * 10^4 calls are made in total.

Problem 4: Implement Queue using Stacks

LeetCode: 232. Implement Queue using Stacks

Description

Implement a first-in-first-out (FIFO) queue using only two stacks. The queue should support all the standard operations: push, peek, pop, and empty. Implement the Problem4 class with:

• void push(int x) pushes element x to the back of the queue.
• int pop() removes the element from the front of the queue and returns it.
• int peek() returns the element at the front of the queue.
• boolean empty() returns true if the queue is empty.

You may only use standard stack operations (push to top, peek/pop from top, size, and is-empty). Amortized cost per operation should be O(1).

Examples

Example 1:

Input:  push(1), push(2), peek(), pop(), empty()
Output: 1, then 1, then false

peek() and the first pop() both return 1 (FIFO order). The queue still holds 2, so empty() is false.

Example 2:

Input:  push(5), pop(), empty()
Output: 5, then true

Example 3:

Input:  push(3), push(4), pop(), push(5), pop(), pop(), empty()
Output: 3, then 4, then 5, then true

Constraints

• 1 <= x <= 9
• At most 100 calls are made to push, pop, peek, and empty.
• All calls to pop and peek are valid (the queue is non-empty).

Problem 5: Implement Stack using Queues

LeetCode: 225. Implement Stack using Queues

Description

Implement a last-in-first-out (LIFO) stack using only one or two queues. The stack should support all the standard operations: push, top, pop, and empty. Implement the Problem5 class with:

• void push(int x) pushes element x onto the stack.
• int pop() removes the element on the top of the stack and returns it.
• int top() returns the element on the top of the stack.
• boolean empty() returns true if the stack is empty.

You may only use standard queue operations (push to back, peek/pop from front, size, and is-empty).

Examples

Example 1:

Input:  push(1), push(2), top(), pop(), empty()
Output: 2, then 2, then false

top() and the first pop() both return 2 (LIFO order). The stack still holds 1, so empty() is false.

Example 2:

Input:  push(8), pop(), empty()
Output: 8, then true

Example 3:

Input:  push(1), push(2), push(3), pop(), top()
Output: 3, then 2

Constraints

• 1 <= x <= 9
• At most 100 calls are made to push, pop, top, and empty.
• All calls to pop and top are valid (the stack is non-empty).

Problem 6: Sliding Window Maximum

LeetCode: 239. Sliding Window Maximum

Description

You are given an array of integers nums and a window size k. A window of size k slides from the very left of the array to the very right. At each step you can see only the k numbers inside the window, and the window moves right by one position. Return an array of the maximum value in each window. Use a monotonic deque to achieve O(n) total time, evicting indices that fall out of the window from the front and indices of smaller values from the back.

Examples

Example 1:

Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7], with maximums 3, 3, 5, 5, 6, 7.

Example 2:

Input:  nums = [1], k = 1
Output: [1]

Example 3:

Input:  nums = [9,8,7,6,5], k = 2
Output: [9,8,7,6]

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Applied Problems

Problem 7: Baseball Game

LeetCode: 682. Baseball Game

Description

You are keeping the scores for a game with a series of operations given as an array of strings operations. Maintain a record (a stack) of valid scores and apply each operation:

• An integer x: record a new score of x.
• "+": record a new score that is the sum of the previous two scores.
• "D": record a new score that is double the previous score.
• "C": invalidate and remove the previous score from the record.

It is guaranteed that every operation is valid when it is applied. Return the sum of all the scores remaining in the record after applying every operation.

Examples

Example 1:

Input:  operations = ["5","2","C","D","+"]
Output: 30

Record 5, record 2, cancel 2 (record [5]), double to 10 (record [5,10]), sum to 15 (record [5,10,15]). Total = 5 + 10 + 15 = 30.

Example 2:

Input:  operations = ["5","-2","4","C","D","9","+","+"]
Output: 27

The record ends as [5, -2, 9, 18, 27], summing to 27.

Example 3:

Input:  operations = ["1","C"]
Output: 0

Constraints

• 1 <= operations.length <= 1000
• operations[i] is "C", "D", "+", or a string representing an integer in [-3 * 10^4, 3 * 10^4].
• For "+" operations, there are always at least two previous scores.
• For "C" and "D" operations, there is always at least one previous score.

Problem 8: Backspace String Compare

LeetCode: 844. Backspace String Compare

Description

Given two strings s and t, return true if they are equal when both are typed into empty text editors. The character '#' means a backspace character, which deletes the character before it (if any). Note that backspacing on an empty editor leaves it empty. Build each resulting string with a stack of characters and compare the results.

Examples

Example 1:

Input:  s = "ab#c", t = "ad#c"
Output: true

Both s and t become "ac" after applying backspaces.

Example 2:

Input:  s = "a##c", t = "#a#c"
Output: true

Both become "c".

Example 3:

Input:  s = "a#c", t = "b"
Output: false

s becomes "c" while t stays "b".

Constraints

• 1 <= s.length, t.length <= 200
• s and t contain only lowercase letters and '#' characters.

Problem 9: Remove All Adjacent Duplicates In String

LeetCode: 1047. Remove All Adjacent Duplicates In String

Description

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. Repeatedly make duplicate removals on s until no more can be made. Return the final string after all such removals; the answer is guaranteed to be unique. A stack makes each removal O(1): push each character, but if it equals the top of the stack, pop instead.

Examples

Example 1:

Input:  s = "abbaca"
Output: "ca"

Remove "bb" to get "aaca", then remove "aa" to get "ca".

Example 2:

Input:  s = "azxxzy"
Output: "ay"

Remove "xx" to get "azzy", then remove "zz" to get "ay".

Example 3:

Input:  s = "aaaaaa"
Output: ""

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

Problem 10: Make The String Great

LeetCode: 1544. Make The String Great

Description

Given a string s of lowercase and uppercase English letters, a good string is one with no two adjacent characters s[i] and s[i + 1] where one is the lowercase version and the other is the uppercase version of the same letter (for example, "aA" or "Aa"). To make the string good, repeatedly remove such adjacent bad pairs until none remain. Return the resulting good string; the answer is unique. Use a stack: push each character unless it forms a bad pair with the current top, in which case pop instead.

Examples

Example 1:

Input:  s = "leEeetcode"
Output: "leetcode"

Removing "eE" (or "Ee") leaves "leetcode", which has no bad pairs.

Example 2:

Input:  s = "abBAcC"
Output: ""

"bB" is removed leaving "aAcC", then "aA" and "cC" are removed, leaving "".

Example 3:

Input:  s = "s"
Output: "s"

Constraints

• 1 <= s.length <= 100
• s contains only lowercase and uppercase English letters.

Problem 11: Next Greater Element I

LeetCode: 496. Next Greater Element I

Description

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each nums1[i], find the index of nums1[i] in nums2 and determine its next greater element in nums2. Return an array ans of the same length as nums1 where ans[i] is the next greater element described above, or -1 if it does not exist. A monotonic decreasing stack over nums2 lets you precompute every next greater element in O(n).

Examples

Example 1:

Input:  nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]

For 4, there is no greater element to its right, so -1. For 1, the next greater is 3. For 2, there is no greater element to its right, so -1.

Example 2:

Input:  nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]

The next greater element of 2 is 3; 4 has none.

Example 3:

Input:  nums1 = [1], nums2 = [1]
Output: [-1]

Constraints

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• All integers in nums1 and nums2 are unique, and nums1 is a subset of nums2.

Problem 12: Daily Temperatures

LeetCode: 739. Daily Temperatures

Description

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0. Use a monotonic decreasing stack of indices: when a warmer day arrives, pop every cooler day and record the gap, giving O(n) total time.

Examples

Example 1:

Input:  temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Day 0 (73) waits 1 day for 74; day 2 (75) waits 4 days for 76; the last two days have no warmer future day.

Example 2:

Input:  temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input:  temperatures = [30,60,90]
Output: [1,1,0]

Constraints

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

Problem 13: Next Greater Element II

LeetCode: 503. Next Greater Element II

Description

Given a circular integer array nums (the next element of nums[nums.length-1] is nums[0]), return the next greater number for every element. The next greater number of an element x is the first greater number traversing the array in circular order; if it does not exist, the answer is -1. Process the array twice with a monotonic decreasing stack of indices, using i % n to wrap around, so the whole thing runs in O(n).

Examples

Example 1:

Input:  nums = [1,2,1]
Output: [2,-1,2]

The first 1’s next greater is 2; 2 has none; the last 1 wraps around to find 2.

Example 2:

Input:  nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

Example 3:

Input:  nums = [5,4,3,2,1]
Output: [-1,5,5,5,5]

Constraints

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

Problem 14: Simplify Path

LeetCode: 71. Simplify Path

Description

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Transform this absolute path into its simplified canonical path. In a Unix file system, a single period '.' refers to the current directory, a double period '..' refers to the parent directory, and any number of consecutive slashes is treated as a single slash. The canonical path must start with a single '/', have directories separated by exactly one '/', not end with a trailing '/', and contain no '.' or '..' components. Split on slashes and use a stack of directory names, popping on each '..'.

Examples

Example 1:

Input:  path = "/home//foo/"
Output: "/home/foo"

Multiple slashes collapse into one and the trailing slash is dropped.

Example 2:

Input:  path = "/a/./b/../../c/"
Output: "/c"

. is ignored; each .. pops the previous directory, leaving only c.

Example 3:

Input:  path = "/../"
Output: "/"

Going above the root directory stays at the root.

Constraints

• 1 <= path.length <= 3000
• path consists of English letters, digits, periods '.', slashes '/', and underscores '_'.
• path is a valid absolute Unix path.

Problem 15: Asteroid Collision

LeetCode: 735. Asteroid Collision

Description

We are given an array asteroids of integers representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed. Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one explodes; if both are the same size, both explode. Two asteroids moving in the same direction will never meet. A stack models the rightward-moving survivors: a leftward asteroid collides with the top of the stack until it is destroyed or survives.

Examples

Example 1:

Input:  asteroids = [5,10,-5]
Output: [5,10]

The 10 and -5 collide, and the -5 explodes. The 10 and 5 never meet because they move in the same direction.

Example 2:

Input:  asteroids = [8,-8]
Output: []

They are the same size, so both explode.

Example 3:

Input:  asteroids = [10,2,-5]
Output: [10]

The -5 destroys the 2, then collides with the 10 and explodes.

Constraints

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Problem 16: Number of Recent Calls

LeetCode: 933. Number of Recent Calls

Description

You have a RecentCounter class which counts the number of recent requests within a certain time frame. Implement the Problem16 class:

• Problem16() initializes the counter with zero recent requests.
• int ping(int t) adds a new request at time t (in milliseconds) and returns the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call. A FIFO queue of timestamps lets you drop everything older than t - 3000 from the front and return the queue size.

Examples

Example 1:

Input:  ping(1), ping(100), ping(3001), ping(3002)
Output: 1, 2, 3, 3

At 3001, the request at time 1 is exactly 3000 ms old and still counts. At 3002, the request at time 1 (3001 ms old) is evicted, leaving 3.

Example 2:

Input:  ping(1000)
Output: 1

Example 3:

Input:  ping(1), ping(2), ping(3)
Output: 1, 2, 3

Constraints

• 1 <= t <= 10^9
• Each test case calls ping with strictly increasing values of t.
• At most 10^4 calls are made to ping.

Problem 17: Validate Stack Sequences

LeetCode: 946. Validate Stack Sequences

Description

Given two integer arrays pushed and popped, each with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack. Simulate the process: push each value from pushed in order, and whenever the top of the stack equals the next value to pop, pop it. The sequence is valid if the stack is empty at the end.

Examples

Example 1:

Input:  pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

One valid order: push 1,2,3,4, pop 4, push 5, pop 5,3,2,1.

Example 2:

Input:  pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false

After popping 4 and 3, the value 1 cannot be popped before 2, so this is impossible.

Example 3:

Input:  pushed = [1,2], popped = [2,1]
Output: true

Constraints

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• All the elements of pushed are unique.
• popped.length == pushed.length
• popped is a permutation of pushed.

Problem 18: Decode String

LeetCode: 394. Decode String

Description

Given an encoded string, return its decoded string. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. You may assume the input is always valid, with no extra white spaces and well-formed brackets. The digits only indicate repeat counts and never appear inside the decoded text. Use two stacks (one for counts, one for partial strings) so that opening a bracket pushes context and closing a bracket repeats and merges.

Examples

Example 1:

Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

3[a] expands to "aaa" and 2[bc] expands to "bcbc".

Example 2:

Input:  s = "3[a2[c]]"
Output: "accaccacc"

The inner 2[c] becomes "cc", so a2[c] is "acc", repeated 3 times.

Example 3:

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• s is guaranteed to be a valid input.
• All integers in s are in the range [1, 300].

Problem 19: Remove K Digits

LeetCode: 402. Remove K Digits

Description

Given a string num representing a non-negative integer and an integer k, return the smallest possible integer (as a string) after removing exactly k digits from num. Use a monotonic increasing stack: while you still have removals left and the current digit is smaller than the top of the stack, pop. Finally, strip any leading zeros from the result, and return "0" if the result is empty.

Examples

Example 1:

Input:  num = "1432219", k = 3
Output: "1219"

Removing the digits 4, 3, and 2 leaves the smallest number 1219.

Example 2:

Input:  num = "10200", k = 1
Output: "200"

Removing the leading 1 gives 0200, which becomes 200 after stripping the leading zero.

Example 3:

Input:  num = "10", k = 2
Output: "0"

Removing both digits leaves nothing, so the answer is "0".

Constraints

• 1 <= k <= num.length <= 10^5
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

Problem 20: Online Stock Span

LeetCode: 901. Online Stock Span

Description

Design an algorithm that collects daily price quotes for a stock and returns the span of that stock’s price for the current day. The span of the stock’s price on a given day is the maximum number of consecutive days (starting from that day and going backward) for which the price was less than or equal to the price of that day. Implement the Problem20 class:

• Problem20() initializes the object.
• int next(int price) returns the span of the stock’s price given today’s price.

A monotonic decreasing stack of (price, span) pairs lets each next call run in amortized O(1).

Examples

Example 1:

Input:  next(100), next(80), next(60), next(70), next(60), next(75), next(85)
Output: 1, 1, 1, 2, 1, 4, 6

At price 75, the prior days 60, 70, 60 are all <= 75, giving a span of 4. At 85, the six most recent days are all <= 85, giving a span of 6.

Example 2:

Input:  next(10), next(20), next(30)
Output: 1, 2, 3

Each price is at least the previous, so the span keeps growing.

Example 3:

Input:  next(50), next(40), next(30)
Output: 1, 1, 1

Constraints

• 1 <= price <= 10^5
• At most 10^4 calls are made to next.

Problem 21: Score of Parentheses

LeetCode: 856. Score of Parentheses

Description

Given a balanced parentheses string s, return the score of the string based on the following rules: "()" has a score of 1; AB has a score of A + B where A and B are balanced parentheses strings; and (A) has a score of 2 * A where A is a balanced parentheses string. Use a stack that holds the running score of each nesting level: ( pushes a new level, ) pops and folds the inner score into the level below.

Examples

Example 1:

Input:  s = "()"
Output: 1

A single matched pair scores 1.

Example 2:

Input:  s = "(())"
Output: 2

The inner () scores 1, and wrapping it in parentheses doubles it to 2.

Example 3:

Input:  s = "()()"
Output: 2

Two adjacent pairs each score 1, summing to 2.

Constraints

• 2 <= s.length <= 50
• s consists of only '(' and ')'.
• s is a balanced parentheses string.

Problem 22: Sum of Subarray Minimums

LeetCode: 907. Sum of Subarray Minimums

Description

Given an array of integers arr, find the sum of min(b) over every (contiguous) subarray b of arr. Because the answer may be large, return it modulo 10^9 + 7. The efficient O(n) approach uses a monotonic stack to find, for each element, how many subarrays it is the minimum of — namely the span to the nearest strictly smaller element on the left and the nearest smaller-or-equal element on the right.

Examples

Example 1:

Input:  arr = [3,1,2,4]
Output: 17

The subarray minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, which sum to 17.

Example 2:

Input:  arr = [11,81,94,43,3]
Output: 444

Example 3:

Input:  arr = [1]
Output: 1

Constraints

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 3 * 10^4

Problem 23: Largest Rectangle in Histogram

LeetCode: 84. Largest Rectangle in Histogram

Description

Given an array of integers heights representing the histogram’s bar heights where the width of each bar is 1, return the area of the largest rectangle in the histogram. Maintain a monotonic increasing stack of bar indices: when a bar shorter than the stack top appears, pop and compute the area of the rectangle that used the popped bar as its limiting height, with the width spanning to the new boundaries. This yields an O(n) solution.

Examples

Example 1:

Input:  heights = [2,1,5,6,2,3]
Output: 10

The largest rectangle spans bars of heights 5 and 6, giving area 5 * 2 = 10.

Example 2:

Input:  heights = [2,4]
Output: 4

The rectangle of height 4 and width 1, or height 2 and width 2, both give 4.

Example 3:

Input:  heights = [1,1,1,1]
Output: 4

Constraints

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Problem 24: Basic Calculator

LeetCode: 224. Basic Calculator

Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it and return the result. The expression may contain non-negative integers, the binary '+' and '-' operators, the unary '-' (negation), and parentheses '(' and ')', possibly with spaces. You are not allowed to use any built-in function that evaluates strings as expressions. Use a stack to save the running result and sign whenever a '(' is opened, restoring them when the matching ')' is reached.

Examples

Example 1:

Input:  s = "1 + 1"
Output: 2

Simple addition.

Example 2:

Input:  s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

The inner groups evaluate to 1 + 11 - 3 = 9 and 14, summing to 23.

Example 3:

Input:  s = " 2-1 + 2 "
Output: 3

Constraints

• 1 <= s.length <= 3 * 10^5
• s consists of digits, '+', '-', '(', ')', and spaces ' '.
• s represents a valid expression.
• The '+' and '-' operators always have a valid operand; '-' can also be unary.
• Every ')' has a matching '(', and the integer values fit in a 32-bit signed integer.

Recursion Deep

What Recursion Is & When to Reach for It

What kind of problem is naturally “the same problem on smaller input,” and when is recursion clearer than a loop?

Base Case and Recursive Case

What stops the recursion, and what shrinks the problem toward that stop?

Why Every Path Must Reach a Base Case

What guarantees that repeated shrinking actually lands on the base case rather than running forever?

The Two-Part Mental Model

How do you separate “what the smallest case answers” from “how a bigger case builds on a smaller one”?

Trusting the Recursion

Why can you assume the recursive call already works on the smaller input while you write the larger case?

Translating a Recursive Idea to Code

How do you turn “solve smaller, then combine” into a method that calls itself?

The Recursive Leap of Faith in Practice

Where in the method do you make the call, and where do you use its result?

The Call Stack and Frames

What gets pushed on each call, and where do parameters and locals live during the call?

What a Single Frame Holds

What information must a frame keep so it can resume after its recursive call returns?

Unwinding the Stack

What happens to each frame’s pending work as control returns up the chain?

Work on the Way Down vs the Way Up

When does computation happen before the recursive call versus after it returns, and how does that change the result order?

Tail vs Non-Tail Recursion

When is the recursive call the last thing a frame does, and why does that distinction matter for the stack?

Why Tail Calls Can Be Loop-Like

What about a tail call means the current frame has nothing left to do, and what could an optimizer exploit?

Multiple and Tree Recursion

What changes about shape and cost when one call spawns two or more recursive calls?

Redundant Work and Memoization

How does caching results stop recomputing the same subproblem, and how does that collapse the cost?

Recursion to Iteration

How would an explicit stack mimic what the runtime does for you automatically?

What You Have to Track by Hand

Which pieces of frame state must you push manually that the language used to manage for you?

Time Complexity

How do you reason about the cost from the call structure rather than deriving a recurrence?

Counting Calls Times Work per Call

Why is total cost roughly the number of calls multiplied by the non-recursive work each does?

Linear vs Exponential Branching

Why does single recursion tend toward linear cost while unmemoized branching can explode exponentially?

How Memoization Changes the Count

Why does caching cut the cost to roughly the number of distinct subproblems?

Space Complexity

Where does recursion spend memory beyond what an equivalent loop would?

Call-Stack Depth Dominates

Why is the peak stack depth, not the total number of calls, the figure that drives space?

Depth by Recursion Shape

Why does linear recursion cost depth proportional to n while balanced branching costs only depth proportional to its height?

Iterative Versions and Their Own Stack

When you convert to a loop with an explicit stack, where does the space actually go, and is it really saved?

Stack Depth and Overflow

What input depth blows past the available frames and crashes, and how do you bound or restructure it?

Common Bugs & Edge Cases

What goes wrong with a missing base case, a step that doesn’t shrink, off-by-one on the boundary, or shared mutable state across calls?

Real-World & Interview Uses

Where do traversals, backtracking, parsing, and divide-and-conquer lean on recursion?

Implementation Walkthrough

Before writing code, decide each part.

Signature & Setup

What parameters carry the shrinking input and any accumulated result, and what does the caller pass first?

The Base Case Branch

Which condition do you test first, and what do you return immediately without recursing?

The Recursive Branch

How do you build a strictly smaller argument, make the call, and use its return value?

Combining Sub-Results

Where does the work that turns the smaller answer into the bigger one belong, before or after the call?

Termination & Return

What does the top-level call ultimately hand back, and how do you confirm every path returns?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Divide and Conquer

What the Paradigm Is & When It Applies

What signals that a problem can be split, solved in pieces, and merged, and when does that beat a direct approach?

Divide, Conquer, Combine

What are the three phases, and which one usually dominates the cost?

Divide

How do you split the input into smaller, same-shaped subproblems, and what makes a split “clean”?

Conquer

How does recursion solve each piece, and where does the base case end the descent?

Combine

How do you merge the sub-solutions into a full answer, and why is this often the hard part?

Subproblem Independence

Why must the pieces not overlap for this paradigm, rather than dynamic programming, to fit?

Contrast with Overlapping Subproblems

What does it look like when subproblems repeat, and why does that push you toward memoization instead?

The Mental Model

How do you picture the recursion as a tree, with the original problem at the root and base cases at the leaves?

Where Work Happens in the Tree

At which nodes does the divide cost land, and at which does the combine cost land?

Mapping the Structure to Code

How does the divide/conquer/combine shape become a recursive method skeleton?

The Base Case First

Why do you test for the smallest solvable size before attempting to split?

A Worked Example: Merge Sort

How do split-in-half, sort-each, and merge realize each phase?

The Merge Step

How do two sorted halves combine into one sorted whole in a single linear pass?

Why Merge Sort Is Stable and Predictable

What about the merge keeps equal elements in order and avoids a bad worst case?

Another Lens: Binary Search

How is halving the search space a degenerate divide-and-conquer with one recursive call and no combine?

Where the Cost Comes From

Which dominates: the splitting, the recursive calls, or the combining, and how does that decide the total?

Time Complexity

How do you reason about the running time without formally solving a recurrence?

Counting Work per Level

Why is the total often “work per level times number of levels,” and what sets each factor?

When Combine Is the Bottleneck

Why does a linear combine over logarithmically many levels give the classic n log n shape?

When Branching Is the Bottleneck

Why can many subproblems per level make the leaf count, not the combine, dominate the cost?

Best, Average, and Worst Triggers

What kinds of splits keep the balanced bound, and what unbalanced split degrades it?

Space Complexity

Where does divide-and-conquer spend memory, and how much?

Recursion-Stack Depth

Why does the depth of the recursion tree, not its total node count, set the stack space?

Auxiliary Buffers in Combine

Why does a step like merge need scratch space, and how big is it relative to the input?

In-Place vs Out-of-Place Variants

What do you trade in code complexity to shrink the auxiliary space toward constant?

Trade-offs vs Alternatives

When does divide-and-conquer beat a straightforward linear scan or a DP table, and when is its overhead not worth it?

Common Bugs & Edge Cases

What breaks on uneven splits, a wrong or missing base case, an off-by-one in the midpoint, or a combine that mishandles leftovers?

Real-World & Interview Uses

Where do sorting, search, closest-pair, fast multiplication, and parallelizable work use this paradigm?

Implementation Walkthrough

Before writing code, decide each part.

Signature & Setup

What bounds or sub-ranges does the recursive method take, and what does the top-level caller pass?

The Base Case Branch

Which smallest size do you solve directly, and what do you return without recursing?

The Divide Step

How do you compute the split point and form the sub-ranges without losing or duplicating elements?

The Recursive Calls

In what order do you solve the sub-ranges, and where do you store their results?

The Combine Step

How do you walk the sub-results together, and where does any scratch buffer live?

Termination & Return

What does the top-level call hand back, and how do you confirm every element is accounted for?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Backtracking

What It’s For & Why It Matters

Why systematically build candidate solutions one choice at a time and abandon (“backtrack”) a partial solution the moment it can’t possibly work — instead of generating every combination blindly?

The Core Idea

How does backtracking turn “search all configurations” into “grow a partial solution, and retreat the instant it becomes hopeless,” and why is retreating the whole point?

The Mental Model

How do you picture the search as walking down into a choice, exploring everything reachable from it, then stepping back up to try the next choice — like exploring a maze with a piece of chalk?

Choose / Explore / Un-choose

What are the three steps of the backtracking skeleton, and why is the “un-choose” (undo the last choice before returning) the part people forget?

Why Un-choose Restores State

Why must the partial solution look exactly as it did before a choice was made once that branch returns, and what breaks downstream if the undo is skipped?

The State-Space Tree

Why does every backtracking problem correspond to a DFS over a tree of partial choices, what does each node represent, and what do the leaves represent?

Branching Factor & Depth

At a given node, how many children does it have (the branching factor), and how deep can a root-to-leaf path get — and why do those two numbers govern everything about the cost?

Pruning

How does rejecting an invalid partial solution early (a “constraint check”) cut off an entire subtree of work, and why is that where the real speedup comes from even though it doesn’t change the worst-case Big-O?

Where to Place the Check

Why test feasibility as early as possible — at the moment of choosing rather than only at a complete leaf — and how much work does an early prune save versus a late one?

Recursion Structure

What is the base case (a complete candidate or a dead end), what is the recursive case (loop over choices, recurse, undo), and how do those map onto a single function?

Recording Solutions

When you reach a valid leaf, why must you usually copy the current partial solution into the results rather than store a reference to the mutable working state?

Classic Examples

How do subsets, permutations, combinations, and N-queens each instantiate the same skeleton with a different choice set and constraint?

Subsets vs Permutations

How do the choice sets differ — at each step include-or-skip the current element (subsets) vs. pick an unused element (permutations) — and why does that change the tree’s shape and leaf count?

N-Queens

Why is N-queens the canonical backtracking problem — how do column and diagonal constraints let you prune most placements before the board is ever full?

Time Complexity

How do you reason about the running time in terms of the state-space tree without solving a formula?

Counting the Nodes

Why is the cost proportional to the number of nodes the search actually visits, and how does that relate to branching factor raised to the depth in the unpruned worst case?

Work Per Node

Beyond the recursion itself, why does each node cost the time of its constraint check and the work to record a solution at a leaf, and why can that add a factor on top of the node count?

Why Pruning Helps in Practice

Why is the worst case typically exponential, yet aggressive pruning can make a problem like N-queens solve in well under the unpruned bound, even though the Big-O is unchanged?

Space Complexity

Where does backtracking spend memory beyond the input?

Recursion-Stack Depth

Why is the call stack bounded by the depth of the state-space tree (the longest partial solution), not by the total number of nodes explored?

The Working State

Why does the in-progress candidate (the board, the chosen-so-far list, the used-markers) cost space proportional to the depth, and why is reusing one mutable buffer cheaper than copying at every step?

Common Bugs & Edge Cases

What breaks if you forget to undo a choice, mutate shared state without restoring it, copy the result list at the wrong time, check constraints too late, or mishandle the empty-input base case?

Connections

How does backtracking relate to plain recursion, to DFS, to dynamic programming (when overlapping subproblems exist), and to branch-and-bound (when you also carry a bound to prune)?

Real-World & Interview Uses

Where do constraint solvers, Sudoku and crossword fillers, parsing, regex matching, and combinatorial generation rely on backtracking?

Implementation Walkthrough

Before writing code, decide each part.

Setup & The Result Container

What state do you carry into the recursion (the working candidate, any used-markers, the start index), and where does the list that collects finished solutions live?

The Base Case Branch

How do you detect a complete candidate or a dead end, and what do you do — record a copy, or simply return?

The Main Loop Over Choices

How do you iterate the available choices at this node, apply the constraint check to skip infeasible ones, and make a choice before recursing?

The Un-choose Step

Right after the recursive call returns, how do you undo the choice so the next iteration starts from a clean state?

Termination & Return

How does the whole search finish once the root’s loop is exhausted, and what does the top-level call hand back?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Closest Pair of Points

The Problem & Why It Matters

Given points in a plane, what exactly are you trying to find, and where does this come up?

Brute-Force Baseline

What does checking every pair cost, and why is it worth beating?

The Divide-and-Conquer Idea

How does splitting the plane turn one hard search into two smaller ones plus a merge?

The Mental Model

How do you picture the points cut by a vertical line, with each half solved on its own before reconciling the boundary?

Divide by Median x

How does a vertical line through the median x split the points into two balanced halves?

Why the Median Keeps Halves Balanced

What goes wrong for the cost if the split is lopsided instead of even?

Conquer Each Half

How does recursion find the closest pair within the left and the right sets, and what does each call return?

The Strip Problem

Why might the true closest pair straddle the dividing line, and how do you catch it?

Strip of Width Two Delta

Which points near the dividing line still need checking, and why only those within delta of the line?

The Constant-Neighbor Argument

Why does each strip point, scanned in y order, compare against only a fixed number of following points?

Combining the Three Candidates

How do you pick the final answer from the left best, the right best, and the strip best?

Keeping the Combine Linear

How does presorting by y, or merging sorted halves on the way up, avoid re-sorting inside the strip?

Two Sort Orders at Once

Why does the algorithm want points ordered by x for the split but by y for the strip scan, and how do you maintain both?

Recursion Structure

What are the base case and the two recursive calls, and how deep does the recursion go?

The Base Case

At what small point count do you stop recursing and just brute-force, and why is that safe?

Time Complexity

How do you reason about the running time without solving a recurrence formally?

Cost per Level

Why is the combine (strip build plus constant-neighbor scan) linear at each level of the recursion?

Why It Beats Brute Force

How does linear-combine work over logarithmically many balanced levels land below the quadratic baseline?

What the Presort Costs

Why is the one-time sort by x not the dominant term once the recursion is running?

Space Complexity

Where does this algorithm spend memory beyond the input points?

Recursion Depth

Why is the stack depth tied to how many times the point set can be halved?

Strip and Sorted Buffers

Why does building the strip and keeping y-sorted order need extra space proportional to the points involved?

Common Bugs & Edge Cases

What goes wrong with duplicate points, fewer than two points, ties at the median, coincident points giving distance zero, or an unsorted strip?

Real-World & Interview Uses

Where do collision detection, clustering, map labeling, and spatial queries rely on closest-pair?

Implementation Walkthrough

Before writing code, decide each part.

Setup & Presort

Which arrays do you sort up front, and by which coordinate, before the first recursive call?

The Base Case Branch

At what size do you switch to brute force, and how do you compute the minimum directly there?

The Divide Step

How do you find the median x and partition points into left and right without breaking the sorted orders?

The Two Recursive Calls

How do you call each half and capture the smaller of the two returned distances as delta?

Building and Scanning the Strip

How do you collect points within delta of the line, order them by y, and run the bounded-neighbor comparison?

Termination & Return

What single value (and pair) does each call return, and how does the top level report the global closest pair?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Fast Exponentiation

The Problem & When to Use It

When you need a power of something with a huge exponent, why not just loop and multiply?

Naive Repeated Multiplication

Why is multiplying one factor at a time wasteful, and exactly how many multiplications does it spend?

The Squaring Insight

How does \( x^n = (x^{n/2})^2 \) cut the remaining work roughly in half at each step?

Why Halving the Exponent Is the Whole Trick

What is the key realization that lets you reuse one squared value instead of recomputing from scratch?

Odd vs Even Exponents

What extra factor of \( x \) appears when the exponent is odd, and how do you fold it in?

Handling the Parity at Each Step

How does testing the lowest bit of the exponent decide whether you multiply in an extra factor?

Recursive Top-Down Version

How do you code “halve the exponent, square the result, multiply once if odd”?

Base Case

What exponent ends the recursion, and what value does it return?

Why You Square the Returned Value, Not Recompute

What goes wrong for the cost if you call the recursion twice instead of squaring its single result?

Iterative Binary Version

How do the bits of the exponent tell you when to square and when to multiply?

Reading the Exponent’s Bits

How does scanning \( n \) bit by bit drive an accumulator alongside a running square?

Why the Running Square Tracks Powers of Two

What does the repeatedly-squared base represent at the moment you inspect each bit?

The Mental Model

How do you see the exponent’s binary representation as a recipe of “square always, multiply on a set bit”?

Modular Exponentiation

How does taking a remainder at each step keep the intermediate numbers small for cryptographic use?

Why You Can Reduce at Every Step

What property of modular arithmetic lets you take the remainder after each multiply without changing the result?

Time Complexity

How do you reason about the cost without deriving a recurrence?

Counting the Multiplications

Why does halving the exponent each step give a number of multiplications tied to the bit-length of \( n \)?

Recursive vs Iterative Step Count

Why do both forms perform essentially the same number of squarings and multiplies?

When Operand Size Matters

Why does the per-multiply cost stop being constant once the numbers grow into bignum territory?

Space Complexity

Where does each version spend memory?

Iterative Constant Space

Why does the loop need only a couple of accumulator variables regardless of the exponent?

Recursive Call-Stack Depth

Why does the top-down version cost stack depth proportional to the bit-length of \( n \)?

Common Bugs & Edge Cases

What goes wrong with exponent zero, negative exponents, integer overflow, a missing modulo, or squaring before handling the odd factor?

Real-World & Interview Uses

Where do cryptography, hashing, matrix-power tricks, and modular arithmetic rely on this?

Implementation Walkthrough

Before writing code, decide each part.

Signature & Setup

What does the method take, and what accumulator and running-base variables do you initialize?

The Base Case or Loop Guard

What condition ends the recursion, or what condition keeps the loop running over the exponent’s bits?

The Square-and-Maybe-Multiply Step

In what order do you inspect the current bit, multiply into the accumulator if set, and square the base?

Optional Modular Reduction

Where exactly do you take the remainder so numbers stay bounded?

Termination & Return

What does the method return once the exponent is exhausted, and what should it return for exponent zero?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Karatsuba Multiplication

The Problem & When It Pays Off

Why do we need a faster multiply for very large numbers, and at what size does the overhead start to win?

Schoolbook Multiply

Why does the grade-school digit-by-digit method scale quadratically, and exactly what work does it duplicate?

Splitting Numbers in Half

How do you write each factor as \( a \cdot 10^{m} + b \) (or the base-2 equivalent)?

Choosing the Split Point

How does the digit count decide where to cut, and what do you do when the length is odd?

The Four-Product Expansion

When you multiply the split forms out, which four partial products appear, and which two are the “corners”?

Why Naively This Is Still Four Multiplies

What makes the straightforward expansion no better than schoolbook in the number of big multiplications?

The Three-Multiplication Trick

How does computing \( (a+b)(c+d) \) let you recover the middle term and drop one of the four products?

Recovering the Middle Term

Which two already-computed products do you subtract from \( (a+b)(c+d) \) to isolate the cross term?

The Mental Model

How do you see three smaller multiplications replacing four, recursively, as the source of the speedup?

Combining the Pieces

How do the three partial products recombine with shifts and a subtraction into the final number?

Where the Shifts Come From

Why does each partial product get multiplied by a specific power of the base when reassembled?

Recursion Structure

How do the three multiplications become three recursive calls, and what is the base case?

The Call Stack

How deep does the recursion go, and what does each frame compute before returning its partial product?

The Base Case

At what operand size do you stop recursing and just multiply directly, and why?

Mapping It to Code

How do you handle the shifts, the additions, the subtraction, and the carries when assembling the result?

Time Complexity

How do you reason about the cost without formally solving the recurrence?

Three Subproblems of Half Size

Why does replacing four half-size multiplies with three change the growth rate at all?

The Resulting Exponent

Why does three-way branching on half-size inputs land near \( n^{1.585} \) rather than \( n^2 \)?

The Hidden Constant Factor

Why do the extra additions, subtractions, and shifts inflate the constant, hurting small inputs?

Space Complexity

Where does Karatsuba spend memory beyond the operands?

Recursion-Stack Depth

Why is the stack depth tied to how many times the operands can be halved?

Temporary Sums and Partial Products

Why do the intermediate sums \( a+b \), \( c+d \), and the three products need scratch space at each level?

Trade-offs vs Alternatives

Why is Karatsuba slower than schoolbook on small inputs, and where do FFT-based methods eventually take over?

Common Bugs & Edge Cases

What goes wrong with odd splits, leading zeros, a negative middle term, mismatched operand lengths, or a missed shift?

Real-World & Interview Uses

Where do bignum libraries and arbitrary-precision arithmetic use this algorithm?

Implementation Walkthrough

Before writing code, decide each part.

Signature & Setup

What representation do the operands use, and how do you read their length to pick a split point?

The Base Case Branch

At what size do you fall back to direct multiplication, and what do you return there?

Splitting Into High and Low Halves

How do you extract \( a, b \) and \( c, d \) from each operand without losing digits?

The Three Recursive Products

Which three products do you compute, and how do you form the \( (a+b) \) and \( (c+d) \) inputs?

Recombining With Shifts

How do you apply the powers of the base and the middle-term subtraction to assemble the result?

Termination & Return

What final number does the top-level call return, and how do you confirm carries were handled?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Recursion & Divide and Conquer: Problem Set

Each problem is an implementation task: fill in the matching stub in problemset/ and make its test in tests/problemset/ pass. The set opens with Foundational warm-ups that drill the core recursive shapes — base case, single recursive step, and divide-and-combine — then moves through Applied Problems that weave real LeetCode interview questions together with contest-style challenges, ordered easy to hard. Lean on recursion and divide and conquer throughout: split the input, solve the pieces, and combine.

Foundational

Problem 1: Sum of Digits

Description

Given a non-negative integer n, return the sum of its base-10 digits. Solve it recursively: the last digit is n % 10, and the rest of the number is n / 10. Do not use any loops.

Examples

Example 1:

Input:  n = 12345
Output: 15

1 + 2 + 3 + 4 + 5 = 15.

Example 2:

Input:  n = 0
Output: 0

Zero has a single digit whose sum is 0 — this is the base case.

Example 3:

Input:  n = 9
Output: 9

A single-digit number is its own digit sum.

Constraints

• 0 <= n <= 2,000,000,000

Problem 2: Recursive Power

Description

Compute b raised to the power e, where e is a non-negative integer, using exponentiation by squaring. Halve the exponent at each step: b^e = (b^(e/2))^2 for even e, and b * b^(e-1) for odd e. The recursion should make O(log e) multiplications, not O(e).

Examples

Example 1:

Input:  b = 2, e = 10
Output: 1024

2^10 = 1024, reached in about four squarings rather than ten multiplications.

Example 2:

Input:  b = 5, e = 0
Output: 1

Any base to the zero power is 1 — the base case of the recursion.

Example 3:

Input:  b = 3, e = 3
Output: 27

3^3 = 27.

Constraints

• -100 <= b <= 100
• 0 <= e <= 30
• The result fits in a 64-bit signed integer.

Problem 3: Reverse a String

Description

Return the reverse of a string using recursion. The empty string is its own reverse (base case); otherwise the reverse is the reverse of everything after the first character, followed by the first character. Do not use a loop or a library reverse helper.

Examples

Example 1:

Input:  s = "recursion"
Output: "noisrucer"

Example 2:

Input:  s = ""
Output: ""

The empty string is the base case.

Example 3:

Input:  s = "a"
Output: "a"

A single character reversed is itself.

Constraints

• 0 <= s.length <= 10,000
• s consists of printable ASCII characters.

Problem 4: Recursive Binary Search

Description

Given an array sorted in ascending order and a target, return the index of target, or -1 if it is absent. Implement the search recursively as divide and conquer: compare against the middle element and recurse into the half that can still contain the target. Run in O(log n).

Examples

Example 1:

Input:  a = [-3, 0, 4, 7, 11, 18], target = 7
Output: 3

The middle splits the array; 7 lies in the right half and is found at index 3.

Example 2:

Input:  a = [1, 2, 3, 4, 5], target = 6
Output: -1

6 is larger than every element, so the search exhausts and returns -1.

Example 3:

Input:  a = [42], target = 42
Output: 0

Constraints

• 0 <= a.length <= 100,000
• a is sorted in strictly ascending order.
• -10^9 <= a[i], target <= 10^9

Problem 5: Greatest Common Divisor

Description

Compute the greatest common divisor of two non-negative integers a and b using the recursive Euclidean algorithm: gcd(a, b) = gcd(b, a % b), with gcd(a, 0) = a as the base case. By convention gcd(0, 0) = 0.

Examples

Example 1:

Input:  a = 48, b = 18
Output: 6

gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) = 6.

Example 2:

Input:  a = 17, b = 5
Output: 1

17 and 5 are coprime.

Example 3:

Input:  a = 0, b = 9
Output: 9

Constraints

• 0 <= a, b <= 2,000,000,000

Problem 6: Power of Two

Description

Decide whether a positive integer n is a power of two. Use a recursive halving check: n is a power of two if it is 1 (base case), or if it is even and n / 2 is a power of two. Any odd number greater than one is not.

Examples

Example 1:

Input:  n = 16
Output: true

16 -> 8 -> 4 -> 2 -> 1, halving cleanly every step.

Example 2:

Input:  n = 12
Output: false

12 -> 6 -> 3, which is odd and greater than one, so 12 is not a power of two.

Example 3:

Input:  n = 1
Output: true

2^0 = 1 is the base case.

Constraints

• 1 <= n <= 2,000,000,000

Applied Problems

Problem 7: Pow(x, n)

LeetCode: 50. Pow(x, n)

Description

Implement pow(x, n), which raises the floating-point base x to the integer power n. Use fast exponentiation (exponentiation by squaring) so the work is O(log |n|). Handle negative exponents by raising the reciprocal: x^(-n) = (1/x)^n.

Examples

Example 1:

Input:  x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input:  x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input:  x = 2.00000, n = -2
Output: 0.25000

2^(-2) = 1 / 2^2 = 1/4 = 0.25.

Constraints

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31 - 1
• Either x is non-zero or n > 0.
• The result is within 10^-5 of the true value.

Problem 8: Fibonacci Number

LeetCode: 509. Fibonacci Number

Description

The Fibonacci sequence is defined by F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n >= 2. Given n, return F(n). Express the recurrence directly; to stay fast you may memoize or fold the two recursive calls into a single linear pass.

Examples

Example 1:

Input:  n = 2
Output: 1

F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input:  n = 4
Output: 3

F(4) = F(3) + F(2) = 2 + 1 = 3.

Example 3:

Input:  n = 10
Output: 55

Constraints

• 0 <= n <= 30

Problem 9: Merge Two Sorted Lists

LeetCode: 21. Merge Two Sorted Lists

Description

Given two arrays each sorted in ascending order, merge them into a single sorted array. Solve it recursively in the spirit of the merge step of merge sort: compare the two front elements, emit the smaller, and recurse on the remainder. Do not call a library sort.

Examples

Example 1:

Input:  a = [1, 2, 4], b = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]

Example 2:

Input:  a = [], b = []
Output: []

Example 3:

Input:  a = [], b = [0]
Output: [0]

Constraints

• 0 <= a.length, b.length <= 50,000
• Both arrays are sorted in non-decreasing order.
• -10^9 <= a[i], b[i] <= 10^9

Problem 10: Find Peak Element

LeetCode: 162. Find Peak Element

Description

A peak element is strictly greater than its neighbors; out-of-bounds neighbors count as negative infinity. Given an array where no two adjacent elements are equal, return the index of any peak. Use a divide-and-conquer binary search: compare the middle to its right neighbor and recurse toward the higher side, which must contain a peak. Run in O(log n).

Examples

Example 1:

Input:  a = [1, 2, 3, 1]
Output: 2

a[2] = 3 is greater than both neighbors, so index 2 is a peak.

Example 2:

Input:  a = [1, 2, 1, 3, 5, 6, 4]
Output: 5

Index 5 (value 6) is a peak; index 1 (value 2) is another valid answer.

Example 3:

Input:  a = [1]
Output: 0

A single element is a peak with both neighbors treated as negative infinity.

Constraints

• 1 <= a.length <= 1,000
• -2^31 <= a[i] <= 2^31 - 1
• a[i] != a[i + 1] for all valid i.

Problem 11: Search in Rotated Sorted Array

LeetCode: 33. Search in Rotated Sorted Array

Description

An ascending sorted array of distinct values has been rotated at an unknown pivot (for example [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]). Given the rotated array and a target, return its index, or -1 if absent. Use a modified binary search: at each step one half is sorted — decide whether the target lies in it and recurse accordingly. Run in O(log n).

Examples

Example 1:

Input:  a = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Example 2:

Input:  a = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

Example 3:

Input:  a = [1], target = 0
Output: -1

Constraints

• 1 <= a.length <= 5,000
• All values in a are distinct.
• a is a rotation of an ascending array.
• -10^4 <= a[i], target <= 10^4

Problem 12: Subsets

LeetCode: 78. Subsets

Description

Given an array of distinct integers, return all possible subsets (the power set). The solution set must not contain duplicate subsets; order does not matter. Build the subsets by recursion/backtracking: at each index, choose to include or exclude the element and recurse on the rest.

Examples

Example 1:

Input:  nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

All 2^3 = 8 subsets, in any order.

Example 2:

Input:  nums = [0]
Output: [[], [0]]

Example 3:

Input:  nums = []
Output: [[]]

The only subset of the empty set is the empty set itself.

Constraints

• 0 <= nums.length <= 10
• All elements of nums are distinct.
• -10 <= nums[i] <= 10

Problem 13: Permutations

LeetCode: 46. Permutations

Description

Given an array of distinct integers, return all possible orderings (permutations). Use backtracking: pick an unused element for the current position, recurse to fill the remaining positions, then undo the choice and try the next candidate. Any order of the permutations is accepted.

Examples

Example 1:

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

All 3! = 6 orderings, in any order.

Example 2:

Input:  nums = [0, 1]
Output: [[0, 1], [1, 0]]

Example 3:

Input:  nums = [1]
Output: [[1]]

Constraints

• 1 <= nums.length <= 6
• All elements of nums are distinct.
• -10 <= nums[i] <= 10

Problem 14: Sort an Array (Merge Sort)

LeetCode: 912. Sort an Array

Description

Given an array of integers, return it sorted in ascending order in O(n log n) time without using any built-in sort. Implement merge sort as divide and conquer: split the array in half, recursively sort each half, then merge the two sorted halves into one.

Examples

Example 1:

Input:  nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]

Example 2:

Input:  nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]

Example 3:

Input:  nums = [42]
Output: [42]

Constraints

• 1 <= nums.length <= 50,000
• -50,000 <= nums[i] <= 50,000

Problem 15: Majority Element

LeetCode: 169. Majority Element

Description

Given an array of size n, return the majority element — the value that appears more than n / 2 times. You may assume one always exists. Solve it with divide and conquer: recursively find the majority of the left and right halves; if they agree that is the answer, otherwise count which candidate dominates the full range.

Examples

Example 1:

Input:  nums = [3, 2, 3]
Output: 3

3 appears twice in an array of length 3, which is more than 1.5.

Example 2:

Input:  nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2

2 appears four times out of seven.

Example 3:

Input:  nums = [7]
Output: 7

Constraints

• 1 <= nums.length <= 50,000
• A majority element is guaranteed to exist.
• -10^9 <= nums[i] <= 10^9

Problem 16: Different Ways to Add Parentheses

LeetCode: 241. Different Ways to Add Parentheses

Description

Given a string expression of numbers and the operators +, -, and *, return all possible results of computing it under every way of grouping the operands with parentheses. Solve it with divide and conquer: split at each operator, recursively evaluate the left and right sub-expressions, and combine every left result with every right result using that operator. Results may be returned in any order.

Examples

Example 1:

Input:  expression = "2-1-1"
Output: [0, 2]

(2-1)-1 = 0 and 2-(1-1) = 2.

Example 2:

Input:  expression = "2*3-4*5"
Output: [-34, -14, -10, -10, 10]

The five distinct parenthesizations evaluate to these values.

Example 3:

Input:  expression = "11"
Output: [11]

A bare number has exactly one value.

Constraints

• 1 <= expression.length <= 20
• expression contains only digits and the operators +, -, *.
• Every integer operand is in the range [0, 99].

Problem 17: Count Inversions

Description

Given an array, count the number of inversions: pairs (i, j) with i < j and a[i] > a[j]. A brute-force scan is O(n^2); instead piggyback on merge sort — while merging two sorted halves, every time you take an element from the right half before the left, it forms an inversion with all remaining left-half elements. Run in O(n log n).

Examples

Example 1:

Input:  a = [2, 4, 1, 3, 5]
Output: 3

The inversions are (2,1), (4,1), and (4,3).

Example 2:

Input:  a = [5, 4, 3, 2, 1]
Output: 10

A strictly descending array of length 5 has every one of its 10 pairs inverted.

Example 3:

Input:  a = [1, 2, 3]
Output: 0

An already-sorted array has no inversions.

Constraints

• 1 <= a.length <= 100,000
• -10^9 <= a[i] <= 10^9
• The count fits in a 64-bit signed integer.

Problem 18: Generate Parentheses

LeetCode: 22. Generate Parentheses

Description

Given n pairs of parentheses, generate all combinations of well-formed parentheses. Use backtracking: at each step you may add an opening bracket if any remain, or a closing bracket if it would not exceed the opens placed so far. Results may be returned in any order.

Examples

Example 1:

Input:  n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

The five valid arrangements of three pairs.

Example 2:

Input:  n = 1
Output: ["()"]

Example 3:

Input:  n = 2
Output: ["(())", "()()"]

Constraints

• 1 <= n <= 8

Problem 19: Combination Sum

LeetCode: 39. Combination Sum

Description

Given an array of distinct positive integers candidates and a target, return all unique combinations whose elements sum to target. The same number may be chosen unlimited times. Two combinations are the same regardless of order. Use backtracking: try each candidate, subtract it from the remaining target, and recurse — allowing the same index again to permit reuse. Any order is accepted.

Examples

Example 1:

Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

2 + 2 + 3 = 7 and 7 = 7.

Example 2:

Input:  candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Example 3:

Input:  candidates = [2], target = 1
Output: []

No multiple of 2 equals 1.

Constraints

• 1 <= candidates.length <= 30
• All elements of candidates are distinct.
• 1 <= candidates[i] <= 200
• 1 <= target <= 500

Problem 20: Median of Two Sorted Arrays

LeetCode: 4. Median of Two Sorted Arrays

Description

Given two arrays sorted in ascending order, return the median of their combined multiset. The overall run time must be O(log(min(m, n))). Binary-search a partition of the shorter array so that all elements on the left of the combined split are no greater than those on the right; the median falls at the boundary.

Examples

Example 1:

Input:  a = [1, 3], b = [2]
Output: 2.00000

The merged array is [1, 2, 3], whose median is 2.

Example 2:

Input:  a = [1, 2], b = [3, 4]
Output: 2.50000

The merged array is [1, 2, 3, 4]; the median is (2 + 3) / 2 = 2.5.

Example 3:

Input:  a = [], b = [1]
Output: 1.00000

Constraints

• 0 <= m, n <= 1,000 and 1 <= m + n
• Both arrays are sorted in non-decreasing order.
• -10^6 <= a[i], b[i] <= 10^6

Problem 21: Relay Station Spacing

Description

Given the planar coordinates of relay stations, return the smallest Euclidean distance between any two distinct stations. Use the closest-pair-of-points divide-and-conquer algorithm: sort by x, split into left and right halves, recurse on each, then check the narrow strip around the dividing line for any closer cross-pair. Run in O(n log n). Reuses the module’s Point record.

Examples

Example 1:

Input:  stations = [(0,0), (5,5), (1,1), (9,2)]
Output: 1.41421356

The closest pair is (0,0) and (1,1), at distance sqrt(2).

Example 2:

Input:  stations = [(0,0), (3,4)]
Output: 5.0

With two points the answer is simply the distance between them.

Example 3:

Input:  stations = [(2,2), (2,5), (2,2.5), (8,8)]
Output: 0.5

The pair (2,2) and (2,2.5) is the closest, at distance 0.5.

Constraints

• 2 <= stations.length <= 100,000
• -10^9 <= x, y <= 10^9
• All stations are distinct points.

Problem 22: Skyline Merge

Description

Each building is given as [left, right, height]. The skyline is the silhouette formed by all the buildings against the horizon, described as a list of “key points” [x, height] sorted by x, where each point marks a change in the visible roofline; the last point has height 0. Compute it with divide and conquer: split the buildings into two groups, recursively compute each group’s skyline, then merge the two skylines by sweeping their key points and tracking the running max height of each side. Run in O(n log n).

Examples

Example 1:

Input:  buildings = [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]
Output: [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]]

The merged silhouette rises to 15, steps down past each building, and returns to 0.

Example 2:

Input:  buildings = [[0,2,3], [2,5,3]]
Output: [[0,3], [5,0]]

Two equal-height adjacent buildings form a single flat roofline.

Example 3:

Input:  buildings = [[1,5,11]]
Output: [[1,11], [5,0]]

A lone building gives its left edge and its right drop to ground.

Constraints

• 1 <= buildings.length <= 10,000
• 0 <= left < right <= 2^31 - 1
• 1 <= height <= 2^31 - 1

Linear Search

What It Is & When to Use It

What problem does linear search solve, and in what situations is it the only option you have?

The Sequential Scan Mental Model

How do you picture walking a collection element by element, and what single piece of state do you carry as you go?

The Loop Invariant

What is guaranteed about every element you’ve already passed at the moment you inspect index \( i \)?

Why Order Doesn’t Matter

Why does this work on unsorted data when binary search cannot, and what freedom does that give you?

The Comparison at the Core

What does it mean to “match” an element — reference equality, value equality, or a predicate — and how does that choice change the code?

Iterative Coding

What does the basic loop look like, and where do you place the equality check and the early return?

Returning First vs Last Match

If duplicates exist, how do you control which occurrence you report, and what loop direction does each need?

Sentinel Optimization

How can placing the target at the end as a sentinel remove the bounds check from the inner loop?

Why the Sentinel Helps

What hidden per-iteration cost does the bounds check carry, and what must you restore afterward?

The Found vs Not-Found Contract

What should you return when the target is absent — an index, a boolean, or \( -1 \) — and why does the caller care?

Time Complexity

What is the cost model — how many comparisons does linear search perform as a function of \( n \)?

Best Case

What input makes it finish in \( O(1) \), and where must the target sit for that to happen?

Average Case

If the target is equally likely at any position, where does a random hit land on average, and why is that still \( \Theta(n) \)?

Worst Case

Which two situations both force a full \( n \)-element scan, and why?

Constant Factors

Why can a plain linear scan beat a fancier algorithm on small \( n \) despite the same or worse big-O?

Space Complexity

Why is linear search \( O(1) \) auxiliary space, and what would you have to add to change that?

Trade-offs vs Binary Search & Hashing

When is an \( O(n) \) scan actually the right call over an \( O(\log n) \) or \( O(1) \) lookup, once you count setup cost?

Common Bugs & Edge Cases

What goes wrong with empty inputs, off-by-one loop bounds, or comparing objects with == instead of .equals?

Real-World Uses

Where do small lists, linked structures, or one-shot scans make linear search the practical choice?

Implementation Walkthrough

Break the algorithm into the parts you must get right before you write a line.

Setup

What inputs and return-type decision do you fix before the loop starts?

The Scan Loop

How do you structure the single pass, and what exactly is compared each iteration?

Termination & Return

What are the two ways the loop can end, and what value does each path return?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Binary Search

What It Is & When to Use It

What precondition must the data satisfy, and what makes binary search worth the setup cost?

How Halving the Search Space Works

How does each comparison let you discard half the remaining range?

The Mental Model of a Shrinking Window

How do you picture [lo, hi] closing in, and what does it mean when it becomes empty?

The Three-Way Decision

At each midpoint, what are the three outcomes (less, equal, greater) and how does each reshape the window?

Iterative Coding with lo/hi

How do you maintain the lo and hi bounds and update them after each midpoint check?

Computing the Midpoint Safely

Why is lo + (hi - lo) / 2 preferred over (lo + hi) / 2?

Recursive Coding

How do you express the same logic as a recursive call on a shrinking subrange?

The Loop Invariant & Termination

What stays true about lo and hi every iteration, and how do you guarantee the loop ends?

Choosing < vs <= and the Interval Convention

Which loop condition matches a closed [lo, hi] versus a half-open [lo, hi) range, and why must they agree?

Why the Window Must Always Shrink

What update mistake leaves lo and hi unchanged, and why does that cause an infinite loop?

Variants: Lower Bound & Upper Bound

How do you find the first element \( \ge \) the target, or the insertion point, instead of just any match?

Leftmost vs Rightmost Match

With duplicates present, how do you bias the search to return the first or last equal element?

Time Complexity

How many times can you halve \( n \) before the window is empty, and why does that count the comparisons?

Best Case

What lets binary search return in \( O(1) \), and how likely is that?

Worst & Average Case

Why are both worst and average \( \Theta(\log n) \), and how few steps is that for a million elements?

Constant Factors vs Linear Search

Why might linear search still win for very small arrays despite \( O(\log n) \)?

Space Complexity

Why is the iterative version \( O(1) \) while the recursive version costs \( O(\log n) \) call-stack space?

Trade-offs vs Linear Search & Hashing

When does the cost of keeping data sorted outweigh the lookup speedup, and when does hashing beat both?

Common Bugs & Edge Cases

Where do infinite loops, off-by-one bounds, and overflow creep in, and how do empty or single-element arrays behave?

Real-World Uses

Where do you see binary search beyond arrays — answer-space search, rotated arrays, library APIs?

Implementation Walkthrough

Break the algorithm into the parts you must get right before you write a line.

Setup

What two bounds do you initialize, and to what values for your chosen interval convention?

The Search Loop

What is the loop condition, how do you compute the midpoint, and how does each comparison branch move a bound?

Termination & Return

How does the loop signal “found” versus “absent,” and what does each case return?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Comparison Lower Bound

What a Comparison Sort Is

Which sorts only ever learn about elements by comparing pairs, and which ones don’t?

The Comparison-Only Rule

Why does “no peeking at the key’s value, only </> results” define this whole class of algorithms?

The Core Claim

What is the headline result — why can no comparison sort beat \( n \log n \) in the worst case?

The Intuition Behind the Bound

Conceptually, why does the number of possible orderings force a minimum amount of work? (idea only, no formal proof)

Counting the Possible Orderings

How many distinct arrangements of \( n \) items exist, and why must a correct sort be able to distinguish all of them?

Information Gained Per Comparison

Why does each yes/no comparison reveal at most one bit, and how does that cap progress per step?

Putting the Two Together

If you must distinguish a huge number of orderings and each step gives one bit, why does the step count grow like \( n \log n \)?

What “Lower Bound” Actually Means

How is a lower bound a statement about every possible algorithm, not the running time of any single one?

Worst-Case vs Average-Case Bounds

Why does the bound hold even for the average case, not just the worst?

Which Sorts Hit the Bound

Why are merge sort and heapsort considered asymptotically optimal comparison sorts?

How Non-Comparison Sorts Escape It

Why do counting, radix, and bucket sort sidestep the \( n \log n \) wall entirely?

What Assumptions They Trade In

What must you know about the keys for a non-comparison sort to be legal, and what do you give up?

Time-Complexity Implications

How does this bound set the floor for the time complexity of any general-purpose comparison sort?

Why \( O(n) \) Comparison Sorting Is Impossible

What would an \( O(n) \) comparison sort have to do that the counting argument forbids?

Where the Best Case Slips Under

Why can a comparison sort still finish in \( O(n) \) on a lucky input without violating the worst-case floor?

Space-Complexity Note

Why does the lower bound concern comparisons and time, and say nothing on its own about memory use?

Why This Matters in Practice

How does knowing the bound stop you from chasing an impossible faster general-purpose comparison sort?

Implementation Walkthrough

Reason about a demonstration rather than a sort.

What There Is to Implement

Why is there no algorithm to code here — what could you instead build to illustrate the idea (e.g. counting comparisons a sort makes)?

Setting Up the Demonstration

What would you measure across input sizes to see the comparison count rise like \( n \log n \)?

Interpreting the Result

How would the measured curve support, but not prove, the lower bound?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Bubble Sort

What It Is & When to Use It

What is the one idea behind bubble sort, and is it ever the right tool outside teaching?

How Bubbling Works

How does each pass of adjacent swaps push the largest remaining element to its final slot?

Watching One Element Bubble

If you track a single large value, why does it rise to the top in one pass while small values drift only one step?

The Pass Invariant

What is guaranteed about the last \( k \) elements after \( k \) completed passes, and why does that prove correctness?

Iterative Coding

How do the outer pass loop and inner adjacent-comparison loop fit together?

The Adjacent Compare-and-Swap

What exactly do you compare, and under what condition do you swap?

The Early-Exit Flag

How can a “no swaps this pass” check turn the best case into \( O(n) \)?

Shrinking the Inner Bound Each Pass

Why can you stop the inner loop one element earlier after every completed pass?

Stability & In-Place

Why does swapping only on strict inequality preserve the order of equal keys, and why is no extra array needed?

Time Complexity

How do you count total comparisons and swaps across all passes, and how do they relate to the number of inversions?

Best Case

Which input lets the early-exit flag finish in a single \( O(n) \) pass?

Average Case

Why does a random permutation cost \( \Theta(n^2) \), and roughly how many swaps is that?

Worst Case

Which input (think reverse-sorted) forces the maximum swaps, and why does each element travel the full distance?

Space Complexity

Why is bubble sort \( O(1) \) auxiliary space with no recursion, and how does that compare to merge sort?

Trade-offs vs Insertion & Selection Sort

Among the quadratic sorts, why is bubble sort usually the slowest in practice despite matching big-O?

Common Bugs & Edge Cases

Where do off-by-one inner bounds, a forgotten swap-flag reset, or single-element arrays trip you up?

Real-World Uses

Where does bubble sort genuinely appear — tiny inputs, nearly-sorted data, or pure pedagogy?

Implementation Walkthrough

Break the algorithm into the parts you must get right before you write a line.

Setup

What outer-loop bound and what swap-tracking flag do you initialize?

The Nested Passes

How does the inner loop walk adjacent pairs, and how does the shrinking bound feed off the outer loop counter?

Early Termination & Return

How does the flag let you break early, and why does the array need no explicit return?

Implementation

// implement from scratch here

Summary

Recap the whole topic in a few lines — the core idea, the key complexities and trade-offs, and when to reach for it. The cheat-sheet you’d skim before an exam or interview.

My Notes

Fill this in as you learn

Selection Sort

What It Is & When to Use It

What is the find-the-minimum idea, and what unusual property makes it occasionally useful?

How Find-Min, Swap-to-Front Works

How does each iteration scan the unsorted suffix for its minimum and place it at the front?

Why Each Placement Is Final

Once you place the smallest remaining element, why will you never have to move it again?

The Sorted-Prefix Invariant

Why is the prefix both sorted and final the moment an element is placed there, and how does that prove correctness?

Iterative Coding

How do the outer placement loop and the inner min-tracking loop interact, and what index do you track?

Tracking the Min Index, Not the Value

Why hold onto the position of the smallest element rather than its value during the scan?

Minimal Writes: Exactly \( n-1 \) Swaps

Why does selection sort perform the fewest writes of the quadratic sorts, and when does write-cost matter?

Stability & In-Place

Why is the classic version unstable, and how can a shift-based variant restore stability?

A Tiny Unstable Example

What small input shows the long-distance swap reordering two equal keys?

Time Complexity

Why does the comparison count come out the same regardless of input order — count the inner-loop work across all passes.

Why There’s No Best Case

Why does even an already-sorted array still cost \( \Theta(n^2) \) comparisons?

Average & Worst Case

Why are average and worst case identical at \( \Theta(n^2) \), unlike most other sorts?

Comparisons vs Swaps

Why is the swap count only \( O(n) \) while comparisons stay \( \Theta(n^2) \), and when does that asymmetry matter?

Space Complexity

Why is selection sort \( O(1) \) auxiliary space with no recursion stack?

Trade-offs vs Bubble & Insertion Sort

When does the low swap count win out, and when do the other quadratic sorts beat it?

Common Bugs & Edge Cases

Where do you forget to reset the min index, swap with the wrong slot, or mishandle a single element?

Real-World Uses

Where do minimal writes (e.g. flash memory, costly swaps) actually justify selection sort?

Implementation Walkthrough

Break the algorithm into the parts you must get right before you write a line.

Setup

What does the outer loop range over, and what does index \( i \) mean each iteration?

The Min-Finding Inner Loop

How do you scan the suffix and remember where the minimum sits?

The Swap & Return

When do you perform the swap (and can you skip it), and why is no explicit return needed?