Minimum Sorted Groups

Hard
0/120
Average time to solve is 40m
profile
Contributed by
6 upvotes
Asked in companies
UberCodenation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
7
1 5 2 3 4 6 7
6
-1 0 2 3 4 6
Sample Output 1 :
2
1
Explanation For Sample Input 1 :
For test case 1 :
We will print 2 because:
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.

For test case 2 : 
We will print 1 because:
The given array is itself sorted, so all the elements can be grouped together and this will result in the formation of a sorted group while maintaining the relative order of the array elements.
Sample Input 2 :
2
4
3 1 2 0
3
1 1 0
Sample Output 2 :
3
2
Hint

Is there a way to keep the track of the last element of each sorted group?

Approaches (1)
Constructive Algorithm

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 :

  1. Initialize a multiset ‘lastElements’. The elements of this multiset correspond to the last element of each group created.
  2. 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.
  3. Finally, return the size of the multiset ‘lastElements’, as it denotes the minimum number of sorted groups formed so far.
Time Complexity

O( N * log( N ) ), where N denotes the size of the array.

 

We iterate each array element exactly once, we then use the lower bound function which is itself implemented using binary search and takes ~log(G) time, where G represents the size of the multiset (or the number of groups formed), in the worst case when the input array is decreasing the number of groups formed will be of the order ~N this means that the value of G will be equal to N in that case.

Hence the time complexity is O( N*log(N) ).

Space Complexity

O( N ), where N denotes the size of the array.

 

We are keeping the track of the last element of each group in a multiset, in the worst case when the input array is decreasing, then the number of groups formed are of the order ~N, this means the size of the multiset formed will also be of the order ~N.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Minimum Sorted Groups
Full screen
Console