Top 15 LeetCode Problems for Complexity Analysis

You've done Two Sum. You know it's O(n). You can recite this in your sleep. And yet, the moment an interviewer asks "why can't you do better?" your brain goes completely blank.

That is the gap. Most engineers can label Big-O after the fact. Fewer can look at an unfamiliar algorithm and derive it from first principles. These 15 problems fix that. Each one isolates a specific lesson in time or space complexity and forces you to reason it through, not just recall it.

Work through them in order. The progression is deliberate.

Pattern Recognition Is Not the Same as Proof

Grinding random mediums builds pattern recognition. This list builds something different: the ability to look at any algorithm and prove its complexity to yourself and your interviewer. That skill is what separates candidates who say "it's O(n)" from candidates who can explain why it cannot be faster.

One is a label. The other is an argument.

Complexity growth curves showing O(1) through O(2^n)

Six complexity classes. Notice where O(2^n) goes off the chart at n=13. That recursion tree you're ignoring? That.

Fifteen Problems, One Mechanism Each

1. Two Sum (LeetCode 1): The Space-Time Swap

You have probably solved this problem so many times you could write it in your sleep, at a hackathon, during a fire drill. Doesn't matter. Most people still can't explain the mechanism.

The brute-force nested loop is O(n²). The hash map version is O(n) time and O(n) space. Nothing else changes.

A nested loop checks every pair: n*(n-1)/2 comparisons, O(n²). Adding a hash map turns each lookup from O(n) to O(1), collapsing the inner loop entirely. You bought time with space. Literally. You paid one extra array's worth of memory to avoid an entire loop.

The lesson is not "use a hash map." The question to internalize is: what structure would make this lookup O(1)? That question solves half of all medium problems.

2. Maximum Subarray (LeetCode 53): Correct Does Not Mean Efficient

Divide and conquer gives O(n log n). Kadane's algorithm gives O(n). Both produce the right answer. Neither is wrong. One is just dramatically faster.

At n = 10,000, D&C runs roughly 133,000 operations. Kadane's runs 10,000. The D&C recursion tree has log n levels each doing O(n) work across the split. Kadane's is a single pass with O(1) state.

The lesson: correctness and efficiency are independent. Know the complexity of your solution before you declare it done.

Kadane's also has a classic gotcha: starting the running sum at 0 instead of nums[0] gives a wrong answer on all-negative arrays. Edge cases matter for the analysis, not just the solution.

def max_subarray(nums):
    best = current = nums[0]   # not 0, all-negative arrays exist
    for num in nums[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

3. Climbing Stairs (LeetCode 70): The Recursion Tree Explosion

This is where things get existentially frightening. The naive recursive solution runs in O(2^n). Not O(n²). O(2^n). Double the input, square the problem. That is not a typo.

Memoization drops it to O(n) time and O(n) space. Two rolling variables drop it to O(1) space.

Draw the recursion tree for n=6. Every unique subproblem appears twice, then four times, then eight. The tree doubles at every level because the subproblems overlap. Memoization converts the tree to a DAG. You go from exponential nodes to n unique states times O(1) work per state.

The formula is: time = (number of unique states) x (work per state). This formula drives the complexity of every top-down DP problem you will ever encounter. See recursion time complexity for the full derivation.

Rolling variables then eliminate the memo table entirely. The dependency is only on the previous two values, so you keep two variables and move on.

4. Trapping Rain Water (LeetCode 42): Same Time, Different Space

Two approaches achieve O(n) time. One uses O(n) extra space. The other uses O(1). Both are O(n) time. An interviewer who asks "can you do better on space?" is not asking you to go faster. They are asking whether you understand what you built.

Learn this problem to understand that the same time complexity can hide very different space requirements.

The complexity insight is subtle. The two-pointer approach works because when left_max < right_max, the right side is guaranteed at least right_max. The left bar is the bottleneck. You never actually need the exact right max at that moment, so you don't have to store it.

When an interviewer asks "can you do it with constant space?" they are asking whether you understand the space analysis, not just the time.

5. Find All Anagrams in a String (LeetCode 438): Fixed Window = Free Slide

Naive approach: for each of n positions, compare a length-k substring to the target. That is O(n*k). Slow enough to fail on any real input.

Fixed sliding window rewrites this as O(n). The window size never changes, so each slide removes one character and adds one. Compare two 26-element frequency arrays in O(26) = O(1). One pass, n steps, O(1) per step.

The lesson: fixed-size windows reduce repeated work to incremental updates. Any constraint that fixes the window size makes a sliding approach O(n). Variable-size windows (expand/shrink) are also O(n), but for a completely different reason: each element enters and exits the window exactly once.

6. Merge Intervals (LeetCode 56): When Sorting Is the Floor

Sort first, then merge. Total: O(n log n). That O(n log n) is not laziness. It is a lower bound.

Can you do better? No. And this is worth understanding precisely.

Sorting buys the global ordering the problem needs. The O(n log n) floor is load-bearing, not lazy.

Without sorting, detecting whether interval A overlaps interval B requires inspecting all others first. That pushes you toward O(n²). Sorting is the cheapest way to get the global ordering you need, and any solution claiming to merge intervals in O(n) without sorting is either wrong or using non-comparison methods like counting sort on integer endpoints.

This is the comparison-sort information-theoretic argument at work: to determine the correct merge order among n intervals, you need at least log2(n!) comparisons. See comparison sort algorithm for the proof.

7. Coin Change (LeetCode 322): Exponential to Polynomial

The naive recursive solution tries every combination. For n denominations and target amount A, the recursion tree has O(n^A) nodes in the worst case. That is not a misprint. A=10,000 and n=3 gives 3^10,000. Your laptop will be a museum piece before that finishes.

Bottom-up DP fills a table of A+1 cells, each requiring O(n) coin comparisons. Total: O(n*A).

Apply the state formula: state space is A+1 values, work per state is O(n). Multiply them. That is the entire analysis. Internalize it here, and reading the complexity of any bottom-up DP becomes mechanical.

def coin_change(coins, amount):
    table = [float('inf')] * (amount + 1)
    table[0] = 0
    for target in range(1, amount + 1):
        for coin in coins:
            if coin <= target:
                table[target] = min(table[target], table[target - coin] + 1)
    return table[amount] if table[amount] != float('inf') else -1

State space: amount + 1. Work per state: len(coins). Total: O(amount * len(coins)).

8. Word Break (LeetCode 139): Recognizing Overlapping Subproblems

Backtracking tries all possible splits. At each position, either break or continue: up to 2^n choices for a string of length n. You can feel the exponential from across the room.

With memoization, you cache the result for each starting index. That gives n states. Each state checks all substrings starting there: O(n) substrings, each matched in O(n) time (or O(1) with a hash set). Total: O(n²).

The lesson is noticing when recursion recomputes the same subproblem. If wordBreak("code", wordDict) is called multiple times during the recursion, you have overlapping subproblems. Cache the answer. Complexity drops from exponential to polynomial.

This is the diagnostic test for dynamic programming: does the recursion revisit identical states? If yes, memoize.

9. Kth Largest Element (LeetCode 215): Three Algorithms, Three Profiles

One problem, three correct solutions, three completely different complexity profiles. Interviewers love this one because it forces you to choose and justify.

Sort and index: O(n log n) time, O(1) extra space with in-place sort. Min-heap of size k: O(n log k) time, O(k) space. Quickselect: O(n) expected, O(n²) worst case, O(1) space.

For small k, the heap beats full sort because log k is much smaller than log n. For k close to n, sort becomes competitive again. Quickselect gives the best expected time but with probabilistic, not worst-case, guarantees.

This is also where interviewers catch people. "O(n) expected" is not the same as "O(n) guaranteed." Quickselect's worst case is O(n²) on adversarial pivot selection. Know the difference before you commit. See quickselect vs sorting for the trade-off in full.

10. Sliding Window Maximum (LeetCode 239): Amortized O(1)

Naive: for each of n windows of size k, scan k elements. O(n*k). Simple, correct, totally impractical.

Monotonic deque: maintain a deque of indices with values decreasing front-to-back. Each element enters the deque once and exits once. Total: O(n), O(k) space.

The complexity argument is amortized. This is the one that confuses people most. No single step is expensive, but each element's total cost across its entire lifetime is O(1). Summed over n elements: O(n). The amortized O(1) per-step pattern reappears in dynamic arrays, LRU caches, and streaming algorithms. Understanding it here means you recognize it everywhere.

11. Longest Increasing Subsequence (LeetCode 300): Log Factor from Binary Search

The O(n²) DP is straightforward: for each index i, scan all j < i. Two nested loops, easy to see.

The O(n log n) version uses patience sorting. Maintain a tails array where tails[i] is the smallest tail of all increasing subsequences of length i+1. For each new element, binary search for its position in tails.

Each of n elements requires one binary search costing O(log n). Total: O(n log n). This is the canonical example of replacing a linear scan with binary search to shave one factor of n from a loop.

Any time you find yourself scanning a sorted structure for a position, ask whether binary search applies. The answer is usually yes. The factor of n you save is the entire point.

12. Unique Paths (LeetCode 62): Space Compression

Naive DP: O(mn) time, O(mn) space. Fill a 2D table. Simple, correct, uses more memory than it needs to.

Space-optimized: O(m*n) time, O(n) space. Use a single row, update left to right.

You only need the row above when computing the current row. Keep one array. Update in-place.

The lesson: space reduces to the look-back horizon. If a DP state depends only on the previous row, keep one row. If it depends only on the previous two Fibonacci values, keep two variables. Match your space allocation to your actual dependency structure, not your intuition about it.

This rolling-array technique applies uniformly to knapsack, LCS, edit distance, and all grid DP problems.

13. Course Schedule (LeetCode 207): O(V+E) Is Not Arbitrary

Cycle detection on a directed graph. BFS via Kahn's or DFS with three-color marking, both O(V+E).

Why V+E and not something else? Each vertex is processed once. Each edge is traversed once. Neither is visited twice. That is the entire argument.

O(V+E) is the floor for graph problems because reading the input is Theta(V+E). Any algorithm claiming to solve course scheduling faster than O(V+E) must skip some vertices or edges, which breaks correctness. The complexity is dictated by input size, not algorithmic choice.

This is the graph-traversal justification you need for any BFS or DFS problem: "We visit every vertex once and traverse every edge once, so O(V+E)." Say it out loud until it comes naturally. It will come up.

14. Median of Two Sorted Arrays (LeetCode 4): Binary Search on the Answer Space

Naive merge: O(m+n). Binary search on the partition: O(log(min(m,n))).

The trick, and it is a genuine trick, is that you are not binary searching an array of values. You are binary searching the space of valid partition points. Run binary search on the shorter array. Each iteration halves the remaining partitions.

Any time you can reduce a problem to finding a valid split point, binary search applies to the solution space itself, not just the data.

This pattern, binary search on the answer rather than on an array, is the technique behind capacity problems, minimum-maximum problems, and allocation problems. Once you see it here, you start seeing it everywhere.

15. Count of Smaller Numbers After Self (LeetCode 315): Merge Sort as a Counter

Brute force: for each element, count smaller elements to its right. O(n²). Correct. Slow.

Merge sort solution: O(n log n). During the merge step, when an element from the right subarray is placed before elements still in the left subarray, those left elements each get an increment. One merge operation, multiple counts updated simultaneously.

The lesson: merge sort's divide-and-conquer processes every cross-subarray pair exactly once in O(n log n) total. This makes it the correct tool for inversion counting, cross-comparisons, and any problem where one element's position affects another's count.

The complexity falls out of the algorithm structure, not from a lookup table. That is the whole point.

Five Complexity Analysis Patterns These 15 Problems Cover

Work through each problem asking: "how many operations does this algorithm perform, and why?" Not as a lookup. As a derivation.

The lessons cluster into five categories:

Space-time tradeoffs (Two Sum, Trapping Rain Water, Unique Paths): extra space buys time, but the tradeoff is always a choice
Recursion to DP (Climbing Stairs, Coin Change, Word Break): overlapping subproblems collapse exponential trees to polynomial tables
Log factors from binary search (Median of Arrays, LIS, Kth Largest heap): replacing a linear scan with binary search shaves one log n
Amortized O(1) (Sliding Window Maximum, deque operations): per-lifetime cost, not per-operation cost
Input-size floors (Merge Intervals, Course Schedule): sorting and graph traversal have floors dictated by information theory and input size

Practice explaining each one out loud. If you cannot articulate why the complexity is what it is in one coherent sentence, you do not have it yet. You have memorized a label.

SpaceComplexity runs voice-based mock interviews that follow up with exactly these questions: "Why can't you do this faster?" and "What happens to the complexity if the input doubles?" You get real-time feedback on whether your reasoning holds, not just whether your code runs.