Constructing array from given array with some constraints

Question

Given an array of N elements, A[0 .. N - 1], Produce an array B such that:

 B[i] = min (A[i], A[i+1], ..., A[i+K-1]).

(The array B will have exactly (N-k+1) elements.

Time complexity should be better than O(N*k)

I was thinking of using minheap... but heapify will increase the complexity Also brute force is O(n*k)

Also space complexity s'd be less than equal to O(k)

Here's an example

Input: 
A={ 2,1,3,2,5,7,1}, N=7,k=3

Output:
B={1,1,2,2,1}

There's no need to abbreviate "should" to "s'd". You're not doing yourself any favours by making your question hard to read. — YXD, Feb 18 '12 at 17:41
[What have you tried?](http://mattgemmell.com/2008/12/08/what-have-you-tried/) — Carl Norum, Feb 18 '12 at 17:44

score 5 · Accepted Answer · edited May 23 '17 at 09:59

5

To solve the problem, you can use queue in which push_rear(), pop_front() and get_min() are all constant time operations.

Push first k elements from the array A to this queue. Then continue filling the queue from the array A, while popping elements from it and appending minimum values to the array B.

Time complexity is O(N). Space complexity is O(k).

edited May 23 '17 at 09:59

Community

1
1

answered Feb 18 '12 at 18:28

Evgeny Kluev

24,287
7
55
98

score 0 · Answer 2 · answered Feb 18 '12 at 17:48

0

The key of doing this in O(N) instead of O(N*k) is to not calculate the given formula B[i] = min (A[i], A[i+1], ..., A[i+K-1]) for every entry but updating it incrementally.

In every step there is a result-set of K sorted entries.

First step: calculate B[0] from the first K entries and assign the result to B[0].

First incremental step: Calculate B[1] you only add A[i+K] to your result-set and subtract A[0] from your result-set instead of adding K entries all-over again.

Every incremental step: So for every additional index you only have two updates of your result-set.

In total you have linear complexity.

answered Feb 18 '12 at 17:48

Bernd Elkemann

23,242
4
37
66

add or insert ? ...and how are you calculating the minimum ? – user401445 Feb 18 '12 at 17:51
update your page guys. i "added" clarification that "adding" is not "+" but "adding to a result-set" – Bernd Elkemann Feb 18 '12 at 17:56
And how did you manage to insert new item into sorted list of find item in sorted list in O(1)? – OleGG Feb 18 '12 at 18:04
@OleGG not in O(1). Adding an entry into a sorted random-access datastructure is O(log(n)) – Bernd Elkemann Feb 18 '12 at 18:33
1

So in wouldn't be linear as a result, total complexity will be O(n*log(n)) – OleGG Feb 19 '12 at 16:07
It depends on whether the `K` grows with input or whether it is constant. – Bernd Elkemann Feb 19 '12 at 16:24

score 0 · Answer 3 · answered Feb 18 '12 at 17:54

Step 1

Write a (minimum-)priority queue that has a "decrease key" feature. This means that you can go to a node (for example by a pointer), decrease its value and update the heap (priority queue).

The operation decrease_key will be of O(log(k)), k being the number of elements in the priority queue.

Step 2

Consider the following operations:

Add A[i]: This consists of adding A[i] to priority queue, as well as keeping a pointer in, say C[i] to the node created in the priority queue. This is O(log(k))
Remove A[i]: This means go to the node containing A[i] (through C[i]), decrease its value to minus infinity and then remove it from the top of the heap. This is also O(log(k))

Step 3

Initialize the priority queue: Add the first k elements of A into the priority queue. This is O(k*log(k))

Step 4

Fill elements of B like this:

for i = 1 to n-k+1
    B[i] = pQ.top
    Remove A[i]
    Add A[i+k]

This part is O(n*log(k))

Final analysis

The total time order of this algorithm is O(n*log(k)). Space order is O(k). This is k nodes for priority queue and k pointers to those nodes (Array C) which would become O(n) if naively implemented.

your second step will create problem with pointers as due to change in priority they will be shuffled ? ...or can you run your algo on given test case — user401445, Feb 18 '12 at 18:24
Pointers, not indices. Write your queue in such a way that doesn't move the objects, but rather their references. — Shahbaz, Feb 18 '12 at 18:35

score 0 · Answer 4 · edited May 23 '17 at 12:20

From my previous answer here: Finding maximum for every window of size k in an array, which has a list of FOUR different O(n) solutions.

0) An O(n) time solution is possible by combining the two classic interview questions:

Make a stack data-structure (called MaxStack) which supports push, pop and max in O(1) time.

This can be done using two stacks, the second one contains the minimum seen so far.
Model a queue with a stack.

This can done using two stacks. Enqueues go into one stack, and dequeues come from the other.

For this problem, we basically need a queue, which supports enqueue, dequeue and max in O(1) (amortized) time.

We combine the above two, by modelling a queue with two MaxStacks.

To solve the question, we queue k elements, query the max, dequeue, enqueue k+1 th element, query the max etc. This will give you the max for every k sized sub-array.

I believe there are other solutions too.

1)

I believe the queue idea can be simplified. We maintain a queue and a max for every k. We enqueue a new element, and dequeu all elements which are not greater than the new element.

2) Maintain two new arrays which maintain the running max for each block of k, one array for one direction (left to right/right to left).

3) Use a hammer: Preprocess in O(n) time for range maximum queries.

The 1) solution above might be the most optimal.