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! 