Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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