Construct an array with from an existing array

Question

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?

Probably this will help: stackoverflow.com/a/11044634/1400768 — nhahtdh
– nhahtdh, Commented Jun 22, 2012 at 15:51

Community · Accepted Answer · 2017-05-23 11:56:20Z

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.

edited May 23, 2017 at 11:56

CommunityBot

11 silver badge

answered Jun 22, 2012 at 15:49

Evgeny Kluev

24.7k7 gold badges58 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Luv Over a year ago

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)

Evgeny Kluev Over a year ago

@Luv: there is no need to search for deleted element if we keep track of each heap element's position.

Collectives™ on Stack Overflow

Construct an array with from an existing array

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related