L61 · Mock Set 3 — One Hard, 45 min

Series: LeetCode — From Basics to Interview-Ready · Session 61 / 65 · Phase 4 · Interview simulation

Why this session exists

Hards are usually two Mediums stacked. That is the claim this session is built on, and it holds far more often than the difficulty label suggests.

Trapping Rain Water is prefix maxima plus suffix maxima — two array scans you already own. Median of Two Sorted Arrays is binary search plus a partition invariant. Word Ladder II is BFS plus backtracking on the parent graph. Merge K Sorted Lists is a heap plus the two-list merge from an Easy. In each case the difficulty is not in either component. It is in seeing that there are two components and finding where they join.

So the skill being trained today is decomposition — specifically, locating the seam. And the secondary skill, which matters at least as much in a real loop, is being visibly productive for forty-five minutes on a problem you do not fully solve. Failing a Hard is normal and frequently survivable. Failing it silently, with nothing on the screen and no stated approach, is not.

A note on expectations. Do not expect to solve it. Roughly speaking, if you solve the Hard outright you picked one that was too close to something you knew, and the session taught you less than a genuine struggle would have. The target outcome is: correct decomposition, a working brute force, a stated plan for the optimisation, and a partial implementation. That set is a pass in most real interviews.

Blank-file warm-up

None. Cold, same as the other mocks.

One setup step: pick a Hard without reading its statement. Filter by difficulty, skip anything whose title you recognise, and take one. Do not browse until something looks tractable — that selection bias is how people accidentally pick a Hard they have already half-solved.

If you did L58's recording, keep your one chosen communication habit in mind. This session is also a check on whether that fix survived contact with a harder problem, which is where such fixes usually collapse.

Pattern anatomy

The pattern is seam-finding, and the invariant is: at every moment you are working on a named sub-problem, not on "the problem". The failure state on a Hard is a kind of undirected circling where you are thinking hard about everything at once and making no reducible progress. Naming a sub-problem — even the wrong one — restores structure.

# HARD DECOMPOSITION PROTOCOL — 45 minutes, one problem.
#
# STAGE 1 — BRUTE FORCE, ALWAYS (0-8 min)
#   Write the exponential or quadratic solution. Actually write it, do not just describe it.
#   Two reasons: it proves you understood the problem, and the optimisation is almost always
#   found by staring at the brute force and asking which step repeats work.
#   In a real interview a working brute force is a partial pass. Silence is not.
#
# STAGE 2 — FIND THE SEAM (8-20 min)
#   Run these four probes in order. One of them usually opens the problem.
#
#   PROBE A — "what would I precompute?"
#     If the brute force recomputes something per index, precompute it.
#     Prefix sums, prefix maxima, suffix maxima, counts. This alone solves many Hards.
#
#   PROBE B — "what if the input were sorted?"
#     If sorting makes it easy, the real question is whether you can afford the sort
#     or need an order-maintaining structure (heap, BST, Fenwick).
#
#   PROBE C — "what is the state?"
#     If the answer depends on choices made so far, it is DP or backtracking.
#     Write dp[i] = ... in ENGLISH before any code. Wrong state definition is the
#     single most common way a DP Hard is lost.
#
#   PROBE D — "which two patterns do I know that each solve HALF of this?"
#     This is the seam probe proper. Say two pattern names out loud and check whether
#     their composition covers the problem. Most Hards answer to this.
#
# STAGE 3 — IMPLEMENT THE HALF YOU CAN (20-40 min)
#   Even if the other half is unsolved. Working code for one component plus a clear
#   statement of the missing piece is a far stronger position than nothing.
#
# STAGE 4 — STATE WHERE YOU ARE (40-45 min)
#   Out loud: what works, what does not, what you would do with more time,
#   and what the complexity would be if the plan completed.

Probe D is the one worth internalising. "Which two things I already know solve half of this each" is a question you can ask about any Hard, and it converts an intimidating monolith into a search over a small set of known pieces.

The cue

You are looking at a decomposable Hard — as opposed to one that genuinely needs an unfamiliar algorithm — when:

1. The problem asks for two things at once. "Find the k most frequent" is counting plus selection. "Longest valid substring" is often validity-checking plus a window. Two nouns in the objective usually means two components.
2. A brute force is easy to write but obviously too slow. That is the good case: the gap between brute force and optimal is where a known pattern lives, and you can search for it systematically with the four probes.
3. One of the constraints is oddly specific. "The array is sorted", "values are at most 100", "k is at most 10". Specific constraints are load-bearing — they are there because the intended solution uses them.
4. You recognise a familiar sub-structure in an unfamiliar frame. "This inner part is just next-greater-element" is the seam appearing.
5. The Hard is a known Medium with one extra dimension. "Word Break" is a Medium; "Word Break II" adds reconstruction, which is the standard DP-plus-backtracking composition. Many Hards are literally a Medium with output reconstruction bolted on.

The case where decomposition does not apply is when the problem needs a specific named algorithm you have never met — max-flow, suffix automaton, heavy-light decomposition. You will recognise this by the four probes all returning nothing. That is a legitimate outcome and the correct response is to say so, implement the brute force, and move on. Not every Hard is fair.

Guided solve

No fixed problem, since yours is unseen. What follows is the protocol worked through with a concrete example, so you can see what the probes look like when they fire.

Worked example: Trapping Rain Water. Given heights, compute the water trapped.

Stage 1, brute force. For each index, water above it is min(max height to the left, max height to the right) - height[i], floored at zero. Computing those two maxima per index by scanning gives O(n²).

def trap_brute(h):
    total = 0
    for i in range(len(h)):
        left = max(h[:i + 1])
        right = max(h[i:])
        total += min(left, right) - h[i]
    return total

That is correct and too slow, which is exactly the position you want to be in at minute eight.

Stage 2, probes. Probe A fires immediately: the brute force recomputes the same prefix maximum and suffix maximum over and over. Precompute both in two passes. That is the seam — the problem is prefix maxima plus suffix maxima, two array scans you have owned since the early sessions.

def trap(h):
    n = len(h)
    if n < 3:
        return 0
    left = [0] * n
    right = [0] * n
    left[0] = h[0]
    for i in range(1, n):
        left[i] = max(left[i - 1], h[i])
    right[n - 1] = h[n - 1]
    for i in range(n - 2, -1, -1):
        right[i] = max(right[i + 1], h[i])
    return sum(min(left[i], right[i]) - h[i] for i in range(n))

O(n) time, O(n) space. There is a two-pointer version that gets space to O(1), and mentioning it is worth a point even if you do not write it — but the O(n)-space version is a complete, correct answer to a Hard, reached by a single probe.

Notice the shape of what happened. Nothing clever was invented. The brute force was written, one probe was applied, and a known pattern appeared. That is the entire method, and it works on more Hards than intuition suggests.

Solo timed

One unseen Hard, 45 minutes, no editorial, narrated out loud if you can.

Hints, kept generic:

• At minute 8, if you have no brute force on screen, stop trying to be clever and write the exponential one. You cannot search for the seam without something to look at.
• At minute 20, if no probe has fired, pick the most promising one and commit anyway. Circling is worse than committing to a wrong path — the wrong path fails informatively and quickly.
• At minute 40, stop implementing and state your position out loud regardless of where you are. Practising the summary is part of the session.

Common failure modes

Refusing to write the brute force. The most common and the most costly. It feels like wasted time on a Hard, and it is the thing that most reliably reveals the optimisation. It is also the difference between a partial pass and a zero in a real interview.

Circling without a named sub-problem. Thinking hard about the whole problem simultaneously produces no reducible progress. If you cannot name what you are currently working on, you are circling — run the probes.

Pursuing an approach past the point it stopped working. Sunk cost applies to interview minutes. If your chosen probe has produced nothing in ten minutes, say so out loud and switch. Announcing the switch is a strength signal.

Silence during the hard part. Whatever communication fix you chose in L58 will collapse here if it has not consolidated, because difficulty consumes exactly the bandwidth that narration needs. Watch for it.

Implementing nothing because the full solution is not clear. Half a solution plus a stated plan beats an empty editor by an enormous margin. Implement the component you understand.

Not stating the position at the end. Even when you have failed, "here is what works, here is what does not, here is what I would try next, and the complexity would be O(n log n) if it completed" converts a failure into a demonstration of structured thinking.

Complexity

Session budget rather than an algorithm:

Stage allocation: brute force 0–8 min, probes 8–20 min, implementation 20–40 min, position statement 40–45 min. The stage boundaries are checkpoints — at each one, ask whether you are where you should be, and if not, move on regardless.

Expected outcome distribution: full solve is the minority case. Correct decomposition plus a working brute force plus a partial optimal implementation is the target and is a pass in most real loops.

Post-session cost: 20 minutes for the autopsy, using the same four buckets from L57 — classification, template, implementation, time. Then re-solve from scratch tomorrow whether or not you solved it today.

Spaced queue

Today's Hard enters the queue at whatever it earned. The ladder applies as usual — cold +60d, warm +21d, hint +7d, failed +2d then +7d — with one adjustment specific to Hards: a Hard you solved only after reading the editorial is failed, not hint. Hards decay faster than anything else and the standard is stricter.

Re-solve it from scratch tomorrow regardless of today's outcome. For a Hard, the second attempt is where most of the learning happens, because you now know the seam and can practise the implementation without the search.

Also check: did the L58 communication habit survive? If narration collapsed during the hard part, that goes back on the list for the L64 contest.