CODEWITHSUNDEEP
algorithmdata-structures
smartsn123
smartsn123

Reputation: 113

Finding the minimum from last K elements , after each insertion , where K is not fixed in less than O(n) time

Finding the minimum from last K elements , after each insertion , where K is not fixed:

For example Given Array 10 2 4 1 3

Query K = 3
ans : 1 (minimum of 4 1 3)

Insertion : 5
10 2 4 1 3 5
Query K =2
ans = 3

Insertion 2
10 2 4 1 3 5 2
Query K =4
ans 1

Is there an efficient way for process such queries in less than O(n) time for each query ?

Upvotes: 2

Views: 568

Answers (4)

Saurav Sahu
Saurav Sahu

Reputation: 13934

Create and maintain a min-heap tree of maximum size k. Before every insertion, you need to delete the last kth inserted value from the min-heap tree, and after insertion min-heapify the tree.

Root node value(after insertion) stores the minimum value among last k inserted element all the time.

For each query:

Deletion costs: O(log k)

Insertion costs : O(log k)

Finding minimum costs : O(1)

So, overall time complexity is O(log k) (which is lesser than O(n)).

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

There is a way to solve this problem using a array and Binary search.

First, we process the array, and maintaining a array of index with increasing value. So, for array 10 2 4 1 3, in the queue we have 1 3

Every time we insert one element into array, we try to remove all elements at the end of the array, which are greater than the current element, so when we insert 5 -> array become 1 3 5 , then insert 2 -> queue become 1 2.

So, to query the minimum element in range K, we need to find the element in the array, which is nearest to the start of the queue, and has index in the range of the last K element, which can be easily done using binary search.

So, total time for all insert will be O(n) or in average O(1) per insert and for each query is O(log n).

Pseudo code

int[] q;
int numberOfElement = 0;
for(int i = 0; i < n; i++){
    while(numberOfElement > 0 && data[q[numberOfElement - 1]] >= data[i]){
          numberOfElement--;
    }
    q[numberOfElement++] = i;
}

//Insert at index i:
while(numberOfElement > 0 && data[q[numberOfElement - 1]] >= data[i]){
      numberOfElement--;
}
q[numberOfElement++] = i;

//Query for range K
int start = 0;
int end = numberOfElement - 1;
int result = 0;
while(start <= end){
     int mid = (start + end) >> 1;
     if(q[mid] >= totalElement - K){
          result = mid;
          end = mid - 1;
     } else{
          start = mid + 1;
     }
}

Upvotes: 1

Yerken
Yerken

Reputation: 1942

If you know the number of elements to be inserted beforehand then you can go with @Abhishek Bansal answer (segment tree). Otherwise you can use a BST (binary search tree), for example Treap. You use index of element in the array as a key and the value of a node is its value in the array. So insertion of an element will take O(log(n)) and same complexity for the query (query is a max range query from last_index-k+1 to last_index, both are keys).

Here is the code for treap (it is for maxrange query) but minrange is the same idea: https://ideone.com/M9rnbg

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

I am assuming that you know in the beginning itself the maximum number of elements that shall be inserted so that you can allocate space for them accordingly.

Then a min-segment tree shall work. Initially all elements in the segment tree contain "INT_MAX" value.

As new elements arrive, the corresponding leafs (and their ancestors) get updated. The leaf chosen for updation is as per the position of the element in the stream.

The interval queries can then be easily performed.

Both insertion and query operations shall take O(log n) time.

Upvotes: 3

Related Questions