CODEWITHSUNDEEP
javascriptarraysalgorithmdynamic-programmingsubsequence
Amanda
Amanda

Reputation: 2153

Finding total number of subsequences in an array with consecutive difference = k

In the given array, I am trying to find the total number of subsequences such that:

For example, in an array: [10,13,7,8,14,200, 876, 11], it has 5 subsequences which follow the above condition.

I am trying a bottom-up approach to this. I tried the following, but it does not give all the subsequences and outputs 4 instead of 5.

How can I approach this? I have an intuition that the approach could be similar to Longest Increasing Subsequence, but not sure how.

Upvotes: 1

Views: 2210

Answers (3)

VFX
VFX

Reputation: 496

I have just noticed @Abhinav's answer to optimize the solution to O(K*N) instead of O(N^2) which will work fine for a small K.
But if an optimal solution is required I would suggest an O(N*log2(N)) solution, where finding the sum in the range [x-k,x+k] can be done in log2(N) using Segment Tree or Binary Indexed Tree(Fenwick Tree) where Range Sum Query(RSQ) is a standard operation that these 2 data structures provide.

In case the values inside the initial array are big(like long or double), a data compression can be done with the help of a Map.
In this approach you don't need to worry about K even if it was too big.

Upvotes: 0

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

@VFX has already proposed a O(N^2) solution, but in most cases an optimised algorithm would be preferred. So here's a O(K*N) solution.
Let's say your first element in the subsequence is x. The next element has to be in the range [x-k, x+k]. If you know the number of valid sequences for all values in that range, you can find the answer for the current element in O(K) as well.
More formally, the algorithm would be:

arr = []              // your list
counter = {}          // a dictionary or hashmap to keep count of sequences
counter[arr[-1]] = 1
for i in range (len(arr)-2 to 0):
    curr_element = a[i]
    sequences = 0
    for x in range (curr_element-k to curr_element+k):
        sequences += counter[x]
    counter[curr_element] += sequences

final_answer = counter[arr[0]]

Upvotes: 1

VFX
VFX

Reputation: 496

Let f(i) be the number of subsequences that fulfill the following conditions:

  • Start by A[0]
  • End by A[i]
  • The difference between the consecutive terms is not greater than 3

Then the answer to your problem will be f(A.length()-1).

Here is the code in C++ in a bottom-up approach:

int A[] = {10,13,7,8,14,11};
int f[6];
int n = 6;
    
for (int i=0;i<n;i++) f[i] = 0;
f[0]=1;
for (int i=1;i<n;i++){
  for (int j=0;j<i;j++){
     if (abss(A[i] - A[j]) <= 3)
         f[i] += f[j];
  }
}
cout<<f[n-1]<<endl;//printing the result

Here is the code written in C++ in top-down approach:

int A[] = {10,13,7,8,14,11};
int n = 6;

int memo[6];//initialized with -1s;

int count(int currIndex){
  if (currIndex == n-1) return 1;
  if (memo[currIndex] != -1) return memo[currIndex];
  
  int res = 0;
  for (int i=currIndex+1 ; i<n ; i++){
      if (abss(A[currIndex] - A[i]) <= 3){
            res += count(i);
      }
  }
    
  memo[currIndex] = res;
  return res;
}

And the result will be by calling count at first index like this:

count(0);

Upvotes: 2

Related Questions