Construct an array from an existing array
- by Luv
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?
