The Subarray with the Minimum Peak

Question

Let X[1:n]: be an array of real numbers, and let L be a given fixed positive integer. An L-subarray is any sequence of consecutive elements of the array X, such as X[k: k + L − 1], and is identified simply by the index k of the first element of the subarray. The array has (n  − L + 1) L-subarrays. The peak of an L-subarray is the maximum value in that subarray.

Give a divide-and-conquer algorithm that takes as input an array X[1:n] and a positive integer L ≤ n, and returns the L-subarray with the smallest peak. Analyze the time complexity of your algorithm.

[We observe that a simple brute force O(NL) time algorithm is straightforward, simply evaluate each L-subarray.  Our interest is in something like O(N log N) or O(N log L) time algorithm.]

Answer 1

 A O(N) Dynamic Programming way :

Divide array by N/L blocks, last one maybe less than L.

For example, X=[2,1,3,4,6,3,8,9,10,12,56] ,L= 4

Then after divide, X= 2,1,3,4 | 6,3,8,9 | 10,12,56 

notation: 

Right_peak(i): peak value of all the elements on the right hand of X[i] (include X[i]) in the same block.

Left_peak(i): peak value of all the elements on the left hand of X[i] (include X[i]) in the same block.

Then, the peak(i), value of subarray X[i : i+L-1] should be max{ Right_peak(i), Left_peak(i+L-1) }

Proof:

 if i is the first position of a block, then the Right_peak(i) equal to Left_peak(i+L-1) is the peak value of this block, Also the subarray X[i : i+L-1].

If i is not the first position of a block, then the Right_peak(i) is the peak value of the rest of the block. The Left_peak(i+L-1) is the peak value of the beginning elements of the next block. Combined together they are the subarray X[i: i+L-1]. So the maximum of the two parts is the peak value of the subarray.

Using the above example:

X= 2,1,3,4 | 6,3,8,9 | 10,12,56 

We can find the Left_Peak value while traversing from left to right of the current block. ( At each end of the block the Left_peak value should reset to 0.)   O(N)

Left_peak[]= 2,2,3,4| 6,6,8,9 | 10,12,56

We can find the Right_peak value while traversing from right to left of the current block. ( At each end of the block the Left_peak value should reset to 0.). O(N)

Right_peak[]= 4,4,4,4 | 9,9,9,9 | 56,56,56

Then peak(i)=max{ Right_peak(i), Left_peak(i+L-1) }

peak[]=[4,6,6,8,9,10,12,56]

Simply find the minimux of peak[] and output the index of it.  O(N)

The subarray is X[ index: index+L-1]

which is X[1: 4]

 

Comments

Sorry the word “minimux” should be the minimum

Answer 2

My first solution :  

Step 1 : Initialize a maximum heap H by first L elements in the array  ( O(L log L) )

Step 2: Store the value of the top element in H, as a Peak ( O(1) )

Step 3: Delete the one element whose index is smallest in the array from  H. ( O(1) )

Step 4: Add next element from the array to the H.  ( O(log L) )

Step 5: Replace the Minimum Peak ( O(1) )

Step 6: Repeat Step 3-5 until there is no new element. ( O((n - L) log L) )

Therefore, total time complexity will be O(n log L). However, no matter this solution is right or not, it is not a D&C method. 

If a D&C method used, it's a hard to merge sub-results. Merging may need about O(L²) by brute force each time, and O(NL) totally.  I will appreciate if someone could tell me whether my solution is right, or could offer any better solution in any method. 

Comments

I am not sure Step 3 is an O(1) time operation.  How do you delete a selected element from a max-heap?  We can delete the largest element in O(log L) time, but we don't know where a random element might be.

---

Sorry, that's my fault. I'll edit it.

---

not that hard, but the merge part is a little complex. It can be O(n) and cannot be better

Answer 3

divide

find the right peak left peak and peak

merge

Comments

How do you merge, and how much time does it take?