Last Updated: 20 Apr, 2021
Divide Array Into Increasing Sequences
Moderate
Asked in companies
You are given a non-decreasing array of positive integers, ‘NUMS’, and provided with an integer ‘K’. Your take is to find out whether it is possible to divide ‘NUMS’ into increasing subsequences such that each of their lengths is at least ‘K’.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first line of each test case contains two positive integers, ‘N’ denoting the size of the array ‘NUMS’ and ‘K’.
The second line of each test case contains ‘N’ space-separated positive integers denoting the array elements.
Output Format:
For each test case, print ‘YES’ if it is possible to create the required subsequences, otherwise print ‘NO’.
The output of 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’ <= 10^6
1 <= ‘K’ <= ‘N’
1 <= ‘NUMS[i]’ <= 10^6
Where ‘NUMS[i]’ is the i-th element of the array ‘NUMS’.
Time Limit: 1 sec
Approaches
- Suppose the frequency of a number 'NUM' in 'NUMS' is 'FREQ'. It is obvious that for the subsequences to be increasing there has to be at least a 'FREQ' number of subsequences, otherwise, in some number of subsequences, there will be more than 1 instance of 'NUM', thus making it non-increasing.
- Therefore, it is also true to say that out of all the frequencies from 'NUMS', if the maximum frequency is 'MAX_FREQ', then the size of 'NUMS', has to be at least 'MAX_FREQ'*'K'.
- Therefore if 'MAX_FREQ'*'K' <= ‘N’, the answer exists otherwise it does not.
- To find the frequency of the numbers, keep a map, and for every element of 'NUMS' increment by 1 at that number’s position. Later on, traverse the map to find the value of 'MAX_FREQ'.
- This approach is an extension of the previous approach. Previously we were keeping a map in order to find the frequencies of the elements, instead, we can use the property that ‘NUMS’ is given to us in sorted order.
- Keep a variable 'MAX_FREQ', which is initially 0.
- Traverse the array NUMS. Suppose NUMS[i] is the current element. Variable 'CUR_FREQ' denotes the frequency of the current element.
- If ‘NUMS[i]’ == ‘NUMS[i-1]’ increment 'CUR_FREQ' by 1.
- Otherwise, make 'MAX_FREQ' to be equal to the max of 'CUR_FREQ' and 'MAX_FREQ'. make 'CUR_FREQ' 0 again.
- 'MAX_FREQ' is the maximum frequency we want. Proceed now as discussed in the previous approach.