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?
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.
