Given an array of N numbers,find the number of sequences of all lengths having the range of R?

Question

This is a follow up question to Given a sequence of N numbers ,extract number of sequences of length K having range less than R?

I basically need a vector v as an answer of size N such that V[i] denotes number of sequences of length i which have range <=R.

not sure that "range less than R" means. All elements in the sequence are less than R? — Zane, Oct 14 '12 at 14:21
@Zane: I would say it's talking about the spread of the sequence (`max(S) - min(S)`). — Matthieu M., Oct 14 '12 at 14:29

score 1 · Accepted Answer · answered Oct 14 '12 at 14:46

Traditionally, in recursive solutions, you would compute the solution for K = 0, K = 1, and then find some kind of recurrence relation between subsequent elements to avoid recomputing the solution from scratch each time.

However here I believe that maybe attacking the problem from the other side would be interesting, because of the property of the spread:

Given a sequence of spread R (or less), any subsequence has a spread inferior to R as well

Therefore, I would first establish a list of the longest subsequences of spread R beginning at each index. Let's call this list M, and have M[i] = j where j is the higher index in S (the original sequence) for which S[j] - S[i] <= R. This is going to be O(N).

Now, for any i, the number of sequences of length K starting at i is either 0 or 1, and this depends whether K is greater than M[i] - i or not. A simple linear pass over M (from 0 to N-K) gives us the answer. This is once again O(N).

So, if we call V the resulting vector, with V[k] denoting the number of subsequences of length K in S with spread inferior to R, then we can do it in a single iteration over M:

for i in [0, len(M)]:
    for k in [0, M[i] - i]:
        ++V[k]

The algorithm is simple, however the number of updates can be rather daunting. In the worst case, supposing than M[i] - i equals N - i, it is O(N*N) complexity. You would need a better data structure (probably an adaptation of a Fenwick Tree) to use this algorithm an lower the cost of computing those numbers.

: Although,it seems a brilliant algorithm,however,o(n*n) is too slow for my purpose. — user1724072, Oct 14 '12 at 16:16

score 0 · Answer 2 · answered Oct 14 '12 at 14:18

If you are looking for contiguous sequences, try doing it recursively : The K-length subsequences set having a range inferior than R are included in the (K-1)-length subsequences set.

At K=0, you have N solutions. Each time you increase K, you append (resp. prepend) the next (resp.previous) element, check if it the range is inferior to R, and either store it in a set (look for duplicates !) or discard it depending on the result.

If think the complexity of this algorithm is O(n*n) in the worst-case scenario, though it may be better on average.

score 0 · Answer 3 · edited May 23 '17 at 12:12

Start with a simpler problem: count the maximal length of sequences, starting at each index and having the range, equal to R.

To do this, let first pointer point to the first element of the array. Increase second pointer (also starting from the first element of the array) while sequence between pointers has the range, less or equal to R. Push every array element, passed by second pointer, to min-max-queue, made of a pair of mix-max-stacks, described in this answer. When difference between max and min values, reported by min-max-queue exceeds R, stop increasing second pointer, increment V[ptr2-ptr1], increment first pointer (removing element, pointed by it, from min-max-queue), and continue increasing second pointer (keeping range under control).

When second pointer leaves bounds of the array, increment V[N-ptr1] for all remaining ptr1 (corresponding ranges may be less or equal to R). To add all other ranges, that are less than R, compute cumulative sum of array V[], starting from its end.

Both time and space complexities are O(N).

Pseudo-code:

p1 = p2 = 0;
do {
  do {
    min_max_queue.push(a[p2]);
    ++p2;
  } while (p2 < N && min_max_queue.range() <= R);

  if (p2 < N) {
    ++v[p2 - p1 - 1];
    min_max_queue.pop();
    ++p1;
  }
} while (p2 < N);

for (i = 1; i <= N-p1; ++i) {
  ++v[i];
}

sum = 0;
for (j = N; j > 0; --j) {
  value = v[j];
  v[j] += sum;
  sum += value;
}

: Last paragraph is not clear,can you add pseudo code to explain it further. — user1724072, Oct 14 '12 at 16:44

score 0 · Answer 4 · answered Oct 14 '12 at 16:56

I think Matthieu has the right answer when looking for all sequences with spread R.

As you are only looking for sequences of length K, you can do a little better. Instead of looking at the maximum sequence starting at i, just look at the sequence of length K starting at i, and see if it has range R or not. Do this for every i, and you have all sequences of length K with spread R.

You don't need to go through the whole list, as the latest start point for a sequence of length K is n-K+1. So complexity is something like (n-K+1)*K = n*K - K*K + K. For K=1 this is n, and for K=n it is n. For K=n/2 it is n*n/2 - n*n/4 + n/2 = n*n/2 + n/2, which I think is the maximum. So while this is still O(n*n), for most values of K you get a little better.

Given an array of N numbers,find the number of sequences of all lengths having the range of R?

4 Answers4