Decreasing Subsequences

Moderate
0/80
9 upvotes
Asked in companies
IBMPegasystemsGoogle inc

Problem statement

Ninja is fond of sequences. He has a set of numbers and wants to make minimum decreasing subsequences such that all numbers are part of exactly one subsequence. Can you help Ninja with this challenge?

You are given an array ‘ARR’ having ‘N’ elements.Your task is to divide all ‘N’ elements of the array into a minimum number of strictly decreasing subsequences. Each number can be in one subsequence only. Find the minimum number of such strictly decreasing subsequences.

For Example 
If 'ARR' is [4,2,1,3] ,it can be splitted into two subsequences as [4,2,1] , [3] or [4,3],[2,1].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T’ , denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of elements in ‘ARR’.

The next line of each test case has ‘N’ integers corresponding to the elements of 'ARR’.
Output Format: 
For each test case, print a single integer corresponding to the minimum number of subsequences.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 2000
1 <= 'ARR'[i]   <= 10^6

Time limit: 1 sec
Sample Input 1:
2
4
4 2 1 3
5
2 3 4 5 1
Sample Output 1:
2
4
Explanation of sample input 1:
For the first test case,
The subsequences can be [4,2,1] , [3] or [4,3] ,[2,1].
 Hence the minimum number of subsequences is 2.

For the second test case, the possible subsets are:
 The subsequences can be [2] , [3] , [4] , [5,1].
 Hence the minimum number of subsequences is 4.
Sample Input 2:
2
2 
2 1 
4 
3 2 1 4
Sample Output 2:
1
2
Hint

Can you greedily pick the elements for the subsequence?

Approaches (2)
Greedy Approach

In this approach, we will prepare an array ‘USED ’ as USED[i] will state that whether any element can be inserted after ARR[i] or not. We will also maintain ‘ANS’ to store the number of subsequences. For each element, we will try also values left to that element and greedily pick the element whose value is just less than ARR[i]. If no such element is found, we will create a new subsequence and increase the value of ‘ANS’ by 1. 

 

Algorithm:

  • Declare an array ‘USED’ to store whether we can add any element next to ARR[i] or not.
  • Declare a variable ‘ANS’ to store the number of subsequences.
  • For each index ‘i’ in range 0 to ‘N-1’,do the following:
    • Set USED[i] as 1.
  • For each index ‘i’ in range 0 to ‘N-1’, do the following:
    • Set ‘INDEX’ as -1.
    • For each index ‘j’ in range 0 to ‘i-1’,do the following:
      • If ‘USED[j]’ == 1 and ‘ARR[j]’ > ‘ARR[i]’:
        • If ‘INDEX’ == -1
          • Set ‘INDEX’ as ‘j’.
        • Else, if difference of ‘ARR[i]’ and ‘ARR[j]’ is less than ‘ARR[i]’ and ‘ARR[INDEX]’:
          • Set ‘INDEX’ as ‘j’.
    • If ‘INDEX’ == -1 ,no suitable element found.We will put ‘ARR[i]’ into a new subsequence:
      • Set ‘ANS’ as ‘ANS +1’.
    • Else
      • Set ‘USED[INDEX]’ as 0.
  • Return ‘ANS’.
Time Complexity

O(N^2), where ‘N’ is the number of elements in 'ARR'.

 

In this approach, we are iterating over all array elements and for finding the suitable index we are iterating all the elements to its left. So the total time taken is (N*N). Hence the overall time complexity is O(N^2).

Space Complexity

O(N), where ‘N’ is the number of elements in 'ARR'.

 

In this approach, we are using an array ‘USED’ of size ‘N’. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Decreasing Subsequences
Full screen
Console