Find the Minimum Shared Increment on Nonadjacent Array Positions

You may perform at most one operation on an integer array. Choose a set of pairwise nonadjacent indices and add the same nonnegative integer x to every chosen element. Find the smallest x that can make the entire array nondecreasing, or return -1 if no such operation exists.

Function Signature

minimum_nondecreasing_increment(values: list[int]) -> int

Rules

• Chosen indices are pairwise nonadjacent: no two chosen indices differ by one.
• The same x must be used at every chosen index.
• Unchosen elements do not change.
• Nondecreasing means each element is at most the next one after the operation.
• If the array is already nondecreasing, return 0. This includes an empty array or one-element array under the exercise's explicit boundary convention.
• There is no requirement to choose an index when no change is needed.

Constraints

• 0 <= len(values) <= 200000.
• -1000000000 <= values[i] <= 1000000000.
• x is an integer and has no additional artificial upper bound.
• Do not mutate the input.

Examples

Input: values = [3,1,4,2]

Output: 2

Choose indices 1 and 3 to obtain [3,3,4,4].

Input: values = [3,1,2]

Output: -1

Raising index 1 enough to reach 3 makes it exceed index 2, and indices 1 and 2 cannot both be selected.

Input: values = [1,2,2,5]

Output: 0

Input: values = []

Output: 0

Smallest Shared Increment on Nonadjacent Indices to Sort an Array

You are given an integer array values. You may perform at most one operation on it.

The operation works like this: choose a set of pairwise nonadjacent indices (no two chosen indices differ by one), pick a single nonnegative integer x, and add that same x to every chosen element. Elements at indices you did not choose are left unchanged. You are never required to choose an index, so choosing nothing is allowed.

An array is nondecreasing when every element is at most the element that follows it. Return the smallest nonnegative integer x for which some such choice of nonadjacent indices makes the whole array nondecreasing, or return -1 if no choice of indices and x can do it.

If the array is already nondecreasing, return 0; by this exercise's explicit boundary convention that includes the empty array and any one-element array. Do not mutate the input array.

Example 1:

Input: values = [3, 1, 4, 2]
Output: 2

Choosing the nonadjacent indices 1 and 3 with x = 2 gives [3, 3, 4, 4], which is nondecreasing. x = 1 is not enough, because 1 + 1 = 2 is still below values[0] = 3.

Example 2:

Input: values = [3, 1, 2]
Output: -1

Index 1 would have to be raised to at least 3 to catch up with values[0] = 3, but then it exceeds values[2] = 2, and indices 1 and 2 are adjacent, so they cannot both be chosen.

The answer can be as large as 2,000,000,000 and intermediate quantities such as values[i] + x can reach 3,000,000,000, which is larger than 2^31 - 1, so use 64-bit integers (long in Java, long long in C++).

Hints

1. Consider one adjacent pair at a time and remember that its two positions can never both be chosen, so a pair admits only three situations: neither position raised, the left one raised, or the right one raised.
2. When values[i] > values[i + 1], ask which of the two positions could possibly be raised given that x is nonnegative; the answer leaves you no freedom at either position.
3. Each adjacent pair turns into either a lower bound or an upper bound on the single shared x; the operation exists only when all of those bounds can hold simultaneously.

Approach

Examine every adjacent pair (i, i + 1) on its own. Because chosen indices are pairwise nonadjacent, at most one of the two positions of a pair can be raised, which leaves exactly three possibilities for that pair:

• neither is raised: the pair is satisfied only if values[i] <= values[i + 1];
• index i is raised: needs values[i] + x <= values[i + 1], i.e. x <= values[i + 1] - values[i];
• index i + 1 is raised: needs values[i] <= values[i + 1] + x, i.e. x >= values[i] - values[i + 1].

If values[i] > values[i + 1] (a descent), the first option fails outright and the second would need a negative x, so index i + 1 MUST be raised and index i MUST NOT be. That forcing determines everything:

1. First pass: set raised[i + 1] = True for every descent at pair (i, i + 1). If some index is both marked and the left end of a descent (raised[i] is True and values[i] > values[i + 1]) it is simultaneously required to be raised and required not to be, so the answer is -1. This is exactly the situation of two consecutive descents, whose two forced indices would be adjacent.
2. Otherwise the marked set is itself pairwise nonadjacent and is the only set worth using. Adding any unmarked index never helps: raising an element only tightens the constraint with its right neighbour, while the left-hand constraint it would relax already holds (otherwise that index would have been marked).
3. Second pass: collect the bounds. Every descent contributes a lower bound x >= values[i] - values[i + 1]; take the maximum as low. Every marked index i that still has a right neighbour contributes an upper bound x <= values[i + 1] - values[i]; take the minimum as high.
4. If there was no descent, low stays 0 and the array is already nondecreasing, so return 0. Otherwise return low when there is no upper bound or low <= high; return -1 when low > high.

Invariant: after the first pass, raised[] is precisely the set of indices that EVERY valid solution must raise, so the set of feasible x is exactly the integers in the interval [low, high] (with high = +infinity when no marked index has a right neighbour). The smallest feasible x is therefore low whenever that interval is nonempty.

Edge cases: arrays of length 0 or 1 are nondecreasing and return 0; a descent in the final pair leaves its forced index without a right neighbour, so it contributes no upper bound; an all-equal array has no descent and returns 0; a forced index may need to land exactly on its right neighbour (low == high), which is still valid because nondecreasing allows equality. With values bounded by 1e9 in absolute value, low can be 2000000000 and values[i] + x can reach 3000000000, so 64-bit arithmetic is used in Java and C++. The input array is only read, never mutated.

• Time complexity: O(n)
• Space complexity: O(n)