Saturday, March 16, 2013

SPOJ ARRAYSUB


SPOJ Problem Set (Classical) 10582. Subarrays

This was also one of the problems I was asked on my recent interview with Google. Problem is a simple one for segment tree based algorithm. The solution basically requires us to maintain a Range Maximum Query (RMQ) algorithm, and I implemented this using segment tree.

Given, there are N items and a window of size K, we have to find the maximum item in each K sized window. First, we insert the first K items in the RMQ, so the segment tree root now knows the maximum item at this stage. Now if you observe you will see, for the (k+1)th item, 1st item will be removed from the tree and (k+1)th item will be inserted. This can be done by inserting (k+1)th item at the position of 1st item. Because for (k+1)th item, 1st item is in the oldest position. And clearly, for each of the next items, we can just insert it in the current oldest position on the K sized window. so (k+1) will be inserted at index 1, (k+2) at 2, (k+3) at 3 ... (2k) at k, (2k+1) at 1, (2k+2) at 2 and so on. So all we need is to keep inserting the items in the RMQ in a circular fashion and each time taking the updated range maximum value.

So, basically the structure of the code is:

for(i = 0; i < k; i++) insert(root, 0, k-1, item[i]);
output Tree[root];
for(; i < n; i++) {
    insert(root, 0, k-1, item[i % k]);
    output Tree[root];
}
// considering item indexes to be 0 based in code
// insert is the function that inserts an item on a specific index in the RMQ tree
So, once you write down the RMQ function insert, you are pretty much done with it. Happy coding!


5 comments:

  1. It can be solved also in O(N) using monotonic queue.

    ReplyDelete
    Replies
    1. yah, I also solved this using a double ended queue, if current item is smaller than q head, then keep popping until you find some item larger than current one and then push the current value, other wise push it at the end of the queue. at any time queue head contains the required value.

      Delete
    2. Exactly :D , good luck with your interviews!!

      Delete
  2. Another solution maybe Sliding Window RMQ, isn't it ? BTW, is Sliding RMQ similar to monotonic queue ?

    ReplyDelete
  3. Yap, I mentioned the linear solution in my second comment to George Christoglou above. Its probably the same as the monotonic queue.

    ReplyDelete