2

You are given an array of N positive integers, A1,A2,…,An. You have to answer Q queries. Each query consists of two integers L and K. For each query I have to tell the Kth element which is larger than or equal to L in the array when all such elements are listed according to increasing order of their indices.

Example A = 22,44,12,16,14,88,25,49

Query 1: L = 3 K = 4 Since all elements are greater than 3. So we list the whole array i.e. 22,44,12,16,14,88,25,49. 4th element among these elements is 16

Query 2: L = 19 K = 5 Listed elements 22,44,88,25,49. 5th element among these is 49.

What I have done: for each query iterate over the whole array and check the Kth element which is larger than or equal to L. Complexity : O(Q*N)

What I require: O(Q*logN) complexity.

Constraints : 1<=Q<=10^5 1<=N<=10^5 1<=Ai<=10^5

Improve this question

1 Answer 1

Reset to default
2

One possible way to solve this task is to use immutable binary (RB) tree.

First you need to sort your array in ascending order, storing original indices of the elements next to the elements.

Traverse array in reverse (descending) order, adding elements one by one to immutable binary tree. Key in the tree is original index of the element. Tree is immutable, so by adding element I mean constructing new tree with added element. Save the tree created on each step near the corresponding element (the element that was last added to the tree).

Having these trees constructed for each element you can do your queries in O(log N) time.

Query: First, perform a binary search for L in sorted array (O(log N)) for the element that is bigger than L. You'll find the element and corresponding tree of indices of the elements that are bigger than L. In this tree you can find K-th largest index in O(log N) time.

The whole algorithm will take O(N log N + Q log N) time. I don't believe that it is possible to do better (as sorting the original array seems to be inevitable).

The key of this approach is using immutable binary tree. This structure shares the properties of mutable binary tree, such as insertion and search in O(log N), while staying immutable. When you add element to such tree, the previous version of the tree is preserved, only nodes that are different from the previous "version" of the tree are recreated. Usually it's O(log N) nodes. Thus creating N trees from elements of your array will require O(N log N) time and O(N log N) space.

You can use immutable RB tree implementation in Scala as the reference.

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

12 Comments

I have already followed this approach. I used map in C++ to store maps for all the elements. Maps are internally represented as BST's. How ever this approach is too memory intensive and is not what i require. In the worst case the memory used in this approach is O(N^2) and not O(N log N) as you suggest which is 10^10 and gives me a runtime error
The first tree will have 1 node . The second tree will have two nodes and so on till the last tree has N nodes. Total space = 1+2+3....N = N^2. Te additional space used at each update is 1 node.
I was thinking of a similar solution till I realized the space complexity is in fact N^2. Given that, time complexity can't be smaller as you'd have to fill this helper structure first and that itself is N^2.
@Aivean Let me have a look :) Thanks for the patience
If you can batch the queries, then you could sort them so as to answer them in descending order of L. Then (assuming that you also sort A) you can use a less exotic data structure, such as a skip list annotated with information about the number of elements <= the current point, to answer each query, putting more and more elements back in as L decreases. Immutable data structures look like cool technology, though.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.