How to find the minimum positive number K for an array to make the array in strictly ascending order

Question

How to find the minimum positive number K such that for each item in the array, adding or subtracting a number from [-K, K] can lead to a strictly ascending array?

For example:

• the array is [10, 2, 20]
• the min K is 5, a possible result is [10-5, 2+4, 20]
• k = 4 is not OK, because 10-4 == 2+4; the array can not be transformed to strictly ascending order

---

My guess is as follows

define f(i, j) = a[i] - a[j] + j-i-1 (require for i < j and a[i] > a[j] : all reverse order pairs)

The min K must satisfy the condition:

2*K > max f(i,j)

because if a pair (i, j) is not in ascending order, a[j] can only add K at most, a[i] can subtract K at most, and you need to leave space for items between a[i] and a[j] (because it's strictly ascending order), so (a[j] + K) - (a[i] - K) should be greater than (j-i-1) (the length between them).

So k >= max f(i, j)/2 + 1

The problem is I cannot prove whether k = max f(i, j)/2 + 1 is OK or not?

---

more clues:

i've thought about find an algorithm to determine a given K is enough or not, then we can use the algorithm to try each K from the possible minimum up to find a solution.

i'v come up with an algorithm like this:

for i in n->1  # n is array length
if i == n:
    add K to a[i]   # add the max to the last item won't affect order
else:
    # the method is try to make a[i] as big as possible and still < a[i+1]
    find a num k1 in [-K, K] to make a[i] to bottom closest to a[i+1]-1
    if found:
        add k1 to a[i]
    else no k1 in [-K, K] can make a[i] < a[i+1]
        return false
return true

i'm also such an algorithm is right or not

Answer 1

I think your guess is correct, but I can't prove it as well :-) Instead, I would start by simplifying your question

How to find the minimum positive number K such that for each item in the array, adding or subtracting a number from [-K, K] can lead to a strictly ascending array?

to this equivalent one by "adding" K:

How to find the minimum positive number 2*K such that for each item in the array, adding a number from [0, 2*K] can lead to a strictly ascending array?

We can solve that quite easily by iterating the array and keeping track of the needed 2K value for fulfilling the condition. It's quite similar to @ruakh's one but without the subtractions:

k2 = 0
last = arr[0]
for each cur in arr from 1
    if cur + k2 <= last
        last ++
        k2 = last - cur
    else
        last = cur
k = ceil ( k2 / 2 )

Answer 2

I think you're overthinking this a bit. You can just iterate over the elements of the array, keeping track of the current minimum-possible value of K, and of the current minimum-possible value of the last-seen element given that value of K. Whenever you find an element that proves your K to be too small, you can increase it accordingly.

For example, in Java:

int[] array = { 10, 2, 20 };
int K = 0, last = array[0];
for (int i = 1; i < array.length; ++i) {
    if (last >= array[i] + K) {
        // If we're here, then our value for K wasn't enough: the minimum
        // possible value of the previous element after transformation is still
        // not less than the maximum possible value of the current element after
        // transformation; so, we need to increase K, allowing us to decrease
        // the former and increase the latter.
        int correction = (last - (array[i] + K)) / 2 + 1;
        K += correction;
        last -= correction;
        ++last;
    } else {
        // If we're here, then our value for K was fine, and we just need to
        // record the minimum possible value of the current value after
        // transformation. (It has to be greater than the minimum possible value
        // of the previous element, and it has to be within the K-bound.)
        if (last < array[i] - K) {
            last = array[i] - K;
        } else {
            ++last;
        }
    }
}