01 — Complexity & Problem Triage

This file answers two questions: "how do I measure how fast my code is?" and "how do I use that measurement to pick an approach before writing anything?"

If you already know Big-O, skim to Constraint → target complexity. Otherwise start here — everything else in this cheatsheet assumes it.

What Big-O actually means

Suppose you want to know how fast a piece of code is. You could time it — but the answer would depend on your laptop, the JVM version, and what else was running. That number tells you nothing portable.

So instead of measuring time, we count operations, and we ask a different question:

When the input gets bigger, how does the amount of work grow?

That growth rate is the same on every machine. It is what Big-O captures.

Building it up from an example

int sum = 0;                          // 1 operation
for (int i = 0; i < n; i++) {         // the body runs n times
    sum += nums[i];                   // 1 operation per run
}
return sum;                           // 1 operation

Total operations ≈ 1 + n + 1 = n + 2.

Now imagine n = 1,000,000. The + 2 is completely irrelevant — it's 2 out of a million. So we throw it away and say this is O(n), read aloud as "oh of n" or "linear time".

Two rules produced that answer, and they are the only two rules you need:

Rule 1 — drop the constants. O(2n) and O(n) and O(100n) are all written O(n). Doubling the work doesn't change how it grows; a graph of 2n is still a straight line. We care about the shape, not the slope.

Rule 2 — keep only the biggest term. O(n² + n) is written O(n²). When n = 1000, n² is a million and n is a thousand — the smaller term contributes 0.1% and is noise.

Reading complexity off code

Nested loops multiply:

for (int i = 0; i < n; i++) {         // runs n times
    for (int j = 0; j < n; j++) {     // ...and for EACH of those, runs n times
        doSomething();                // so the body runs n × n times
    }
}
// O(n²) — "quadratic"

Sequential loops add (and then Rule 2 collapses them):

for (int i = 0; i < n; i++) { ... }   // O(n)
for (int j = 0; j < n; j++) { ... }   // O(n)
// O(n) + O(n) = O(2n) = O(n)         <- Rule 1

Halving the input each step gives O(log n):

while (n > 1) {
    n = n / 2;                        // 1024 -> 512 -> 256 -> ... -> 1
}
// O(log n) — "logarithmic"

Why that's log n: you're asking "how many times can I halve n before reaching 1?" For n = 1024 the answer is 10, because 2^10 = 1024. That question is the definition of a base-2 logarithm. In Big-O the base is always 2 unless stated, and it doesn't matter anyway — changing base is a constant factor, which Rule 1 discards.

The growth rates, and what they feel like

Sorted from fastest to slowest. The right-hand column is the practical takeaway.

The jump from O(n log n) to O(n²) is where most interview problems live. Turning a nested loop into a single pass with a hash map is the most common optimization in the entire NeetCode 150 — and it is exactly this jump.

Worst, average, and best case

Big-O usually describes the worst case — the input that makes your code work hardest.

for (int i = 0; i < n; i++) {
    if (nums[i] == target) return i;
}

• Best case: the target is at index 0 → 1 operation → O(1).
• Worst case: the target is last, or absent → n operations → O(n).

We say this is O(n) because we care about the guarantee. Saying "it's O(1) if you're lucky" is not a useful promise.

Where average case matters: HashMap.get is O(1) average but O(n) worst case (if every key collides into one bucket). In interviews you say "O(1) average" — the worst case essentially never happens with good hash functions, but knowing it exists is what separates understanding from recitation.

Space complexity

Same idea, counting memory instead of operations.

int sum = 0;                          // one variable, regardless of n
for (int x : nums) sum += x;
// O(1) space — "constant extra space"

int[] copy = new int[n];              // n slots
// O(n) space

Three things people forget to count:

1. The recursion stack is memory. Each pending recursive call holds a frame. Recursion n levels deep costs O(n) space even with no arrays involved.
2. The output usually doesn't count. If the problem requires returning a list of n items, that O(n) is unavoidable and conventionally excluded. We measure auxiliary (extra) space. Make the distinction out loud — it signals precision.
3. A fixed-size array is O(1). int[26] for the lowercase alphabet doesn't grow with n, so it's constant space no matter how long the string is.

Constraint → target complexity

Here is where Big-O stops being academic and starts saving you.

Every problem states constraints like 1 <= nums.length <= 10^5. That number tells you which complexity you're allowed — and therefore narrows your approach to two or three candidates before you write a line.

The reasoning: a judge or interviewer roughly expects about 10^8 simple operations per second. So if n = 10^5, an O(n²) solution needs 10^10 operations — around 100 seconds. Too slow. But O(n log n) needs about 1.7 × 10^6 — instant.

How to actually use this

Read the constraint before proposing an approach, then say the target out loud:

"n is up to 10⁵, so I need O(n log n) or better. That rules out checking every pair. Sorting is affordable, and so is one pass with a hash map — let me think about which fits."

That single sentence does more for an interview than a page of code. It shows you're reasoning from the problem rather than pattern-matching.

Inverting the rule is the real trick. A constraint of n ≤ 20 is not a small input — it is the interviewer telling you that exponential is expected, so stop hunting for a clever polynomial algorithm and write the backtracking.

Read the value range too, not just the length

1 <= nums[i] <= 10^9 with n <= 10^4 is a strong hint. n is small but the values are huge — which suggests you binary search over the range of possible answers, not over the array. That is exactly Koko Eating Bananas (10 — Binary Search).

Small alphabets are a hint

"consists of lowercase English letters" means there are only 26 possible characters, so an int[26] replaces a HashMap. Comparing two of those arrays is 26 steps — a constant — so a comparison that looked like O(k) collapses to O(1).

Cost table — Java structures

You need these to compute your own complexity, and interviewers ask "why is that O(1)?" All average case unless noted.

Why HashMap.get is O(1) — the one-sentence version interviewers want: the key is converted to a number (its hash), that number is used to jump directly to a bucket, and the bucket holds very few entries. No searching, just arithmetic and a jump.

Why TreeMap is O(log n) — it's a balanced binary search tree. Each comparison discards half the remaining keys, so you reach any key in about log n steps. You pay that log n to get sorted order and neighbour queries, which HashMap cannot provide at any price.

Two traps that appear in real interviews:

• PriorityQueue.contains and remove(Object) are O(n), not O(log n). The heap is only organized around its root; finding an arbitrary element means scanning. If your design needs "remove any element from the heap", you need lazy deletion or a different structure.
• Iterating a PriorityQueue does not give sorted order. Only repeated poll() does. Printing one for debugging shows the internal heap array, which looks scrambled.

Other costs worth memorizing:

• Arrays.sort(int[]) — O(n log n) average, O(log n) space. (Quicksort-based; adversarial inputs can hit O(n²).)
• Arrays.sort(Object[]) / Collections.sort — O(n log n) guaranteed, O(n) space. (TimSort — a merge sort, which never degrades.)
• String.substring(i, j) — O(j - i), because it copies. Building substrings inside a loop is a hidden O(n²).
• s += c in a loop — O(n²). Strings are immutable, so each += builds a whole new string. Always use StringBuilder.
• new PriorityQueue<>(collection) — O(n) to build, cheaper than n separate inserts at O(n log n).

Amortized analysis — why some nested loops are secretly linear

"Amortized" means averaged over a whole sequence of operations, rather than measured on the single worst one. Three claims recur across the 150, and interviewers ask you to defend all three.

1. ArrayList.add is O(1) amortized

An ArrayList wraps an array. When it fills up, it allocates a bigger one (double the size) and copies everything over — that single add costs O(n).

But doubling means resizes are rare and get rarer. Growing to size n copies 1 + 2 + 4 + 8 + ... + n elements total, which sums to less than 2n. Spread across n adds, that's under 2 copies per add — a constant.

Say it as: "Any individual add can be O(n), but n adds cost O(n) total, so it's O(1) amortized."

2. The monotonic stack pass is O(n), not O(n²)

This one looks wrong at first glance:

for (int i = 0; i < n; i++) {            // n iterations
    while (!stack.isEmpty() && ...) {    // a nested loop?!
        stack.pop();
    }
    stack.push(i);
}

A nested loop usually means O(n²). Here it doesn't, and the reason is an accounting argument:

• Each index is pushed exactly once — that's n pushes total.
• Each index can be popped at most once, because once popped it's gone.
• So across the entire outer loop, the inner while body executes at most n times in total.

Total work: n pushes + at most n pops = O(n).

The key shift in thinking: don't bound the inner loop per iteration — bound it across the whole run. Some single iterations pop 50 items, but then 50 later iterations pop nothing. It averages out.

3. The sliding window is O(n)

Same structure, same argument. left and right each only ever move forward, and neither can exceed n. So no matter how the inner shrink loop is written, the two pointers take at most 2n steps combined.

The unifying idea behind all three is aggregate accounting: bound the total work over the whole run, not the worst case of one step.

Triage checklist — run this on every problem

Spend 60–90 seconds here before proposing anything. This is the process, in order.

1. Restate the problem in one sentence, in your own words. If you can't, you've misread it. This catches misunderstandings while they're still free.

2. Read the constraints and write the target complexity down. Before proposing an approach. n ≤ 10^5 → "I need O(n log n) or better."

3. Ask about the input's guarantees. Sorted? All distinct? Non-negative? Bounded alphabet? Can it be empty? Each answer eliminates candidate approaches. "Is it sorted?" is the highest-value question in the whole list — a yes unlocks two pointers and binary search.

4. Ask what to return for degenerate input. Empty array, one element, no valid answer. Settle this before coding, not mid-implementation.

5. State the brute force out loud, with its complexity. This is free credit. It proves you understand the problem, and it gives you something concrete to optimize. "The obvious approach is to check every pair, which is O(n²). Let me see if I can do better."

6. Find the redundancy in the brute force. This is the actual optimization step. Every improvement in the 150 is one of four moves:

Ask: "what work am I doing twice?" The answer points at one of these four rows.

7. Only now propose the optimal approach — and state its complexity before writing code.

How to state complexity well

Weak: "It's O(n)."

Strong: "Time is O(n) — each element is pushed and popped at most once, so the inner loop is amortized constant. Space is O(n) for the stack, worst case being a strictly increasing input where nothing pops until the end."

The pattern is claim → mechanism → worst case:

• Claim — the notation.
• Mechanism — why, in one clause. This is the part that proves understanding.
• Worst case — which input triggers it. This proves you thought about it rather than guessed.

Use this every time. It takes ten seconds and it is consistently the difference between "knows the answer" and "understands the answer."