Monotonic Array · Optimal Solution

Two flags. One scan. One answer.

A reactor monitoring system captures coolant temperatures every second. Before triggering an alert, it must verify whether the latest reading window trends in a single direction — steadily rising, steadily falling, or holding flat. An array is monotonic if it is entirely non-decreasing or entirely non-increasing. Two boolean flags start alive; each adjacent-pair comparison can only kill a flag, never revive one. If either survives, the array is monotonic. O(n) time. O(1) space.

Interactive

Watch the flags survive — or die

Concept

The dual-flag invariant

Start with two hypotheses about the array. Each comparison can only eliminate one — never restore it. The algorithm succeeds if at least one hypothesis survives.

adjacent pairs

The algorithm compares each consecutive pair exactly once. No revisiting, no lookahead — a single left-to-right scan.

two flags

Begin assuming the array could be non-decreasing and non-increasing. A rise kills the non-increasing flag. A fall kills non-decreasing. Equal kills neither.

one survivor suffices

The array is monotonic if at least one flag is still alive when the scan ends. If both die, the array had both a rise and a fall — not monotonic.

Algorithm

Scan, compare, eliminate

The algorithm tracks two boolean flags through a single pass over adjacent pairs.

  1. 1

    Initialize both flags as true

    canBeNonDecreasing = true and canBeNonIncreasing = true. Both directions are possible until contradicted.

  2. 2

    Scan adjacent pairs

    For each pair (nums[i−1], nums[i]): if nums[i] > nums[i−1], kill non-increasing. If nums[i] < nums[i−1], kill non-decreasing. If equal, kill neither.

  3. 3

    Early termination

    If both flags are dead, return false immediately — the array has both a rise and a fall, so no future pair can change the verdict.

  4. 4

    Verdict

    After all pairs: return canBeNonDecreasing || canBeNonIncreasing. If either survived, the array is monotonic.

Edge Cases

Where the flags tell the story

The flag states at the end reveal the array's structure.

All equal elements

Every comparison is equal, so neither flag is ever killed. Both survive — the array is simultaneously non-decreasing and non-increasing. This is the purest monotonic case.

Equal prefix

Equal pairs at the beginning keep both flags alive. The direction is only decided at the first unequal pair. This is why the first-pair heuristic fails — it would lock in a direction too early and reject valid monotonic arrays.

Single element

No adjacent pairs to compare means zero iterations. Both flags remain alive by default — trivially monotonic. The empty loop handles this without a special case.