1

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?

SexyBeast
  • 7,913
  • 28
  • 108
  • 196

1 Answers1

1

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]:
    D.popLast()

  D.pushBack(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.

IVlad
  • 43,099
  • 13
  • 111
  • 179
  • Should `i` range from 0 to `N-1` or upto `N-W`? – SexyBeast Sep 26 '12 at 09: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 09: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? – SexyBeast Sep 26 '12 at 09: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 09:52
  • Can you please elaborate a little more? What does `popfirst`, `poplast` and `pushback` do, and how it maintains the order? – SexyBeast Sep 26 '12 at 09:53
  • @Cupidvogel - I explained some more. I strongly suggest you run it on paper though, it was difficult for me to imagine how it works when I first learned about this too. It's quite elusive until you get the hang of it I think. – IVlad Sep 26 '12 at 09:58
  • Exactly. I am doing it right now! Another question, can you suggest what can be done, if, instead of specifying a window length (like `W` here) and asking for all such subsequences of that length, it is required to find such a subsequence of the maximum possible length? – SexyBeast Sep 26 '12 at 10:04
  • Okay, so inside the outer `for` loop, I will use the `D` dequeue once to find the minimum element in the current window, then use another similar dequeue to find the maximum element, and then check `max-min+1 = W`, right? – SexyBeast Sep 26 '12 at 10:19
  • @Cupidvogel - I'm not sure what you mean by no window length being specified. What requirement do you have in that case? Since the entire array is a permutation, then the entire array would be the subsequence of maximum possible length, wouldn't it? As for your second question, yes, you can use another similar deque to find the maximum. – IVlad Sep 26 '12 at 10:38
  • In that question, the entire array is not a permutation, there may be repeating numbers. – SexyBeast Sep 26 '12 at 10:39
  • @Cupidvogel - and the requirement is the same, as in to find the longest subarray that is a permutation? Since repeating numbers are allowed, the `max - min` trick won't work there. I can't think of anything off the top of my head. Please post it as another question so others can contribute too. – IVlad Sep 26 '12 at 10:47
  • Exactly. That max-min trick is bugging me too. I will post it as a new question. Thanks a ton! This problem had me hooked for one whole day! – SexyBeast Sep 26 '12 at 10:51