CODEWITHSUNDEEP
algorithm
user401445
user401445

Reputation: 1014

Constructing array from given array with some constraints

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}

Upvotes: 1

Views: 1928

Answers (4)

Evgeny Kluev
Evgeny Kluev

Reputation: 24657

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).

Upvotes: 5

user127.0.0.1
user127.0.0.1

Reputation: 1337

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.

Upvotes: 0

Shahbaz
Shahbaz

Reputation: 47553

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.

Upvotes: 0

Bernd Elkemann
Bernd Elkemann

Reputation: 23550

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.

Upvotes: 0

Related Questions