Making Minimal Changes to Change Range of the Array

Question

Consider having an array filled with elements a0,a1,a2,....,a(n-1). Consider that this array is sorted already; it will be easier to describe the problem.

Now the range of the array is defined as the biggest element - smallest element. Say this range is some value x. Now the problem I have is that, I want to change the elements in such a way that the range becomes less than/equal to some target value y.

I also have the additional constraint that I want to change minimal amount for each element. Consider an element a(i) that has value z. If I change it by r amount, this costsr^2.

Thus, what is an efficient algorithm to update this array to make the range less than or equal to target range y that minimizes the cost.

An example:

Array = [ 0, 3, 19, 20, 23 ] Target range is 17.

I would make the new array [ 3, 3, 19, 20, 20 ] . The cost is (3)^2 + (3)^2 = 18.

This is the minimal cost.

If you are adding/removing to some certain element a(i), you must add/remove that quantity q all at once. You can not remove 3 times 1 unit from a certain element, but must remove a quantity of 3 units once.

Answer 1

I think you can build two heaps from the array - one min-heap, one max-heap. Now you will take the top elements of both heaps and peek at the ones right under them and compare the differences. The one that has the bigger difference you will take and if that difference is bigger than you need, you will just take the required size and add the cost.

Now, if you had to take the whole difference and didn't achieve your goal, you will need to repeat this step. However, if you once again choose from the same heap, you have to remember to add the cost for the element you are taking out of the heap in that steps AND also for those that have been taken out of the processed heap before.

This yields an O(N*logN) algorithm, I'm not sure if it can be done faster.

Example:

Array [2,5,10,12] , I want difference 4. First heap has 2 on top, second one 12. the 2 is 3 far from 5 and 12 is 2 far from 10 so I take the min-heap and the two will have to be changed by 3. So now we have a new situation: [5, 10, 12] The 12 is 2 far from 10 and we take it, subtract 2 and get new situation: [5,10] Now we can choose any heap, both differences are the same (the same numbers :-) ). We just need to change by 1 so we get subtract 1 from 10 and get the right result. Now, because we changed 5 to 6 we would also have to change the number that was originally 12 once more to 9 so the resulting cost:

[2 - changed to 5, 5 - unchanged, 10 - changed to 9, 12 - changed to 9].

Answer 2

Here is a linear-time algorithm that minimizes the piecewise quadratic objective function. Probably it can be simplified.

Let the range be [x, x + y], where x is a variable. For different choices of x, there are at most 2n + 1 possibilities for which points lie in the range, arising from 2n critical values a0 - y, a1 - y, ..., a(n-1) - y, a0, a1, ..., a(n-1). One linear-time merge yields the critical values in sorted order. For each of the 2n - 1 intervals [w, z] between critical values where the range contains at least one point, we can construct and minimize a quadratic function consisting of a sum where every point aj less than w yields a term (x - aj)^2 and every point aj greater than z + y yields a term (x + y - aj)^2. The global minimum lies at the mean of aj (for terms of the first type) or aj - y (for terms of the second type); the endpoints of the interval must be checked as well. Naively, this gives a quadratic-time algorithm.

To get down to linear time, it suffices to update the sum preceding the mean computation incrementally. Each of the critical values has an associated event indicating whether the point responsible for it is entering or leaving the interval, meaning that that point's term should enter or leave the sum.