How to find efficiently the minimum modification to avoid close consecutive numbers?

Question

I have an array of sorted numbers:

arr = [-0.1, 0.0, 0.5, 0.8, 1.2]

I want the difference (dist below) between consecutive numbers for that array to be above or equal a given threshold. For example, if threshold is 0.25:

dist = [0.1, 0.5, 0.3, 0.4] # must be >=0.25 for all elements

arr[0] and arr[1] are too close to each other, so one of them must be modified. In this case the desired array would be:

valid_array = [-0.25, 0.0, 0.5, 0.8, 1.2] # all elements distance >= threshold

In order to obtain valid_array, I want to modify the minimum amount of elements in arr. So I substract 0.15 from arr[0] rather than, say, substract 0.1 from arr[0] and add 0.05 to arr[1]:

[-0.2, 0.05, 0.5, 0.8, 1.2]

Previous array is also valid, but we have modified 2 elements rather than one. In order to obtain valid_array, I already have a brute force solution which works fine, but it is quite slow for large arrays. My questions are:

What is the time complexity of that brute force solution?

Does a more efficient algorithm even exist?

Edit

First, I need to clarify what I mean by difference, which I define the same way as in here, so out[n] = a[n+1] - a[n]. The fact that all elements in that difference must be above (or equal) threshold implies that valid_array is also sorted.

Second, the number of modifications (which must be minimized) is obtained by comparing elementwise the original arr and valid_array

Answer 1

Here is an algorithm that returns the minimum amount of elements that need to be modified. It is about as simple as possible and as fast as possible. Its time complexity is $O(n)$, where $n$ is the size of input array.

def minimize(arr, threshold):
    size = len(arr)

    # keep[i] or modify[i] is the minimal number of modification 
    # needed on arr[0:(i+1)], keeping or modifying the i-th
    # element respectively, so that any two consecutive numbers 
    # in arr[0:(i+1)] are greater than `threshold` apart.
    keep = [0] * size
    modify = [0] * size

    for i in range(1, size):
        modify[i] = min(keep[i - 1], modify[i - 1]) + 1

        if abs(arr[i] - arr[i - 1]) >= threshold:
            keep[i] = min(keep[i - 1], modify[i - 1])
        else:
            keep[i] = modify[i - 1]

    return min(keep[-1], modify[-1])

The criticall observation is that if a number at a certain index has been modified, we can consider it has been modified so wildly it will be more than threshold away from any of its neighbours, whether those neighbours will be modified or not.