

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

The problem is this, given an array of length say N, we have to find all subsequences of length W such that those W elements, when sorted, forms an arithmetic progression with interval 1. So for an array like [1,4,6,3,5,2,7,9], and W as 5, the slice [4,6,3,5,2] can be regarded as one such subsequence, since, when sorted, it yields [2,3,4,5,6], an A.P with common difference 1.

The immediate solution which comes to the mind is to have a sliding window, for each new element, pop the old one, push the new one, sort the window, and if for that window, window[w-1] - window[0] + 1 = w, then it is such a subsequence. However, it takes O(NlogN) time, whereas the solution at Codechef proposes a O(N) time algorithm that uses double-ended queue. I am having difficulty in understanding the algorithm, what is being pushed and popped, and why so, and how it maintains the window in sorted order without the need to resort with each new element. Can anybody explain it?

share|improve this question
Can the array contain duplicate elements? – amit Sep 26 '12 at 9:20
No no, all are unique. In fact, the N element array is a permutation of 1..N-1. – AttitudeMonger Sep 26 '12 at 9:23
An N element array cannot be a permutation of 1..N-1, for example a 3-element array cannot be a permutation of {1,2}. – High Performance Mark Sep 26 '12 at 9:31
Sorry, I meant 1..N! Confused the permutation with the range of index! – AttitudeMonger Sep 26 '12 at 9:44
If the N element array is a permutation of 1..N, then doesn't the whole array qualify? – cHao Sep 26 '12 at 17:54
up vote 1 down vote accepted

You are correct in observing that a segment is valid if max(segment) - min(segment) + 1 = W. So, the problem reduces to finding the min and max of all length W segments in O(N).

For this, we can use a deque D. Suppose we want to find the min. We will store the indexes of elements in D, assuming 0-based indexing. Let A be the original array.

for i = 0 to N - 1:
  if D.first() == i - W:
    D.popFirst() <- this means that the element is too old, 
                    so we no longer care about it
  while not D.empty() and A[ D.last() ] >= A[i]:


For each i, this will give you the minimum in [i - W + 1, i] as the element at index D.first().

popFirst() removes the first element from D. We have to do this when the first element in D is more than W steps away from i, because it will not contribute to the minimum in the interval above.

popLast() removes the last element from D. We do this to maintain the sorted order: if the last element in D is the index of an element larger than A[i], then adding i at the end of D would break the order. So we have to keep removing the last element to ensure that D stays sorted.

pushBack() adds an element at the end of D. After adding it, D will definitely remain sorted.

This is O(1) (to find a min, the above pseudocode is O(n)) because each element will be pushed and popped to / from D at most once.

This works because D will always be a sliding window of indexes sorted by their associated value in A. When we are at an element that would break this order, we can pop elements from D (the sliding window) until the order is restored. Since the new element is smaller than those we are popping, there is no way those can contribute to a solution.

Note that you can implement this even without the methods I used by keeping two pointers associated with D: start and end. Then make D an array of length N and you are done.

share|improve this answer
Should i range from 0 to N-1 or upto N-W? – AttitudeMonger Sep 26 '12 at 9:46
@Cupidvogel - up to N - 1, because for each i, this will give you the minimum in [i - W + 1, i]. If you go only up to N - W, you will miss minimums. – IVlad Sep 26 '12 at 9:48
Plus I couldn't understand your code. What does D contain? Indices of elements before i? In what order, order of increasing value for each index? – AttitudeMonger Sep 26 '12 at 9:51
@Cupidvogel - yes to both. The while loops ensures that the order is maintained. Try running through it on paper on an example to better see how and why it works. – IVlad Sep 26 '12 at 9:52
Can you please elaborate a little more? What does popfirst, poplast and pushback do, and how it maintains the order? – AttitudeMonger Sep 26 '12 at 9:53

Your Answer


