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
  • 13,778
  • 6
  • 40
  • 69
Luv
  • 5,161
  • 8
  • 44
  • 58

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,007
  • 7
  • 53
  • 94
  • 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