UMPIRE — The Problem-Solving Framework

Review boundary and corrected contracts

Use the proposed framework as a practice aid, not a proven hiring rubric. The daily-temperature stack contains unresolved indices in non-increasing temperature order; each is pushed once and popped at most once. The sorted-pair exercise depends on sorted input.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Internalise UMPIRE — Understand, Match, Plan, Implement, Review, Evaluate — a proposed practice routine for making requirements, reasoning and checks explicit. It is neither a fixed-duration rule nor a guarantee of recovery.

Series: LeetCode — From Basics to Production-Ready · Session 6 / 65 · Phase 0 · Foundations

Prerequisites: L01 (constraints → budget), L02 (complexity), L04–L05 (your first patterns: two-pointer compaction and hashing). UMPIRE is the process that decides WHICH pattern to reach for.

What this pattern IS — a routine for the blank minutes

Every other session teaches a pattern (hashing, two pointers). This session teaches the process that decides which pattern to use, and what to do in the terrifying first minute when you have no idea.

Beginning to type before understanding the output or constraints can commit you to the wrong task. But difficulty can also come from missing prerequisites, an unfamiliar proof or an implementation bug; routine alone does not solve those problems.

UMPIRE supplies six prompts. When stuck, identify which artifact is missing: a contract, a candidate approach, an invariant, an implementation, a test or a cost argument. For example, “I have a quadratic baseline but no safe way to discard candidates” is more actionable than “I am bad at this.” Sometimes the next useful move is a small brute-force prototype, a counterexample or asking for a prerequisite explanation—not forcing a known pattern onto the problem.

A checklist is a reminder, not a guarantee that steps cannot be skipped. Revisit earlier steps when a test refutes an assumption. No comparative study or hiring-score evidence for this particular routine is claimed here.

The six steps — what UMPIRE stands for

U  Understand   Restate the problem. Ask clarifying questions. Write 2-3 examples
                by hand, including an EDGE case (empty, single, duplicates, negatives).
M  Match        Which known pattern fits? Read the constraints (L01) and the shape:
                sorted? pairs? subarray? tree? "Have I seen a problem like this?"
P  Plan         Say the algorithm in plain words / pseudocode BEFORE coding.
                State the invariant and target complexity; invite questions if collaborating.
I  Implement    Translate the plan to clean code. Small, named helpers. No cleverness.
R  Review       Read your code line by line against your hand example. Check the
                edge cases you wrote in step U. Fix off-by-ones.
E  Evaluate     State final time AND space complexity. Discuss the follow-up
                (scale n, streaming, less space, duplicates) and how you'd adapt.

Why separate the prompts? A plan can expose an error before it is spread through code, while a concrete test can expose an error in the plan itself. Neither stage has a guaranteed correction cost. Writing edge cases before implementation can reduce the temptation to test only familiar successes; add newly discovered cases afterward too.

Treat Match as hypothesis generation. Sorted pair sums suggest an elimination proof; a contiguous range does not by itself justify a sliding window; “fewest steps” suggests BFS only when transitions have equal cost, otherwise weighted-graph or DP reasoning may be needed. A technique name is not a proof, and a constraint bound is not a stopwatch.

The template — UMPIRE as a runnable checklist

Keep this literally beside you while practising until it is automatic:

U — Understand
    [ ] Restate the problem in my own words.
    [ ] Inputs/outputs, types, ranges (read Constraints — L01).
    [ ] 2-3 examples by hand + at least ONE edge case.
    [ ] Clarify: empties? duplicates? negatives? sorted? one answer or all?
 
M — Match
    [ ] Identify all input/output sizes; estimate work and memory (L01).
    [ ] Shape cues: sorted->two pointers/binary search; pair/complement->hash;
        subarray/substring->sliding window/prefix; tree/graph->DFS/BFS;
        "all combinations"->enumeration; "fewest equal-cost steps"->BFS.
    [ ] Verify candidate preconditions rather than treating these cues as rules.
    [ ] "What earlier problem does this resemble?"
 
P — Plan
    [ ] Pseudocode the approach in plain words.
    [ ] State target time AND space.
    [ ] State an invariant and check a hand example; seek feedback if collaborating.
 
I — Implement
    [ ] Clean code, named variables, small helpers. Handle the edge cases.
 
R — Review
    [ ] Trace my hand example line by line.
    [ ] Re-run each edge case mentally. Off-by-one? Empty input?
 
E — Evaluate
    [ ] Final complexity, stated aloud.
    [ ] Follow-up: bigger n? streaming? O(1) space? duplicates? -> how I'd adapt.

Name: Umpire calling the game

Picture: Six labeled checkpoints, with arrows back as well as forward. A failing test can send you from Review back to Understand or Plan. Name the missing evidence, then choose the next useful action.

• Before committing to an optimized implementation, explain what it must compute and why the approach should work.

• Write initial edge cases during Understand and add counterexamples discovered later.

• Say the plan and the target complexity OUT LOUD before coding.

• Stuck is a base, not a wall: name your base, do its action.

Trigger: Use the checklist when practicing or when progress stalls; compress or revisit stages according to the actual uncertainty.

Memory technique — the six-word peg sentence

The acronym U-M-P-I-R-E is already a memorable word, but under stress people forget what the letters mean. Anchor each letter to one imperative verb in a single sentence you can recite in four seconds:

Understand it, Match it, Plan it, Implement it, Review it, Evaluate it.

Six "-it" verbs, in order. Say it as a chant at the start of every practice problem. Because each verb is the action of its base (not a noun to interpret), reciting the sentence tells you exactly what to DO next, not just what the letter abbreviates. Repetition may make the prompts easier to recall, but no fixed number of problems establishes fluency or transfer.

Misconception: every strong solver must follow one visible sequence. Experts can use different orders, short prototypes and familiar invariants; this article does not measure their behavior. The practical question is whether you can produce the needed contract, correctness argument, implementation, tests and cost analysis—not whether you recite an acronym.

Local check: after an attempt, inspect which artifact was missing when an error arose. On a later unseen task, try supplying that artifact earlier. Record whether it helped; a personal comparison is not proof that this framework outperforms alternatives.

What reviewers actually ask — and how UMPIRE handles each

The following are illustrative practice mappings, not a universal interviewer script or employer rubric. They show where the prompts can be useful:

• Two Sum (1) · Practice selection. (Easy) — U: one answer? negatives? M: pair/complement → hash (L05). P: state expected O(n) hash plan with bounded-cost keys. E: follow-up "sorted → O(1) space" (two pointers).
• Valid Palindrome (125) · Practice selection. (Easy) — U: which chars count, case? M: two ends → two pointers (L07). E: follow-up "allow one deletion (680)."
• Best Time to Buy and Sell Stock (121) · Practice selection. (Easy) — M: running min in one pass. R: edge = strictly decreasing prices → answer 0. E: follow-up "multiple transactions."
• Number of Islands (200) · Practice selection. (Medium) — M: grid connectivity → DFS/BFS flood fill. E: follow-up "huge grid → BFS to dodge recursion limits."
• Search in Rotated Sorted Array (33) · Practice selection. (Medium) — M: problem states O(log n) → binary search. P: decide which half is sorted. E: follow-up "duplicates (81)."
• Coin Change (322) · Practice selection. (Medium) — M: "min steps / fewest coins" → DP. U: edge = amount 0, or unreachable → -1. E: follow-up "count the ways (518)."
• Merge Intervals (56) · Practice selection. (Medium) — M: intervals → sort by start then merge. E: the sort dominates → O(n log n).

Worked example 1 — UMPIRE on a fresh problem

Problem: Given an array of daily temperatures, return, for each day, how many days until a warmer temperature (0 if none).

U — Understand. Input: list of ints. Output: list of ints, same length. Example [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]. Edge: strictly decreasing → all zeros; single element → [0]. Clarify: temperatures can repeat; "warmer" is strictly greater.

M — Match. At n=100,000, scanning every later day can inspect nearly five billion pairs. Seek better growth rather than assuming a universal timeout boundary. Shape cue: "next greater element to the right" → monotonic stack (L17). We keep indices of days still waiting for a warmer day.

P — Plan. Walk left to right. Keep a stack of indices whose warmer day is unknown. For each new day, while it is warmer than the day at the stack top, we just found that day's answer — pop it and record the distance. Then push the current day. Target O(n) time (each index pushed/popped once), O(n) space.

I — Implement.

def daily_temperatures(temps):
    answer = [0] * len(temps)            # default 0 = no warmer day
    stack = []                           # unresolved indices; non-increasing temperatures
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:  # current day is warmer than a waiting day
            j = stack.pop()              # that waiting day's answer is now known
            answer[j] = i - j            # distance in days
        stack.append(i)                  # this day now waits for its warmer day
    return answer

R — Review. Trace the example: matches [1,1,4,2,1,1,0,0]. Edge strictly decreasing [5,4,3] → nothing ever pops → [0,0,0]. Correct. Off-by-one: i - j is the day gap, right.

Proof and E — Evaluate. Stack indices increase while their temperatures are non-increasing; equal temperatures stay because warmer means strictly greater. If a new day pops j, no earlier day between j and the current one was warmer, or j would already have been removed. Any unresolved index below a non-popping top has at least that top’s temperature, so it cannot be resolved by the current day either. Each index is pushed once and popped at most once: O(n) total work and O(n) stack/output storage under bounded-cost comparison.

For a value-output variant, store the new temperature instead of its distance and specify the no-answer sentinel. For a circular distance variant, handle empty input separately, scan virtual indices 0 through 2n-1 using temps[i % n], push original indices only in the first pass, and record i-j when an original index is resolved. A strict greater-than comparison prevents an element from resolving itself. Returning values instead is the usual Next Greater Element II contract; do not confuse that output with distances.

Worked example 2 — using UMPIRE to escape being stuck

Problem: Find the length of the longest substring without repeating characters.

U. Input string; output int. Example "abcabcbb" → 3 ("abc"). Edge: "" → 0; "bbbb" → 1. Clarify: ASCII, "substring" is contiguous.

M. Stuck? Restate the baseline: enumerating all substrings and rebuilding each uniqueness check takes O(n³) total scanned characters; extending a set from each starting index gives expected O(n²) work. Bottleneck: we re-scan overlapping substrings. Shape cue: "longest contiguous substring satisfying a property" → sliding window (L10), with a set/last-seen map to detect repeats. That is the escape: naming the brute-force bottleneck pointed at the pattern.

P. Keep a unique-character window. On a repeated character, remove leftmost characters through the previous occurrence, then add the new character. This leaves the longest valid suffix ending at the current right boundary: any earlier start would retain that duplicate, and starts already discarded earlier cannot become valid by extending the window. Maximize over right endpoints. Each position enters and leaves at most once, giving expected O(n) total set work and O(min(n, alphabet size)) space.

I — Implement.

def length_of_longest_substring(s):
    seen = set()                         # chars currently in the window
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:                # duplicate -> shrink from the left
            seen.remove(s[left])
            left += 1
        seen.add(ch)                     # ch now fits
        best = max(best, right - left + 1)  # window size
    return best

R. "abcabcbb": window grows to abc (3), hits a again, shrinks, stays length 3 → returns 3. "" → loop never runs → 0. "bbbb" → window never exceeds 1. Correct.

E. Expected O(n) time for bounded-cost character hashing, O(min(n, alphabet)) space. Follow-up: "at most K distinct characters (340)" → same window with a Counter and a distinct-count check.

Goal: Run the full UMPIRE loop yourself.

Hint: Given a sorted array, return TRUE if any two entries sum to target. Write U, M, P before coding, then the code.

# U: sorted ints, one bool out. Example [1,2,4,7], target 6 -> True (2+4). Edge: len<2 -> False.
# M: sorted + pair-sum -> two pointers, O(1) space (L07).
# P: lo/hi from the ends; move lo up if sum too small, hi down if too big.
def has_pair_sum(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return True
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return False
 
print(has_pair_sum([1, 2, 4, 7], 6))     # True

Now do the E step out loud: state the complexity, then name the follow-up ("what if it were unsorted?" → hash, L05).

Decision: full checklist, compressed checklist or exploratory prototype?

• A full checklist makes missing artifacts visible during learning, but costs attention and may duplicate reasoning already done.
• A compressed checklist is reasonable for a familiar task if the contract, proof and tests remain explicit; difficulty labels do not establish familiarity.
• A small exploratory prototype can reveal an unknown API or counterexample. Label it as exploration, then return to the contract and proof rather than promoting a passing example to a solution.

Use the lightest process that exposes the actual uncertainty. A routine should help you think, not forbid useful experiments or force every problem into a remembered category.

Where this shows up in production

The prompts resemble useful questions in engineering work: what is required, which prior design applies, what assumptions need review, how will it be implemented and tested, and how will costs be checked? Real projects also need security, deployment, monitoring and rollback work. Neither using this acronym nor succeeding on these exercises proves future job behavior or prevents building the wrong thing.

You can now…

• Recite UMPIRE and the six '-it' verbs from memory.

• Run Understand: restate, example, edge cases, clarifying questions.

• Match a problem's shape and constraints to a pattern family.

• State a plan and target complexity OUT LOUD before coding.

• Review code against pre-written edge cases to catch off-by-ones.

• Evaluate final complexity and answer the standard follow-up.

• Treat 'stuck' as a step: name your base and do its action.

Self-check (answer follows each question).

Recall check

Q: What do the letters in UMPIRE stand for, in order?

A: Understand, Match, Plan, Implement, Review, Evaluate.

Q: What can Match and Plan contribute before implementation?

A: Candidate approaches, their preconditions, a correctness invariant and a cost estimate. Missing these can leave a wrong assumption undiscovered, but this page does not establish which mistakes candidates make most often.

Q: In the Understand step, name three things you should produce before moving on.

A: A restatement in your own words, 2-3 hand examples including an edge case, and clarifying questions (empties/duplicates/negatives/sorted).

Q: You are stuck at Match — nothing fits. What is the concrete next action?

A: State a correct baseline and its cost, isolate repeated work, and test a candidate improvement’s assumptions. Overlapping ranges can suggest a window, but the window still needs a monotonicity or validity invariant; otherwise seek another approach or prerequisite.

Q: What must you say out loud during Plan and again during Evaluate?

A: The target/final time AND space complexity — plan it before coding, confirm it after, then give the follow-up.

Q: ★ Why does stating the plan out loud make mistakes cheaper than coding first?

A: An explicit plan gives a collaborator an earlier chance to challenge assumptions before more code depends on them. There is no fixed one-sentence or ten-minute cost guarantee; some flaws become visible only in a prototype or test.

Practice queue

Solve each by writing U, M, P as comments FIRST, then the code, then say E aloud.

• Two Sum (1) — Easy · practise Match → hash. (spaced-repeat anchor: +7d)
• Valid Palindrome (125) — Easy · Match → two pointers.
• Best Time to Buy and Sell Stock (121) — Easy · one-pass running min.
• Longest Substring Without Repeating Characters (3) — Medium · Match → sliding window.
• Daily Temperatures (739) — Medium · Match → monotonic stack.
• Number of Islands (200) — Medium · Match → DFS/BFS. (spaced-repeat anchor: +21d)
• Coin Change (322) — Medium · Match → DP.

Next session (L07) is your first pattern applied under the UMPIRE loop end to end: two pointers converging from opposite ends of a sorted array, and the monotonicity proof that lets one comparison discard a whole row of candidates.

Corrective source notes

• Minimum Stack / Minimum Queue - Algorithms for Competitive Programming — A monotonic queue obtains linear total work by bounding each element’s insertions/removals. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.