Last Updated: 29 Nov, 2021
Minimum Sorted Groups
Hard
Asked in companies
You are given an array ‘ARR’ containing ‘N’ integers.
You have a simple task, you need to split the elements of this array into different groups, inside each group the relative order between elements must be maintained.
You need to find the minimum number of groups that are required to be formed such that elements inside each group are sorted in ascending order.
For Example :
If ‘N’ = 7 and ‘ARR’ = { 1, 5, 2, 3, 4, 6, 7 }
Then, we can split the array elements into two groups: { 1, 2, 3, 4 } and { 5, 6, 7 }, this splitting is valid as it maintains the relative ordering of the elements of the original array and after splitting all the groups contain elements in sorted order. Therefore we will print 2.
Note that a group like { 1, 2, 3, 5 } can’t be formed as it doesn’t have relative ordering the same as the input array.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’, denoting the size of the array.
The second line of each test case contains 'N' integers ‘ARR’, denoting the array elements.
Output Format :
For each test case, print the count of minimum groups that need to be formed.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 5000
-10^9 ≤ ARR[i] ≤ 10^9
Time limit: 1 sec
Approaches
If we are somehow able to keep the track of the largest element in each group then to insert a new array element in one of the groups, we can greedily select a group whose largest element is as close as the new element to be inserted and also it must be smaller than or equal to the new element, a standard lowe_bound function available in multiple languages comes in handy to directly do this. This greedy method of selecting the group for our current element works perfectly fine as we are just increasing the lower limit of a particular (as each group is sorted) which is much better than making a new group, and for a new element, if their none of the last ending element of each group is smaller or equal to the new element, then we will assign this new element to a new group.
A data structure like multiset in C++ comes in handy to implement all the discussed features, it will allow us to insert multiple elements with equal values (as two groups might have equal ending elements) also it supports the lowe_bound function which directly tells us the greater than or equal to element for any new number to be inserted. The size of this multiset denotes the number of groups formed so far.
The steps are as follows :
- Initialize a multiset ‘lastElements’. The elements of this multiset correspond to the last element of each group created.
- Iterate the array elements.
- Use the lower_bound to find the element greater than or equal that ARR[i] in ‘lastElements’.
- If the corresponding element is equal to the value of ARR[i], then move on to the next array element, as Arr[i] will be inserted in the group where the last element had the same value as ARR[i] and nothing needs to be updated in the multiset.
- If the value equal to ARR[i] is not present in the multiset, then check:
- If the lower bound element corresponds to the first element in the multiset then we will need to create a new group, therefore insert the value ARR[i] in ‘lastElements’.
- Else decrement the pointer so that it now points to the previous element, delete that element and insert the value ARR[i] in ‘lastElements’, we just inserted ARR[i] in one of the existing groups and updated the last element corresponding to that group.
- Finally, return the size of the multiset ‘lastElements’, as it denotes the minimum number of sorted groups formed so far.