L06 · UMPIRE — The Problem-Solving Framework

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

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.

The naive approach to an interview is to read the problem and start typing, hoping the answer emerges. Under a ticking clock that produces panic: you freeze, or you commit to a half-formed idea and code yourself into a corner. The failure is not lack of knowledge — it is lack of routine.

UMPIRE is that routine. It is six named steps you run in order every single time. Its real value is psychological: when you get stuck, you are not "stuck" — you are simply on a step, and each step has a concrete action. "Stuck" becomes "I am in Match and nothing fits, so I will restate the brute force and look at its bottleneck." That reframing is most of what separates candidates who recover from ones who spiral.

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 target complexity. Get a nod from the interviewer.
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.

The single most common interview mistake is skipping straight from U to I — reading, then coding — with no M and P. That is how you write a correct-looking O(n^2) that times out, or code a wrong approach and have to restart with five minutes left.

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
    [ ] Constraint budget -> target complexity (L01 table).
    [ ] Shape cues: sorted->two pointers/binary search; pair/complement->hash;
        subarray/substring->sliding window/prefix; tree/graph->DFS/BFS;
        "all combinations"->backtracking; "min/max steps"->BFS/DP.
    [ ] "What earlier problem does this resemble?"
 
P — Plan
    [ ] Pseudocode the approach in plain words.
    [ ] State target time AND space.
    [ ] Sanity-check on my hand example. Get interviewer buy-in.
 
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.

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. After ~20 problems the chant fires automatically the instant you finish reading a prompt.

What interviewers actually ask — and how UMPIRE handles each

Interviewers rarely want the optimal answer instantly. The universal script they run — and the exact steps UMPIRE gives you a move for — is: clarify → brute force → its cost → the key insight → clean code → test an edge → final complexity → one follow-up. Mapping real problems onto the loop:

• Two Sum (1) · Amazon, Google, Meta (Easy) — U: one answer? negatives? M: pair/complement → hash (L05). P: state O(n) plan. E: follow-up "sorted → O(1) space" (two pointers).
• Valid Palindrome (125) · Meta, Microsoft (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) · Amazon, Microsoft (Easy) — M: running min in one pass. R: edge = strictly decreasing prices → answer 0. E: follow-up "multiple transactions."
• Number of Islands (200) · Amazon, Microsoft, Meta (Medium) — M: grid connectivity → DFS/BFS flood fill. E: follow-up "huge grid → BFS to dodge recursion limits."
• Search in Rotated Sorted Array (33) · Amazon, Microsoft, Meta (Medium) — M: problem states O(log n) → binary search. P: decide which half is sorted. E: follow-up "duplicates (81)."
• Coin Change (322) · Amazon, Google (Medium) — M: "min steps / fewest coins" → DP. U: edge = amount 0, or unreachable → -1. E: follow-up "count the ways (518)."
• Merge Intervals (56) · Amazon, Meta, Google (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. Constraints n up to 10^5 → need about O(n), so no O(n^2) "for each day scan forward." 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 = []                           # indices of days awaiting a warmer day (decreasing temps)
    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.

E — Evaluate. Each index is pushed and popped at most once → O(n) time, O(n) space. Follow-up: "return warmer temperature value instead of distance" → record temps[i] rather than i - j. Or "circular array (503)" → iterate twice with modulo.

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? No pattern jumps out. Match is a step, not a wall. Restate brute force: check every substring for uniqueness — O(n^3) or O(n^2). 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. Grow a window with a right pointer; keep a set of chars inside. On a duplicate, shrink from the left until the duplicate is gone. Track the max window length. O(n): each char enters and leaves the window once. O(k) space for the character set.

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. O(n) time, O(min(n, alphabet)) space. Follow-up: "at most K distinct characters (340)" → same window with a Counter and a distinct-count check.

# 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

Where this shows up in production

The UMPIRE loop is a scaled-down version of how engineers approach any real ticket: understand the requirement and edge cases, match it to a known design or prior art, plan and get review before building, implement, review/test, then evaluate performance and follow-ups. Senior engineers are not faster typists — they are disciplined about the understand-match-plan phase, which is why they rarely build the wrong thing. Interviewers score the loop precisely because it predicts on-the-job behaviour: someone who clarifies, names the approach, and tests edge cases will do the same when the stakes are a production system, not a whiteboard.

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.