What pattern does each cue suggest: sorted input, longest contiguous stretch, and next-stronger-later value?
answer
- read the input's guarantees, not just the ask
- each cue names an access shape
- two ends that can move toward each other
- adjacent spans overlap; reuse the overlap
- items waiting for a later, stronger value
basics
~20 sA cue narrows the pattern family: sorted input points to converging pointers or binary search, a longest contiguous stretch points to a sliding window or prefix sums, and 'next stronger later value' points to a monotonic stack.
solid answer
~50 sEach cue names the *shape of access* the problem allows, not the answer. Sorted input means order is already an invariant you can exploit, so two pointers walking inward or a binary search over a boundary become available. A longest or best **contiguous** stretch means adjacent candidate spans overlap heavily, so you reuse the previous span instead of recomputing it — a sliding window when the tracked quantity is monotone, prefix sums when it is not. "For each item, the next later item that beats it" means each item waits for its resolver, which is exactly what a monotonic stack maintains in O(n) total. The discipline is to say the cue out loud before the pattern: "the manifest is sorted, so both ends can converge." That makes the mapping checkable, and it exposes fast when the cue is present but a constraint disqualifies the pattern.
go deeper
Be ready to read a short statement and name a pattern plus the exact phrase that suggested it. Memorising a handful of cue-to-pattern pairs is fine at this level, but you must be able to point at the licensing word.
An interviewer expects you to explain why the cue licenses the pattern — why order lets one comparison discard a whole side, why overlapping spans permit reuse. Also state what would invalidate the mapping.
Show that you confirm before committing: name the cue, name the pattern, name the assumption it rests on, and check the assumption against the stated constraints before writing a line.
Own the framing that cue reading is a hypothesis generator, not a lookup table. When you set an interview bar, credit the candidate who names a cue and then disproves it over one who pattern-matches correctly by luck.
## What a cue actually is A cue is a phrase in the problem statement that constrains the **shape of the access** you are allowed to make — not the algorithm, and not the complexity. Practiced candidates read a fresh statement twice: once for the *ask* (what must be returned: an existence check, a count, a maximum, a position, a reconstruction), and once for the *guarantees* (is the input ordered, are values bounded, may values be negative, must the result be contiguous). The cue lives in the guarantees; the ask decides which member of the licensed family you use. Interviewers measure this mapping explicitly. "Talk me through how you'd approach it" is scored on whether you can name the cue you keyed on, not on whether you produce the optimal solution in the first minute. ## The triage table | Cue in the statement | What it licenses | Why | |---|---|---| | Input is sorted / monotone | Converging pointers, binary search on a boundary, a merge pass | Order is an invariant, so one comparison rules out a whole side | | Best/longest **contiguous** span | Sliding window, or prefix sums plus a lookup structure | Adjacent spans overlap; reuse the overlap instead of recomputing | | "Next greater/smaller later" | Monotonic stack | Each element waits for its resolver and is popped once | | "Has this value been seen" / pair complement | Hash map of seen values | Turns a repeated linear scan into an expected-constant lookup | | k largest/smallest, or a stream | Size-k heap | Keeps only the frontier, O(n log k) rather than a full sort | | "Grouped", "connected", "same component" | Union-find or a traversal | The ask is about reachability, not about order | The table is a starting hypothesis, never a verdict. ## Three worked reads **A shipping manifest, sorted by crate weight: is there a pair of crates whose combined weight comes closest to the container's remaining capacity without exceeding it?** Cue: sorted. Ask: a *pair* with a target relation. Sorted plus pair-with-target licenses two pointers converging from the lightest and heaviest crate — if the pair is too heavy, only the heavy end can help, so move it inward; otherwise record the candidate and move the light end. O(n) after the input is already ordered, O(1) extra space. **A chat log, one message length per entry: the longest run of consecutive messages whose total length stays under a display cap.** Cue: *consecutive*. Consecutive candidate runs overlap by all but one entry, so a window that extends on the right and shrinks on the left reuses that overlap — provided the tracked total moves monotonically, which it does while lengths are non-negative. **Radio telemetry, a signal strength per sample: for each sample, the next later sample that is stronger.** Cue: "next later item that beats it." Each sample sits on a stack of not-yet-resolved samples; a new stronger reading pops and resolves everything weaker beneath it. Every sample is pushed once and popped once, so the whole pass is O(n) even though a naive read looks quadratic. ## Cues narrow; they do not decide The single most common junior error is treating the cue as the answer. Three ways the mapping fails: - **The cue underdetermines the pattern.** Sorted input licenses converging pointers, a boundary binary search, *and* a merge pass — which one you use depends on whether the ask is a pair, a threshold, or a combination of two ordered sources. - **A constraint disqualifies the pattern.** "Contiguous stretch" suggests a window, but if values may be negative the window's shrink step is unsound and you need prefix sums with a lookup structure instead. - **The word means something else than you read.** *Subarray* and *substring* are contiguous; *subsequence* is not, and a window cannot represent a candidate set that skips positions. That one word usually moves the problem from windows to dynamic programming. ## How to use it in the room Say the cue, say the pattern it licenses, then say what would invalidate it: "contiguous plus non-negative lengths, so a sliding window — if lengths could be negative I'd switch to prefix sums." That is thirty seconds, it is checkable by the interviewer, and it converts a wrong guess into a ten-second correction rather than ten minutes of dead code. Cue reading is a hypothesis generator; the confirmation step is what makes it engineering rather than recall.
- The statement says 'subsequence' rather than 'contiguous run'. Does the window cue still hold?No. A window represents a contiguous span, so it cannot express a candidate that skips positions. Once selections may skip, advancing the left edge no longer discards a dominated candidate, and the problem almost always becomes dynamic programming or a greedy over a sorted order. Contiguous versus non-contiguous is the single most decisive word in the statement, and it is worth confirming before naming any pattern.
- Why say the cue out loud instead of just starting on the pattern it suggests?Because the cue is the part that can be checked cheaply. If your mapping is wrong, an interviewer can correct it in ten seconds; if you silently start coding, the same error surfaces ten minutes later with a half-written solution attached. Narrating the cue also forces you to state the assumption it rests on, which is exactly where the disqualifying constraint usually hides.
- Two cues fire at once — the input is sorted and the ask is about a contiguous run. How do you choose?Let the ask lead and the guarantee follow. The ask determines the family (a contiguous-run question is a span-reuse problem), and the extra guarantee usually simplifies inside that family rather than replacing it — sortedness may make the window's monotonicity obvious or make a boundary search possible over the run lengths. Name both aloud and state which one you are keying on.
A cue is a triage tag, not a diagnosis: it tells you which shelf of instruments to reach for, and you still have to examine the patient before you pick one off the shelf.
saying these in an interview costs you the question
- Says sorted input always means binary search
- Names a pattern but cannot say which word licensed it
- Treats contiguous runs and subsequences as interchangeable
- Reaches for a window whenever the word 'stretch' appears
- Recites cue-pattern pairs without the invariant underneath