01 / The idea
A monitor asks three questions that invite a loop inside a loop.
A server room monitor keeps a week of daily temperature readings, a list of maintenance windows, and a log. For each day it wants to know how many days passed before a warmer one. For the calendar it wants the maintenance windows merged so no two overlap. And in the log it wants the first place a warning pattern appears.
Each question has an obvious nested loop: scan forward from every day, compare every pair of windows, try the pattern at every position. Each also has structure worth keeping. A monotonic stack holds the days still waiting, in an order a warmer day can resolve from the top. Interval merging sorts once and keeps a single active window. KMP remembers which part of the pattern repeats, so a mismatch does not throw away what already matched.
02 / Name the rule
Keep only what the next input can still change.
Stack. Keep the indexes of days whose answer is not known yet. Their readings never increase from bottom to top, so a new warmer day pops and answers the waiting days on top, and stops at the first one that is not colder. Every day is pushed once and popped at most once.
for each day i:
while stack and reading[i] > reading[stack.top]:
j = stack.pop()
answer[j] = i - j
stack.push(i)Intervals. Sort the windows by start. The first becomes active; each later window either starts after the active end and begins a new block, or overlaps and stretches it. Touching windows merge here, because maintenance can run straight on.
sort intervals by start
for next in intervals:
if next.start > active.end: start a new active window
else: active.end = max(active.end, next.end)Borders. KMP first builds a prefix table: for each position in the pattern,
the length of the longest proper prefix of the pattern that is also a suffix of what has
matched so far. In WARN WARN FAIL, a mismatch after WARN WARN falls back to WARN and compares again at the same place in the log. The log cursor
never moves backward.
What “monotonic” means hereAn order kept, not values sorted
A monotonic stack keeps its readings in a non-increasing order from bottom to top. KMP sorts nothing and keeps no stack; what only ever moves forward is its position in the text, while the matched length falls back through borders. The shared idea is to retain only information that can still affect the next decision.
03 / Follow one operation
Three streams, three compact summaries.
Before you watch, predict how long day 1 (75°) waits for a warmer day, and where the pattern
falls back. The animation resolves the waiting readings, merges the maintenance calendar,
and searches the log for WARN WARN FAIL, then lines up each approach’s work
against its nested-loop baseline. Try it lets you compare each structure with its baseline
yourself.
Keep the useful order.
daily readings
Find the next warmer reading
stack = []No readings processed yet
Read day 0 at 72; waiting stack is [0]. Step 1.
Read day 0 at 72; waiting stack is [0]. Step 1.
Follow the next structural decision.
Read day 0 at 72; waiting stack is [0]. Step 1.
Reduced motion: choose a scene to see its completed state.
Read this scene
Read day 0 at 72; waiting stack is [0]. Step 1.
Read day 0 at 72; waiting stack is [0]. Step 1.
Find each reading’s next warmer day.
Watch restarts when you return. Step through keeps the selected trace. Try it measures another strategy on the same monitor fixtures.
04 / Read the shape
Return the answer and the evidence together.
Basic form is the three algorithms, nextWarmer, mergeIntervals, and findPattern, each beside its nested-loop
baseline and able to record every decision. In the wild wraps them in small public
functions and composes them in one monitor review.
nextWarmer, mergeIntervals, and findPattern: the stack, the sort-and-merge pass, and the KMP prefix table, each beside its baseline mode, with optional traces.
function validateValues(values: readonly number[]): number[] {
if (!Array.isArray(values) || values.length === 0 || values.length > MAX_VALUES)
throw new RangeError(`values must contain 1 to ${MAX_VALUES} whole numbers`);
return values.map((value, index) => {
if (!Number.isSafeInteger(value) || value < -100 || value > 200)
throw new RangeError(`values[${index}] must be a bounded reading`);
return value;
});
}
function validateIntervals(values: readonly Interval[]): Interval[] {
if (!Array.isArray(values) || values.length === 0 || values.length > MAX_VALUES)
throw new RangeError(`intervals must contain 1 to ${MAX_VALUES} entries`);
return values.map((interval, index) => {
if (
!Number.isSafeInteger(interval.start) ||
!Number.isSafeInteger(interval.end) ||
interval.end <= interval.start
)
throw new RangeError(`intervals[${index}] must end after it starts`);
return { ...interval };
});
}
function validateText(text: string, pattern: string): void {
if (
typeof text !== 'string' ||
text.length > MAX_TEXT ||
typeof pattern !== 'string' ||
pattern.length > MAX_TEXT
)
throw new RangeError(`text and pattern must be at most ${MAX_TEXT} characters`);
}
// A stack whose readings never increase keeps unresolved readings in the only order that can still be helped by a future warmer value.
export function nextWarmer(
values: readonly number[],
mode: TemperatureMode = 'monotonic-stack',
trace = false
): TemperatureEvaluation {
const checked = validateValues(values);
const answers = Array<number>(checked.length).fill(-1);
const steps: TemperatureStep[] = [];
let work = 0;
if (mode === 'scan') {
for (let index = 0; index < checked.length; index++) {
for (let next = index + 1; next < checked.length; next++) {
work++;
if (checked[next] > checked[index]) {
answers[index] = next - index;
break;
}
}
if (trace) steps.push({ kind: 'read', index, value: checked[index], waiting: [] });
}
return { kind: 'temperature', mode, values: checked, answers, work, steps };
}
const stack: number[] = [];
for (let index = 0; index < checked.length; index++) {
while (stack.length && checked[index] > checked[stack.at(-1)!]) {
const waiting = stack.pop()!;
answers[waiting] = index - waiting;
work++;
if (trace)
steps.push({
kind: 'resolve',
index,
resolved: waiting,
wait: index - waiting,
value: checked[index]
});
}
stack.push(index);
work++;
if (trace) steps.push({ kind: 'read', index, value: checked[index], waiting: [...stack] });
}
return { kind: 'temperature', mode, values: checked, answers, work, steps };
}
// Sorting by start puts overlaps next to one another; then a single active interval absorbs its neighbors.
export function mergeIntervals(
values: readonly Interval[],
mode: IntervalMode = 'sort-and-merge',
trace = false
): IntervalEvaluation {
const checked = validateIntervals(values);
const steps: IntervalStep[] = [];
let work = 0;
if (mode === 'pairwise') {
const merged: Interval[] = [];
for (const interval of checked) {
let current = { ...interval };
for (let index = 0; index < merged.length; index++) {
work++;
if (current.start <= merged[index].end && current.end >= merged[index].start) {
const before = { ...merged[index] };
current = {
start: Math.min(current.start, before.start),
end: Math.max(current.end, before.end)
};
merged.splice(index, 1);
if (trace) steps.push({ kind: 'merge', into: before, with: interval, result: current });
index--;
}
}
merged.push(current);
if (trace) steps.push({ kind: 'consider', interval, accepted: true, current });
}
merged.sort((a, b) => a.start - b.start);
return { kind: 'interval', mode, values: checked, merged, work, steps };
}
const order = [...checked].sort((a, b) => a.start - b.start || a.end - b.end);
const merged: Interval[] = [];
for (const interval of order) {
work++;
const current = merged.at(-1);
if (!current || interval.start > current.end) {
merged.push({ ...interval });
if (trace)
steps.push({ kind: 'consider', interval, accepted: true, current: { ...interval } });
} else {
const before = { ...current };
current.end = Math.max(current.end, interval.end);
if (trace)
steps.push({ kind: 'merge', into: before, with: interval, result: { ...current } });
}
}
return { kind: 'interval', mode, values: checked, merged, work, steps };
}
function prefixTable(pattern: string, trace: boolean, steps: MatchStep[]): number[] {
const prefix = Array<number>(pattern.length).fill(0);
let length = 0;
for (let index = 1; index < pattern.length; index++) {
while (length && pattern[index] !== pattern[length]) {
const from = length;
length = prefix[length - 1];
if (trace) steps.push({ kind: 'fallback', from, to: length });
}
if (pattern[index] === pattern[length]) length++;
prefix[index] = length;
if (trace) steps.push({ kind: 'prefix', index, length });
}
return prefix;
}
// KMP falls back to the pattern's own prefix table instead of moving the text cursor backward.
export function findPattern(
text: string,
pattern: string,
mode: MatchMode = 'kmp',
trace = false
): MatchEvaluation {
validateText(text, pattern);
const steps: MatchStep[] = [];
if (pattern.length === 0)
return { kind: 'match', mode, text, pattern, index: 0, comparisons: 0, prefix: [], steps };
let comparisons = 0;
if (mode === 'naive') {
for (let start = 0; start <= text.length - pattern.length; start++) {
let offset = 0;
while (offset < pattern.length) {
comparisons++;
const equal = text[start + offset] === pattern[offset];
if (trace)
steps.push({ kind: 'compare', textIndex: start + offset, patternIndex: offset, equal });
if (!equal) break;
offset++;
}
if (offset === pattern.length) {
if (trace) steps.push({ kind: 'found', index: start });
return { kind: 'match', mode, text, pattern, index: start, comparisons, prefix: [], steps };
}
}
return { kind: 'match', mode, text, pattern, index: -1, comparisons, prefix: [], steps };
}
const prefix = prefixTable(pattern, trace, steps);
let matched = 0;
for (let index = 0; index < text.length; index++) {
while (matched && text[index] !== pattern[matched]) {
const from = matched;
matched = prefix[matched - 1];
comparisons++;
if (trace) steps.push({ kind: 'fallback', from, to: matched });
}
comparisons++;
const equal = text[index] === pattern[matched];
if (trace) steps.push({ kind: 'compare', textIndex: index, patternIndex: matched, equal });
if (equal) matched++;
if (matched === pattern.length) {
const found = index - pattern.length + 1;
if (trace) steps.push({ kind: 'found', index: found });
return { kind: 'match', mode, text, pattern, index: found, comparisons, prefix, steps };
}
}
return { kind: 'match', mode, text, pattern, index: -1, comparisons, prefix, steps };
}func validateValues(values []int) ([]int, error) {
if len(values) == 0 || len(values) > maxValues {
return nil, fmt.Errorf("values must contain 1 to %d readings", maxValues)
}
copyOf := append([]int(nil), values...)
for index, value := range copyOf {
if value < -100 || value > 200 {
return nil, fmt.Errorf("values[%d] must be a bounded reading", index)
}
}
return copyOf, nil
}
func validateIntervals(values []Interval) ([]Interval, error) {
if len(values) == 0 || len(values) > maxValues {
return nil, fmt.Errorf("intervals must contain 1 to %d entries", maxValues)
}
copyOf := append([]Interval(nil), values...)
for index, interval := range copyOf {
if interval.End <= interval.Start {
return nil, fmt.Errorf("intervals[%d] must end after it starts", index)
}
}
return copyOf, nil
}
func nextWarmer(values []int, mode TemperatureMode) (TemperatureEvaluation, error) {
checked, err := validateValues(values)
if err != nil {
return TemperatureEvaluation{}, err
}
answers := make([]int, len(checked))
for index := range answers {
answers[index] = -1
}
work := 0
if mode == Scan {
for index := range checked {
for next := index + 1; next < len(checked); next++ {
work++
if checked[next] > checked[index] {
answers[index] = next - index
break
}
}
}
return TemperatureEvaluation{Mode: mode, Values: checked, Answers: answers, Work: work}, nil
}
stack := []int{}
for index, value := range checked {
for len(stack) > 0 && value > checked[stack[len(stack)-1]] {
waiting := stack[len(stack)-1]
stack = stack[:len(stack)-1]
answers[waiting] = index - waiting
work++
}
stack = append(stack, index)
work++
}
return TemperatureEvaluation{Mode: mode, Values: checked, Answers: answers, Work: work}, nil
}
func NextWarmer(values []int, mode TemperatureMode) (TemperatureEvaluation, error) {
return nextWarmer(values, mode)
}
func mergeIntervals(values []Interval, mode IntervalMode) (IntervalEvaluation, error) {
checked, err := validateIntervals(values)
if err != nil {
return IntervalEvaluation{}, err
}
merged := []Interval{}
work := 0
if mode == Pairwise {
for _, interval := range checked {
current := interval
index := 0
for index < len(merged) {
work++
if current.Start <= merged[index].End && current.End >= merged[index].Start {
if merged[index].Start < current.Start {
current.Start = merged[index].Start
}
if merged[index].End > current.End {
current.End = merged[index].End
}
merged = append(merged[:index], merged[index+1:]...)
continue
}
index++
}
merged = append(merged, current)
}
slices.SortStableFunc(merged, func(a, b Interval) int { return cmp.Compare(a.Start, b.Start) })
return IntervalEvaluation{Mode: mode, Values: checked, Merged: merged, Work: work}, nil
}
order := append([]Interval(nil), checked...)
slices.SortStableFunc(order, func(a, b Interval) int {
return cmp.Or(cmp.Compare(a.Start, b.Start), cmp.Compare(a.End, b.End))
})
for _, interval := range order {
work++
if len(merged) == 0 || interval.Start > merged[len(merged)-1].End {
merged = append(merged, interval)
continue
}
if interval.End > merged[len(merged)-1].End {
merged[len(merged)-1].End = interval.End
}
}
return IntervalEvaluation{Mode: mode, Values: checked, Merged: merged, Work: work}, nil
}
func MergeIntervals(values []Interval, mode IntervalMode) (IntervalEvaluation, error) {
return mergeIntervals(values, mode)
}
func prefixTable(pattern string) []int {
prefix := make([]int, len(pattern))
length := 0
for index := 1; index < len(pattern); index++ {
for length > 0 && pattern[index] != pattern[length] {
length = prefix[length-1]
}
if pattern[index] == pattern[length] {
length++
}
prefix[index] = length
}
return prefix
}
func FindPattern(text string, pattern string, mode MatchMode) (MatchEvaluation, error) {
if len(text) > maxText || len(pattern) > maxText {
return MatchEvaluation{}, fmt.Errorf("text and pattern must be at most %d characters", maxText)
}
if len(pattern) == 0 {
return MatchEvaluation{Mode: mode, Text: text, Pattern: pattern, Index: 0, Prefix: []int{}}, nil
}
comparisons := 0
if mode == Naive {
for start := 0; start <= len(text)-len(pattern); start++ {
offset := 0
for offset < len(pattern) {
comparisons++
if text[start+offset] != pattern[offset] {
break
}
offset++
}
if offset == len(pattern) {
return MatchEvaluation{Mode: mode, Text: text, Pattern: pattern, Index: start, Comparisons: comparisons, Prefix: []int{}}, nil
}
}
return MatchEvaluation{Mode: mode, Text: text, Pattern: pattern, Index: -1, Comparisons: comparisons, Prefix: []int{}}, nil
}
prefix := prefixTable(pattern)
matched := 0
for index := 0; index < len(text); index++ {
for matched > 0 && text[index] != pattern[matched] {
matched = prefix[matched-1]
comparisons++
}
comparisons++
if text[index] == pattern[matched] {
matched++
}
if matched == len(pattern) {
return MatchEvaluation{Mode: mode, Text: text, Pattern: pattern, Index: index - len(pattern) + 1, Comparisons: comparisons, Prefix: prefix}, nil
}
}
return MatchEvaluation{Mode: mode, Text: text, Pattern: pattern, Index: -1, Comparisons: comparisons, Prefix: prefix}, nil
}
func WarmerDays(values []int, mode TemperatureMode) ([]int, error) {
evaluation, err := nextWarmer(values, mode)
if err != nil {
return nil, err
}
return evaluation.Answers, nil
}
func MaintenanceWindows(values []Interval, mode IntervalMode) ([]Interval, error) {
evaluation, err := mergeIntervals(values, mode)
if err != nil {
return nil, err
}
return evaluation.Merged, nil
}
func SearchLog(text string, pattern string, mode MatchMode) (int, error) {
evaluation, err := FindPattern(text, pattern, mode)
if err != nil {
return -1, err
}
return evaluation.Index, nil
}Reading the TypeScriptOne trace, one result
Each evaluation returns its answer, a work counter, and a trace from the same run. The stack trace records reads and resolutions, the interval trace considerations and merges, and KMP comparisons, fallbacks, and prefix entries.
Reading the GoCopied slices and explicit errors
Go copies input slices before working and returns errors for bad input. Intervals sort
with slices.SortStableFunc, and the KMP result keeps the prefix table as
its own field.
What would I normally use in application code?Your runtime’s search, and a small loop for the rest
For finding text, your language’s own search: indexOf in TypeScript, strings.Index in Go. Neither uses KMP, and both are fast on ordinary text. Reach
for KMP when the text arrives as a stream you cannot rewind. The stack and the merge are a
few lines each, and usually written by hand.
05 / Try a decision
Decide what KMP keeps after a mismatch.
A mismatch inside a repeated pattern is where KMP earns its table. Decide what it does next before the feedback tells you.
06 / Follow the cost
Count what moves forward, then add the setup.
Here is every operation at a glance, with n readings, windows, or log characters and a pattern of length m. The rest of this section is about why an inner loop here is not quadratic.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Next warmer, nested scan | O(n²) | O(1) | For every reading, scan forward until a warmer value appears. |
| Next warmer, monotonic stack | O(n) | O(n) | Each index is pushed once and popped once when a future value resolves it. |
| Sort and merge intervals | O(n log n) | O(n) | Sorting by start dominates; the merge pass visits each ordered interval once. |
| KMP prefix table and search | O(n + m) | O(m) | Build borders for a pattern of length m, then scan text of length n without rewinding. |
| Naive string matching | O(nm) | O(1) | Try each possible start and compare the pattern from the beginning. |
The stack has a while inside a for, and is still linear: the pops
across the whole run cannot outnumber the pushes. KMP’s text cursor only advances, and each
fallback follows a prefix link. Interval merging is linear after sorting, so the sort sets
the total.
On seven readings and four windows the counters come out even or slightly in the baseline’s favor: the stack does 12 pushes and pops where the scan does 10 comparisons. The gain is in growth. Sixty-four falling readings cost the scan 2,016 comparisons and the stack 64 pushes. On the log, KMP already saves 13 of the naive search’s 45 comparisons.
07 / Give it a real job
Run each answer where the data arrives.
In a real monitor, readings arrive one a day, so the stack runs as they come: each new reading answers the days it beats, and the rest keep waiting. Maintenance windows arrive from several teams, so the calendar sorts and merges them once per change. The alerter watches a live log, and KMP’s refusal to rewind is exactly what a stream needs.
What the examples leave out is a decision too. Readings here are whole degrees; a real sensor needs a rule for ties and gaps. Windows are hours on one day, not time zones. And the log search finds one fixed pattern; several patterns at once are a job for Aho–Corasick.
In frontend code, interval merging is the one you are most likely to write, for busy blocks in a calendar view or overlapping selection ranges in an editor; the stack and KMP usually stay inside the libraries that need them.
08 / Make the call
Let the next input tell you what to keep.
Reach for a monotonic stack when each waiting item is answered by the first later value that beats it: next warmer, next higher, the nearest taller bar. Reach for sort-and-merge when overlapping ranges must become one list of non-overlapping blocks. Reach for KMP when a pattern repeats part of itself and the text cannot be read twice.
Look elsewhere when the question changes. A few readings or windows: the nested loop is fine. Ranges that keep arriving and must be checked for overlap as they come: an interval tree. Many patterns at once: Aho–Corasick. A pattern in text you can read freely: your runtime’s own search.
09 / Take the idea with you
Explain it without saying “monotonic stack,” “interval merging,” or “KMP.”
“I keep the days still waiting for a warmer one, coldest on top, and each new day answers the ones it beats. I sort the windows once and keep stretching the current one until a gap appears. When a search fails partway, I keep the part of the pattern that could still be the start of a match and carry on from where I am.” That describes the mechanisms. The names are what you call them in a review.
Before moving on, explain three things without the names: why a while inside a for is still linear here, why the windows must be sorted before merging, and
where WARN WARN FAIL falls back to. Then find a nested loop in your own code that asks
“what comes next that beats this?” and decide whether a stack would answer it.
Connections to follow nextRelated lessons
- Stack is the structure the waiting readings live in.
- Sorting is the setup that makes one pass of merging enough.
- Aho–Corasick extends the same fallback links to many patterns at once.