What is the min buffer value such that an array of ints will be sorted in increasing order?

Question

Problem: Given an array of integers, find the minimum buffer value such that the array can be sorted in strictly increasing order. Each element in the array can add or subtract up to the buffer value.

Ex: [4, 0, 9, -2]

The minimum buffer value is 6, because you can change the array into:

[4 - (6 or 5 or 4 or 3), 0 + (-1 or 0 or 1 or 2), 9 - (6) = 3, -2 + (6) = 4]

I believe I have a solution that works O(N^2), but I'm wondering if I can do better.

EDIT: never mind, my solution doesn't work.

My solution:

For each element, draw a line with slope 1 passing that element. Find the smallest buffer value that allows every element to be shifted onto the line. Keep track of the buffer values obtained and return the smallest one at the end.

Thanks

Answer 1

O(n) can be achieved by looping the array one by one and keeping the invariant correct and keeping track of the current buffer size:

1. we start from left and go one by one to the right
2. a single element subarray is by definition sorted
3. adjust the current element using our current buffer to the lowest possible value (so the invariant still holds)
4. if current element (after adjustment) is bigger than the previous element then we do not need to do anything (sorted)
5. otherwise (unsorted) we need to update the buffer (increase it) - this is done trivially by checking the difference in the current element and the max of the already sorted array which is simply the previous element ( so we add abs((curr-prev)/2) + 1 to the current buffer) and the previous/current values (to the smallest values possible). At this point we don't need to care about earlier entries because since we are increasing the buffer to decrease the previous/current values we could simply subtract up to abs((curr-prev)/2) + 1 from each previous value and the invariant would hold.

Some examples to make it all more clear (bolded - current, italic - previous):

I) Input: [4, 0, 9, -2]

• [4] - sorted by definition
• [4,0] - unsorted, update current one with buffer [4,0], diff = (4-0)/2+1 = 3 => [1,2], buffer = 3 // the update is done as follow: decrease the previous value by the whole diff, for the current one check if newPrevious (1 here) plus 1 is in range current+-diff, if yes then set newPrevious+1, otherwise set current+diff
• [1,2,9] - sorted, update current one with buffer [1,2,6] // here update is done similarly to the previous update but instead off doing current+diff we do current-diff
• [1,2,6,-2] - unsorted, update current one with buffer [1,2,6,1], still unsorted so diff = (6-1)/2+1 = 3, buffer = 6, [1,2,3,4]

Done, buffer = 6

II) Input: [40, 31, 140, 131]

• [40] - sorted by definition
• [40,31] - unsorted, update current one with buffer [40,31], diff = (40-31)/2+1=5 => [35,36], buffer = 5
• [35,36,140] - sorted, update current one [35,36,135]
• [35,36,135,131] - unsorted, update current one [35,36,135,136]

Done, buffer = 5

III) Input: [1,1,1,1]

• [1] - sorted by definition
• [1,1] - unsorted, update current one [1,1], diff = (1-1)/2+1=1 => [0,1] (because 0+1 is ok), buffer = 1
• [0,1,1] - unsorted, update current one [0,1,2], sorted
• [0,1,2,1] - unsorted, update current one [0,1,2,2], diff = (2-2)/2+1=1 => [0,1,2,3], buffer = 2

Done, buffer = 2

IV) Input: [7,11,1,2,3]

• [7] - sorted by definition
• [7,11] - sorted, adjust [7,11]
• [7,11,1] - unsorted, adjust [7,11,1], diff = (11-1)/2+1 = 6 => [7,5,6], buffer = 6
  • here we can see that we do not need to check anything before 11 as all the previous numbers are smaller than 11 so if we do 11 - X we could simply do PREVIOUS - X and the invariant would still hold
• [7,5,6,2] - unsorted, adjust [7,5,6,7] <- invariant still holds, I simply didn't adjust the first 7 in the previous step
• [7,5,6,7,3] - unsorted, adjust [7,5,6,7,8]

Done, buffer = 6

V) Input: [0,1,3,-15]

Up until [0,1,3] nothing changed

• [0,1,3,-15] diff = 10, adjust prev and current [0,1,-7,-6] - again here we can see that we increase the buffer from 0 to 10 so all numbers to the left of 3 and 3 itself can be decreased by 10 and the invariant will hold but for the rest of the algorithm we don't need to do this

Done, buffer = 10

VI) Input: [1,2,3,4]

• [1] - sorted by definiton
• [1,2] - sorted, adjust by buffer 0
• [1,2,3] - sorted, adjust by buffer 0
• [1,2,3,4] - sorted, adjust by buffer 0

Done, buffer = 0

Answer 2

The original answer

My original answer consisted of the following three steps. That algorithm works provided that the max value in the normalized array comes before the min value in the normalized array. The sample arrays that I was considering were [4, 0, 9, -2] and [0, 1, 3, -15]. Note that in both of those sample arrays, the max precedes the min. However, this algorithm fails if the absolute min in the array appears before the absolute max. Two examples where the algorithm fails are [-15, 1] and [40, 31, 140, 131].

Step 1: subtract the array index from the value at that index

array:              4    0   9   -2
index:             -0   -1  -2   -3
                   ----------------
normalized array:   4   -1   7   -5

Step 2: scan the normalized array to find the min and max values

max =  7
min = -5

Step 3: subtract the min from the max and divide by 2 (rounding up if necessary) and there's your answer

(7 - (-5)) / 2 = 6

The rationale and flaw in the original answer

The idea behind my original answer was that the midpoint between the max and the min provided a target value that every entry in the normalized array could be adjusted to hit. The max and min being the farthest from the target required the largest adjustments and hence provided the answer. However, after seeing hk6279's comment, I realized that it's possible to have multiple targets for the normalized array. For example, consider the array [40, 31, 140, 131]. The first step is

array:         40  31   140  131
index:         -0  -1    -2   -3
               -----------------
normalized:    40  30   138  128

The target for the first two numbers is 35 (reachable with adjustments of +-5). The target for the second two numbers is 133 (also reachable with adjustments of +-5). So the answer is 5, and the adjustments to the array are

array:         40  31   140  131
adjustment:    -5  +5    -5   +5
               -----------------
sorted:        35  36   135  136

(Side note: the array [-15,1] also has two targets. The target for -15 is -15 with an adjustment of 0. The target for 0 (the normalized value of 1) is 0 with an adjustment of 0. So the answer is 0).

The more complicated (but still O(n)) answer

Step 1: Normalize the array by subtracting the array index from the value at that index. This step is unchanged from the original answer.

Step 2: Define a data structure to hold information about the array entries.

struct Section
{
   int max;           // the maximum value seen in this section of the array
   int min;           // the minimum value seen in this section of the array
   int startIndex;    // the starting index for this section of the array
   int endIndex;      // the ending index for this section of the array
}

Step 3: Scan the normalized array while creating an array of Section structs. (The sectionsArray may be as long as the normalized array.) The rules for creating the sectionsArray are

initialize the first section as { normalized[0], normalized[0], 0, 0 }

for each subsequent entry in the normalized array
{
   if ( normalized[i] > currentSection.max )        // found a larger value than the current max
   {
      newSection = { normalized[i], normalized[i], i, i }   // create a new section and add it to the sectionsArray
      currentSection = newSection                           // the new section is now our current section
   }
   else if ( normalized[i] < currentSection.min )           // found a new minimum for the current section
   {
      currentSection.min = normalized[i]                    // update the min and end of the current section
      currentSection.endIndex = i;
   }
   else                                                     // normalized[i] is within the current range of values
   {  
      currentSection.endIndex = i;              // update the end of the current section
   }
}

Note that in this step, the max values in the sectionsArray are in strictly ascending order. This is important for the next step.

Step 4: Working backwards from the end of the sectionsArray, combine sections where possible. The rule for combining two sections is

if ( sectionsArray[i].min <= sectionsArray[i-1].min )       // bigger max and smaller min allows preceding section to be absorbed into the current section  
{ 
   sectionsArray[i-1].max = sectionsArray[i].max            
   sectionsArray[i-1].min = sectionsArray[i].min            
   sectionsArray[i-1].endIndex = sectionsArray[i].endIndex

   discard sectionsArray[i]
}

Step 5: Scan the sectionsArray to find the largest difference between max and min. The largest difference, divided by two and rounded up if necessary, is the answer to the question. Also, the midpoint between min and max is the target value for that section of the array (target values can be truncated).

An example

Consider the array [8,5,8,6,14,12,18,13]. First normalize the array:

Input array:    8   5   8   6  14  12  18  13
index:         -0  -1  -2  -3  -4  -5  -6  -7
               ------------------------------
Normalized:     8   4   6   3  10   7  12   6

Then create the sections array:

{  8,  3,   0, 3 }   // started with 8, 4 became the min, 6 was in range, 3 replaced 4 as the min.  10 ended the section since it was higher than 8
{ 10,  7,   4, 5 }   // started with 10, 7 became the min.  12 ended the section.
{ 12,  6,   6, 7 }

Working backwards: The 10,7 section can be absorbed into the 12,6 section resulting in

{  8,  3,   0, 3 }
{ 12,  6,   4, 7 }

The maximum difference is 6, so the answer is 3.

The target for the first section is (8+3)/2 = 5 (after truncation) The target for the second section is (12+6)/2 = 9

The adjustments are:

Normalized:     8   4   6   3   10   7  12   6
Adjustments:   -3   1  -1   2   -1   2  -3   3
               -------------------------------
Targets:        5   5   5   5    9   9   9   9

Apply those same adjustments to the input array:

Input array:    8   5   8   6   14  12  18  13
Adjustments:   -3   1  -1   2   -1   2  -3   3
               -------------------------------
Sorted:         5   6   7   8   13  14  15  16

Applying this technique to other arrays seen in this thread

input:         4   0  9  -2
normalized:    4  -1  7  -5
sections:      { 4, -1, 0, 1 }  { 7, -5, 2, 3 }
combined:      { 7, -5, 0, 3 }
answer:        (7 - (-5)) / 2 = 6
targets:       one target for the entire normalized array => (7 + (-5)) / 2 = 1

input:         0  1  3  -15
normalized:    0  0  1  -18
sections:      { 0, 0, 0, 1 }  { 1, -18, 2, 3 }
combined:      { 1, -18, 0, 3 }
answer:        (1 - (-18)) / 2 = 10
targets:       one target for the entire normalized array => (1 + (-18)) / 2 = -8

input:         -15 1
normalized:    -15 0
sections:      { -15, -15, 0, 0 }  { 0, 0, 1, 1 }
combined:      same as above
answer:        0 (same answer for both sections)
targets:       targets are -15 and 0

input:         40  31  140  131
normalized:    40  30  138  128
sections:      { 40, 30, 0, 1 }  { 138, 128, 2, 3 }
combined:      same as above
answer:        5 (same answer for both sections)
targets:       targets are 35 and 133

The challenge

Find a counter example that breaks this algorithm and post it in the comments :)