-4

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
3

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[2] = Min(savedvalue, a[2...4],a[10...11])

This saves 3 comparisons with each iteration.

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.