1064. One Change to Make It Non-Decreasing

A row of n integers is given. You may change AT MOST ONE entry to any integer you like. Print yes if the row can be made non-decreasing, so a[i] <= a[i+1] everywhere, or no otherwise.

4 2 3 4 -> yes change the 4 to something at most 2 4 2 1 3 -> no two separate falls 3 4 2 -> yes change the 2 up to 4, or the 4 down to 2 1 4 2 3 -> yes change the 4 down to 2

## What most people try first

For each position, try removing it and check whether the rest is non-decreasing with room for a value in the gap. That is O(n^2) and it is the brute force this problem was checked against. It is also the clearest correct statement of the question: position i is fixable exactly when the row without a[i] is non-decreasing AND some integer fits between a[i-1] and a[i+1], which needs a[i-1] <= a[i+1] when both neighbours exist.

## Count the falls, then look at the one that matters

A FALL is a position i with a[i-1] > a[i].

* zero falls: the row is already non-decreasing, answer yes * two or more falls: one change touches one entry and fixes at most one fall, answer no * exactly one fall at i: there are exactly two repairs to consider

For the single fall at i, either lower a[i-1] or raise a[i].

lowering a[i-1] to a[i] works when i == 1 or a[i-2] <= a[i] raising a[i] to a[i-1] works when i == n-1 or a[i-1] <= a[i+1]

Answer yes if either works.

## Why only those two repairs

The change must be at i - 1 or at i, since any other entry leaves the fall in place.

If the change is at i - 1, it must bring that entry down to at most a[i], and the cheapest legal choice is exactly a[i]: any smaller value is at least as likely to break the pair (i-2, i-1), and any larger one keeps the fall. So testing a[i-2] <= a[i] covers every possible new value.

If the change is at i, it must raise that entry to at least a[i-1], and the cheapest legal choice is exactly a[i-1]: any larger value is at least as likely to break the pair (i, i+1). So testing a[i-1] <= a[i+1] covers every possible new value.

Reducing "any integer" to a single candidate on each side is the whole trick, and it is the reason this is a constant amount of work rather than a search.

## Both repairs must be tried

Checking only one of them is the usual bug. 4 2 3 4 is fixable only by lowering the first entry, and 1 4 2 3 is fixable only by lowering the 4, which in this framing is the a[i-1] repair with i = 2; testing solely the "raise a[i]" branch there would need a[1] = 4 <= a[3] = 3, which is false, so a one-branch solution answers no.

## The two ends

When the fall is at i = 1 there is no a[i-2], and lowering a[0] is always safe. When it is at i = n - 1 there is no a[i+1], and raising a[n-1] is always safe. Reading past either end is the crash this problem is really guarding.

## Overflow

Values fit in a signed 32 bit integer, limit 2147483647, and nothing is added or multiplied.

## Where this sits

Problem #478 asks for the FEWEST changes rather than whether one is enough, and that needs a longest-non-decreasing-subsequence argument on a[i] - i rather than a case analysis. Problem #1048 allows only increments and asks for their total. Three questions, one row, three completely different methods.

## Cost

Time O(n). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a[i] ≤ 1000000000`