Construct an array from an existing array

Given an array of integers A[1...n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ..., A[i+K-1]), where K will be given.

Array B will have N-K+1 elements.

We can solve the problem using min-heaps Construct min-heap for k elements - O(k) For every next element delete the first element and insert the new element and heapify Hence Worst Case Time - O( (n-k+1)*k ) + O(k) Space - O(k)

Can we do it better?

• I would start at the end of B and go "backwards" toward the beginning. – NominSim Jun 22 '12 at 18:11

Here is my first thought, it may not be the best solution, but here it goes.

Take a look at the diagram below for K=10, N=15

You can see that when calculating each value of B, you need use the elements of A[S], A[S+1],..., A[E]. So you could do this calculation and store it first, then with each iteration use the stored value with the other A values, hence saving some iterations.

For example,

B = Min(savedvalue, a[2...4],a[10...11])

This saves 3 comparisons with each iteration. 