2

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?

Abbas
  • 14,186
  • 6
  • 41
  • 72
Luv
  • 5,381
  • 9
  • 48
  • 61

1 Answers1

1

We can do better if in the algorithm from OP we change expensive "heapify" procedure to much cheaper "upheap" or "downheap". This gives O(n * log(k)) time complexity.

Or, if we iterate through input array and put each element to the min-queue of size 'k', we can do it in O(n) time. Min-queue is a queue that can perform find-min in O(1) time. It may be implemented as a pair of min-stacks. See this answer for details.

Community
  • 1
  • 1
Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
  • But at the time of deletion we have to search for the element hence would be O(k) not log(k) here. That's why i stated the worst case complexity would be O( (n-k+1)*k ) + O(k) – Luv Jun 22 '12 at 15:56
  • 1
    @Luv: there is no need to search for deleted element if we keep track of each heap element's position. – Evgeny Kluev Jun 22 '12 at 16:02