What is the value of min buffer so that the ints array will be sorted in ascending order?

Question

Problem:. Given an array of integers, find the minimum buffer value so that the array can be sorted in strictly ascending order. Each element of the array can add or subtract a buffer value.

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

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

 [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 wonder if I can do better.

EDIT: it doesn't matter, my solution is not working.

My decision:

For each element, draw a line with a slope of 1 passing through this element. Find the smallest buffer value that allows each item to be wrap onto the line. Keep track of the resulting buffer values ​​and return the smallest at the end.

thanks

Answer 1

O(n) can be achieved by cycling the array one after the other and correctly preserving the invariant and tracking the current buffer size:

• we start left and go right one after another
• submatrix of one element is sorted by definition
• adjust the current element using our current buffer to the lowest possible value (so that the invariant is still preserved)
• If the current element (after adjustment) is larger than the previous element, we do not need to do anything ( sorted )
• otherwise ( unsorted ) we need to update the buffer (increase it) - this is done trivially, checking the difference in the current element and the maximum size of the already sorted array, which is just the previous one (so we add abs((curr-prev)/2) + 1 to the current buffer) and previous / current values ​​(up to the smallest possible values). At this point, we don’t need to care about the earlier elements, because as we increase the buffer to reduce previous / current values, we could just subtract to abs((curr-prev)/2) + 1 from each previous value and save invariant.

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

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

• [ 4 ] - sorted by definition
• [4, 0 ] - unsorted, update the current using the buffer [4, 0 ], diff = (4-0) / 2 + 1 = 3 => [1,2], buffer = 3 // the update is performed as follows: reduce the previous value by the whole diff, for the current one, check if newPrevious (1 here) is plus 1 in the range of the current + -diff, if so then set newPrevious + 1, otherwise set current + diff
• [1,2, 9 ] - sorted, updated the current using the buffer [1,2, 6 ] // here the update is performed similarly to the previous update but instead of doing the current + diff, we do current-diff
• [1,2, 6 , - 2] - unsorted, update the current one using the 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 the current using the buffer [40,31], diff = (40-31) / 2 + 1 = 5 => [35,36], buffer = 5
• [35.36, 140 ] - sorted, updated the current [35,36,135]
• [35,36,135, 131 ] - unsorted, update current [35,36,135,136]

Done, buffer = 5

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

• [ 1 ] - sorted by definition
• [1, 1 ] - unsorted, update the current one [1,1], diff = (1-1) / 2 + 1 = 1 => [0,1] (because 0 +1 is ok), buffer = 1
• [0,1, 1 ] - unsorted, update the current one [0,1,2], sorted
• [0,1,2,1] - unsorted, update the 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, since all previous numbers are less than 11, so if we do 11 - X, we could just do PREVIOUS - X and the invariant will still hold
• [7,5,6,2] - unsorted, adjust [7,5,6,7] <-invariant is still executed, I just did not 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]

Before [0,1,3] nothing has changed

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

Done, buffer = 10

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

• [1] - sorted by specific
• [1,2] - sorted, adjusted by buffer 0
• [1,2,3] - sorted, adjusted by buffer 0
• [1,2,3,4] - sorted, adjusted by buffer 0

Done, buffer = 0

Answer 2

Original answer

My initial answer consisted of the following three steps. This algorithm works under the condition that the max value in the normalized array precedes the min value in the normalized array. The sample arrays I reviewed were [4, 0, 9, -2] and [0, 1, 3, -15]. Note that in both of these sample arrays, max preceded by min . However, this algorithm fails if the absolute min in the array appears before the absolute max . Two examples in which the algorithm fails are [-15, 1] ​​and [40, 31, 140, 131].

Step 1: subtract the index of the array from the value in 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 min from max and divide by 2 (rounding if necessary), and there your answer

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

Justification and lack of original answer

The idea of ​​my initial answer was that the midpoint between max and min provided a target value so that each record in a normalized array could be adjusted to hit. max and min , which are the farthest from the target , required the greatest settings and, therefore, provided the answer. However, after seeing hk6279 comment, I realized that it is possible to have multiple targets for a normalized array. For example, consider an array [40, 31, 140, 131]. First step is

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

target for the first two numbers - 35 (available with settings + -5). target for the second two numbers - 133 (also available with settings + -5). So the answer is 5, and the array settings are

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

(Lateral note: the array [-15,1] also has two targets. The target for -15 is -15 with a setting of 0. The target for 0 (normalized value 1) is 0 with a setting of 0. Thus, the answer is 0).

More complex (but still O (n)) answer

Step 1: normalize the array by subtracting the array index from the value in that index. This step does not change from the original answer.

Step 2: Define a data structure for storing information about 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. Scanning a normalized array when creating an array of Section structures. ( sectionsArray can be as long as the array is normalized .) The rules for creating 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 maximum values ​​in sectionsArray are in strictly ascending order. This is important for the next step.

Step 4: Working back from the end of sectionsArray , merge sections where possible. The rule for combining two sections:

 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 sectionsArray to find the largest difference between max and min . The largest difference, divided into two and rounded, if necessary, is the answer to the question. In addition, the midpoint between min and max is the target value for this section of the array (target values ​​can be truncated).

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 an array of partitions:

 { 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 } 

Work back: section 10.7 can be absorbed by section 12.6, resulting in

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

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

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

Adjustments:

 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 the same settings 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 visible in this stream

 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 

Task

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

Answer 3

You can solve this problem using binary search.

• Suppose the buffer size is x = (low + high) / 2, what you can do is from each index from 0 to n - 1 (with n - numeric elements), you just need to calculate what is the minimum value it can accept using buffer x (provided that it must be larger than the last element). This greedy one will help you check if x will find a valid solution.

• Example: if x = 6, the array is [4,0,9, -2]

   index 0, min is 4 - 6 = -2 index 1, min is 0 - 1 = -1 (as we need to make this greater than -2) index 2, min is 9 - 6 = 3 index 3, min is -2 + 6 = 4 

  So 6 really.

Pseudocode:

  int low = 0; int high = //n times Max absolute value in the array while(low <- high){ int x = (low + high)/2 if(x make the array become sorted) update min result; high = x - 1; else low = x + 1; } 

Answer 4

Here is a solution to O(N) .

For a neighboring pair, say a and b , we need to adjust them if a > b happens. To adjust them in ascending order, we need to find X such that a - X < b + X , which is equivalent to finding X that satisfies a - b < 2X . Therefore, we only need to scan the array once to find these pairs with a > b , and calculate ceil((a - b) / 2) and answer max.

An implementation that works can be written below:

 temp = a[0]; ans = 0 for (i = 1; i < N; i ++) temp = max(temp + 1, a[i]) ans = max(ans, temp - a[i]); return ceil(ans / 2)