CODEWITHSUNDEEP
algorithmsubsequence
oflocon
oflocon

Reputation: 11

Counting contigious subsequences in an array with given pair of indices

Given an array of length n, for every index i have a integer xi (xi<=i). I need to count all continous subsequences that include these two indices also there should be no repetition for eg. I have counted the subsequence [1,4] for say (i=4 && x4=0), then if for next (i=5 && x5=1) I should not include the same continous sequence twice. I need to find count of all those subsequences. I tried brute force approach which wasn't sufficient to beat the time.

Can I have any better approach? Possibly O(NLOGN) or less than that?

Upvotes: 0

Views: 410

Answers (1)

Sumeet
Sumeet

Reputation: 8292

The solution is pretty simple and straightforward.

Say we are doing this for index i.

We generate the subsequences by extending our subsequence outside the limits(indices) x[i] and i because the subsequence will always take elements of array from x[i] to i and if we only expand, our subsequnce will always have the indices x[i] and i.

But of course, we will also cover the obvious subsequence from x[i] to i which is the very first subsequence.

EDIT:To avoid duplicates, we must check whether the given combination of left and right boundaries have been tried or not.

For this we will make an adjacency list which will contain

N linked lists.

and all linked lists are initially empty.

Now a given subsequence with corresponding left and right boundaries have not been tried before if and only if

linked list arr[left] does not contain element right.

If linked list arr[left] contains element right then it means the subsequence has been printed before.

First we fix left boundary of our subsequence to be x[i] and then with new left boundary we try all possible new right boundaries which are:

i,i+1,i+2 ....... N-1 , N is equal to length of array a.

Corresponding subsequenes being
if(a[j] linked list does not contain i)
 {
   print the subsequence a[j],a[j+1],......a[i]
   add i to arr[j]
 }
if(a[j] linked list does not contain i+1)
 {
   print the subsequence a[j],a[j+1],.........a[i+1]
   add i+1 to a[j]
 }

and similar if condition before all subsequences given below.      

a[j],a[j+1],...............a[i+2]
. 
.
a[j],a[j+1]..........................a[N-1]

j is x[i] for the above subsequences.

Then we fix left boundary to be x[i]-1 and then with new left boundary we try all possible new right boundaries which are:

i,i+1,i+2 ....... N-1

Corresponding subsequenes being

similar if condition as given above before all subsequences given below.      
and they will be printed if and only if the condition is true.

a[j],a[j+1],.........a[i]
a[j],a[j+1],...............a[i+1]
. 
.
a[j],a[j+1]..........................a[N-1]

j is x[i]-1 for the above subsequences.

We do this till j becomes 0 and that will be the last iteration.

Now coming to the efficiency of this algorithm, because at every step I am generating a new subsequence,and none of the steps go wasted in producing a subsequence that does not include both indices so I think it is pretty much efficient.

Upvotes: 1

Related Questions