Divide Array Into Increasing Sequences

Moderate

0/80

Average time to solve is 50m

Contributed by

0 upvote

Asked in companies

Problem statement

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’.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
7 3
1 2 2 3 3 4 4

Sample Output 1:

YES

Explanation for sample input 1:

We can divide the original array into [1,2,3,4] and [2,3,4] and we can see both of the new arrays have length >= 3.

Sample Input 2:

Sample Output 2:

NO
YES

Explanation for sample input 2:

For test case 1, It can be proved that no combination of subsequences fulfills the required conditions. Hence ‘NO’.

For test case 2, The original array itself is a valid answer, Hence ‘YES’.

Hint 1

Hint 2

How does the frequency of numbers affect the answer?

Approaches (2)

Approach 1

Approach 2

Greedy Approach

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'.

Time Complexity

O(N*log(N)), where N is the size of the array ‘NUMS’.

We need to traverse the array while inserting it into the map, which has time complexity O(N), and insertion into the map takes O(log(N)) time. Hence net time complexity: O(Nlog(N)).

Space Complexity

O(N), where N is the size of the array ‘NUMS’.

In the worst case, when all the elements of NUMS are different, then there are N elements in the map, hence space complexity is O(N).

(100% EXP penalty)

Divide Array Into Increasing Sequences

Console