30 Hard LeetCode Problems That Are Actually Worth Your Time

Most hard problems are mediums with the hint removed. Solve them, recognize the trick, done. Nothing transfers.

A smaller subset is different. The hard part IS the insight: a technique that doesn't exist at the medium tier, a modeling leap that unlocks entire problem families, a complexity argument you'll need to articulate out loud. This list is that subset. 30 hard problems chosen for what they teach, not because they appeared in someone's interview report.

Do 50+ mediums before you open this list. Hard problems are binary at interview time: you either saw the insight before, or you stare at the screen for 40 minutes and write brute force. They only pay off after you've built enough medium-tier vocabulary that the hard parts are actually the hard parts. That vocabulary lives in the medium tier.

Problems are ordered within each section by what to do first. Earlier problems build vocabulary for later ones.

Sliding Window: The Two-Pointer Dance

1. Minimum Window Substring (LC 76) The canonical variable-size sliding window template. Expand right when you need more, contract left when you're satisfied. Every other hard sliding window problem is a variation on this mechanic. Solve this until the two-pointer dance is automatic.

2. Sliding Window Maximum (LC 239) Monotonic deque: the front is always the current maximum. Evict elements that fall out the window from the front; evict elements smaller than the incoming element from the back. The same O(n) amortized logic underpins every sliding window optimization.

3. Subarrays with K Different Integers (LC 992) The at-most(K) minus at-most(K-1) trick. Exactly K is hard to count directly; at-most K is easy with a sliding window. This subtraction pattern unlocks a class of hard counting problems that look intractable until you see the decomposition.

Two Heaps Walk Into an Interview

4. Find Median from Data Stream (LC 295) Two heaps with a size invariant: the max-heap holds the lower half, the min-heap holds the upper half. Median is O(1). This appears verbatim at Meta and Amazon. The balancing logic carries directly to Sliding Window Median (LC 480), so learn it once and it pays twice.

5. The Skyline Problem (LC 218) Event sweep plus a max-heap with lazy deletion. Split buildings into start and end events, process sorted, track current maximum height. The tie-breaking in event ordering is the critical detail. This exact pattern shows up in calendar problems, room assignment, and bandwidth allocation.

6. Maximum Frequency Stack (LC 895) A frequency map plus a stack-per-frequency level gives O(1) push and O(1) pop. Track which elements exist at each frequency tier, not just each element's frequency. Design problems requiring O(1) on a non-obvious operation are increasingly common at the hard tier.

Binary Search the Answer Space

7. Median of Two Sorted Arrays (LC 4) Partition both arrays so everything left of both partitions is less than everything on the right. You're binary searching on the partition point, not on values. This is the hardest pure binary search on the site. The correctness argument takes patience. Work through it anyway, because it exercises exactly the reasoning you need for the next problem.

8. Split Array Largest Sum (LC 410) Binary search on the answer: the answer space is monotone, so feasibility becomes a greedy scan. Can you split into k pieces where no piece exceeds X? Linear check. This pattern reappears in Koko Eating Bananas, Ship Within D Days, Minimum Difficulty of a Job Schedule, and dozens more.

9. Swim in Rising Water (LC 778) The wait time is the maximum edge weight on the minimum bottleneck path, which is Dijkstra with a different priority key. Alternatively, binary search on the answer with BFS as the feasibility check. Two valid framings, same answer. Picking between them under time pressure is the actual skill.

DP: The Stuff Mediums Refused to Teach You

The hard tier tests techniques that simply don't appear below it: interval DP, state machine DP, meet-in-the-middle, and the cases where the naive DP direction is wrong in a way that isn't obvious until you're already stuck.

10. Burst Balloons (LC 312) Interval DP only works if you think about the last balloon burst, not the first. "First burst" creates tangled subproblems because you've removed a balloon and can't reference the original neighbors. "Last burst" keeps the surrounding boundaries fixed as constants. The first time you see this inversion it feels like cheating. It isn't. It's a principled technique, and it's the same insight needed for Matrix Chain Multiplication and Strange Printer.

11. Regular Expression Matching (LC 10) * means zero or more of the preceding character, forcing a branch at each * in the pattern. Either skip the pair (zero matches) or consume one text character (at least one match). The state transition takes a few attempts to get right; the implementation is compact once you do.

12. Wildcard Matching (LC 44) * matches any sequence including empty, which is simpler than regex but needs a different base case. Solve this immediately after LC 10. The two problems together make the difference in * semantics a permanent mental anchor for string DP.

13. Best Time to Buy and Sell Stock IV (LC 188) State machine DP with dimensions for day, transactions used, and holding status. dp[k][0] and dp[k][1] as "k transactions used, not holding" and "k transactions used, holding" reduces every stock variation to a state machine modification. This is the general version of the entire Stocks series.

14. Russian Doll Envelopes (LC 354) Sort by width ascending, height descending within equal widths. Now it's 1D LIS on heights. The descending sort on height prevents two envelopes with the same width from being nested. Patience sorting then gives O(n log n). The trick is seeing it as LIS at all.

15. Dungeon Game (LC 174) Forward DP fails because minimum health at a cell depends on what comes after it, not before. Solve backwards from the princess. You'll probably try forward first. That's expected. Let the failure teach you exactly why the direction matters.

16. Longest Valid Parentheses (LC 32) Stack DP: push the index on (, pop on ), and the span from current index to the new stack top gives a valid length. The stack stores unmatched open-paren indices as sentinels. Three distinct correct approaches exist here; knowing all three builds real flexibility.

17. Longest Increasing Path in Matrix (LC 329) DFS with memoization on a grid, no visited set needed, because the strictly increasing constraint makes cycles impossible. Each cell depends only on its smaller neighbors, so the DAG structure is implicit. The same pattern applies to any DAG longest-path.

18. Partition Array Into Two Arrays (LC 2035) Meet in the middle: split in half, enumerate subset sums for each half, binary search for the best complement. O(2^n) brute force becomes O(2^(n/2) log n). When n is around 20 and no clean DP state space exists, meet in the middle is often the only path.

Graph and Tree Problems: Draw It Before You Code It

19. Binary Tree Maximum Path Sum (LC 124) Dual-return pattern: return the best single-arm gain to the parent, update the global maximum with both arms inside. The function signature lies. The recursion returns one value but computes a different one internally. Every hard tree DP problem uses this shape.

20. Serialize and Deserialize Binary Tree (LC 297) Preorder with explicit null markers is the cleanest encoding. Serialization tests your understanding of recursive tree structure and how to reconstruct it from a linear representation. A design problem that tells you whether your mental model of recursion is actually solid or just functional.

21. Critical Connections in a Network (LC 1192) Tarjan bridge-finding: a back edge from a descendant to an ancestor proves an alternative path exists. If no descendant can reach above a given edge, that edge is a bridge. This is the most accessible entry into Tarjan's disc and low-link arrays. Understand it, and Tarjan's SCC follows naturally.

22. Word Ladder II (LC 126) BFS to find the shortest-path distance to the target, then DFS backtrack to reconstruct all shortest paths. Two distinct phases: BFS gives layer distances, DFS gives the actual paths. Getting both correct simultaneously is where most candidates fail.

23. Sort Items by Groups (LC 1203) Two-level topological sort: one for items within groups, one for groups themselves. Build two dependency graphs and run Kahn's algorithm on each. The nested structure is the novel element. If you can do this cleanly, topological sort is genuinely understood.

24. Maximum Employees to a Meeting (LC 2127) Functional graphs decompose into rho-shaped components: a cycle with tails hanging off it. Two cases: one large cycle, or interleaved two-cycles with the longest chains attached. This tests whether you can model constraints as a graph and reason about its topology. Appears whenever each element maps to exactly one other.

O(n) But Nothing Looks Linear

25. First Missing Positive (LC 41) The array itself is the hash table. Index i should store i+1 if present. Cyclically swap each element to its correct position, then scan for the first mismatch. O(n) time, O(1) space. The flagship problem for index-as-hash-bucket reasoning.

26. Largest Rectangle in Histogram (LC 84) For each bar, find the nearest shorter bar on left and right using a monotonic stack. The maximum rectangle through bar i has height heights[i] and width equal to the gap between those boundaries. Every element is pushed and popped exactly once. Arguably the most important monotonic stack problem on the site.

27. Maximal Rectangle (LC 85) Reduce to LC 84 once per row. Treat each row as the base of a histogram where heights[j] counts consecutive filled cells above it in column j. One call to the histogram solution per row gives O(mn). Teaches you to decompose 2D problems into repeated 1D subproblems.

28. Count of Smaller Numbers After Self (LC 315) Merge sort naturally counts inversions. During the merge step, each element from the right half that slots before a left-half element contributes one inversion count. The connection between merge sort and inversion counting reappears in several other hard problems.

Backtracking: Prune First, Then Code

29. N-Queens (LC 51) Track occupied columns, diagonals, and anti-diagonals as sets rather than scanning the board. O(1) conflict check per placement. N-Queens is the foundational backtracking problem with non-trivial constraint propagation. Every hard backtracking problem is a variation: choices, constraint check, undo.

30. Sudoku Solver (LC 37) Track available values per row, column, and box. Choose the cell with fewest options first. The minimum remaining values (MRV) heuristic isn't required for correctness, but it keeps your runtime from becoming an embarrassing counterexample. It's the same principle behind optimized constraint satisfaction solvers. Hard backtracking teaches you to prune before you recurse, not after.

What These 30 Problems Actually Teach

Count the distinct techniques: variable sliding window, monotonic deque, two-heap median, event sweep, partition binary search, answer-space binary search, interval DP, string DP with branches, state machine DP, meet-in-the-middle, backwards DP, dual-return tree DP, Tarjan bridges, functional graph decomposition, cyclic sort hashing, merge-sort inversion counting, MRV backtracking. That's 17 techniques in 30 problems.

Work through these in order within each section. Before you look at any solution, write down why the naive approach fails. The failure mode is the lesson.

When you're ready to test your reasoning under pressure, not just your code, SpaceComplexity runs voice-based mock interviews where you explain your thinking in real time. That's the condition that separates candidates who know the solution from candidates who get the offer.

Coding interview difficulty is 60% medium in real distributions. These 30 hards cover the tail with the highest return per hour spent.