Sliding Range Query

As the name depicts we will be given a problem and we will compute results for the range-queries.
We can assume that there is a range [Left,Right] in each query and we need to give the answer to the problem for the given range given in each query.

Now what could be the problem, it could be the minimum value, maximum value, sum or anything typical.For this post let us assume we need to find the minimum value.Now let us rephrase the problem : Given an array of numbers find for each range-query the minimum value in the range.
There is also a condition in our favor that these ranges are in increasing order.Example if range-queries are [L1,R1], [L2,R2], [L3,R3]..., then L1<=L2<=L3<=... and R1<=R2<=R3....

Now let us see how to solve the problem.

The Brute force way : O(n^2).

For each range traverse the array store the min till now in a variable and return it. For each query the complexity will be O(n) and for n queries O(n^2).

The Smart way O(n log n).

We can use a segment tree, Binary Indexed Tree or RMQ etc and get the answer for each query in O(logn) time.So overall complexity for n queries is O(n log n).

The Genius way O(n).

Due to the favorable condition of ranges we can use a Deque and solve our problem in linear time.Lets see how to do that.

Let us write down some of the facts that we can observe :

1) Since L and R will always increase we never need to come back, once we have moved forward.
2) When R increase and a number is smaller that current min value, our current min will change else it will not effect our current min.i.e R can only decrease the min, never increase it.
3) When L increase it may be possible our current min is left behind hence our current min will increase else it will remain same.i.e L can only increase the min, never decrease it.

Now how can we use these facts to our advantage, lets see how.

Deque, if someone is confused is a data structure where we can add as well as remove elements from both the ends start as well as last.

So we need to use a deque for adding and removing elements per query such that overall complexity remains O(2*n).i.e each element will be added and removed at most once.

Now here is how we will do our magic :
1) For each R, if the new element is bigger than last element in deque add the element in deque, else remove all elements from deque which are bigger than new element from the end.
2) For each L, if first element of deque is is the element to be removed, remove the element from deque.

Now what will be the output : tadaa, The leftmost element of Deque.

Here is pseudocode in java to do the same :

   Deque<Integer> deque=new LinkedList<Integer>();

int l=0,r=-1;

while(Q-->0)

{

str=in.readLine().split(" ");

int L=Integer.parseInt(str[0])-1;

int R=Integer.parseInt(str[1])-1;

while(l<L)

{

if((!deque.isEmpty())&&deque.getFirst()==arr[l]) deque.removeFirst();

l++;

}

while(R>r)

{

r++;

if((!deque.isEmpty())&&deque.getLast()<=arr[r]) deque.addLast(arr[r]);

else if((!deque.isEmpty()))

{

while((!deque.isEmpty())&&deque.getLast()>arr[r]) deque.removeLast();

}

deque.addLast(arr[r]);

}

out.write(deque.getFirst()+"\n");

}

Hope you enjoy it !!!