2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ad your first question: see here. $\endgroup$ – dkaeae Dec 12 '18 at 16:36
  • $\begingroup$ Please credit the original source of the problem. $\endgroup$ – Apass.Jack Dec 12 '18 at 17:57
  • $\begingroup$ @Apass.Jack The original source is me, this is a problem I ran into while analysing some data $\endgroup$ – Brenlla Dec 12 '18 at 18:05
  • $\begingroup$ In that case, could you please share a bit of background how you ran into this problem? Why is it important to avoid close consecutive numbers? $\endgroup$ – Apass.Jack Dec 12 '18 at 18:08
  • 2
    $\begingroup$ @Apass.Jack Unfortunately I cannot go into much detail. Briefly, those numbers represent a property for individual contributions of subpopulations into a larger dataset. So the difference between those numbers should be above a threshold, which (kind of) represents the data noise. $\endgroup$ – Brenlla Dec 12 '18 at 18:13
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Memory consumption could be brought down to $O(1)$ since we only look at the two most recent values of keep and modify. $\endgroup$ – Erick Wong Dec 13 '18 at 2:52
  • $\begingroup$ @ErickWong, nice observation. $\endgroup$ – Apass.Jack Dec 13 '18 at 2:59
  • $\begingroup$ If I run minimize([0,0.25,0.6,0.7,1.2], 0.5) it returns 2. How would I transform only 2 elements in input array to obtain valid_array? $\endgroup$ – Brenlla Dec 13 '18 at 18:11
  • $\begingroup$ @Brenlla Move 0.25 and 0.7 to the far end of the array. If there is a requirement that the list remain sorted after the modifications, please adjust your question to clarify this restriction. $\endgroup$ – Erick Wong Dec 13 '18 at 18:32
  • $\begingroup$ By the way, do you want the adjustment be smaller than the threshold? That would be a reasonable requirement. You may want to keep the array as sorted. Another reasonable requirement. Please raise a new question if you want either or both of two requirements satisfied. $\endgroup$ – Apass.Jack Dec 13 '18 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.