1

There is an array of integers ,I have to find the number of sequences of K length having range (max - min of the subsequence) less than equal to R .Is there a relation between Number of sequences of length k and number of sequences of length K-1 ? I am trying to solve a practice question on SPOJ. I don't want the full solution,just point me in the right direction /suggestion/hint.

I was thinking of a deque like structure to maintain min and max elements of the array upto a certain index.However,when k is closer to n ,this would become close to o(n*n) which is too slow ,I am ideally looking at O(n) solution or O(n * log n) solution. It would be best if I can calculate the required value for K=1 to K=N using a recursion/iteration relation as the same answer maybe required again

IVlad
  • 43,099
  • 13
  • 111
  • 179
user1724072
  • 331
  • 1
  • 3
  • 8

1 Answers1

0

This is a perfect application for a deque. See my answer here.

You should be able to adapt that for your needs with almost no changes, giving you an O(N) solution.

Community
  • 1
  • 1
IVlad
  • 43,099
  • 13
  • 111
  • 179
  • :What if I have to calculate this value from K=1 to K=N ,what will be the complexity in that case.And what algorithm can I use ? – user1724072 Oct 14 '12 at 13:29
  • @user1724072 If you apply the same algorithm for each `K`, it will be `O(n^2)`, because the algorithm for a fixed `K` is `O(N)`. Do you want to count the number of substrings of length `1, 2, ..., N` with range `<= R`? That is a different question, I suggest you open another question for that problem. – IVlad Oct 14 '12 at 13:33