Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Beautiful Distribution

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in company
Wipro

Problem statement

You are given an array ‘A’ containing ‘N’ positive integers.

You define a beautiful distribution of an array as follows.

1. Split the array into multiple groups.

2. Each element of the array is present in exactly one group.

3. If you individually sort each group, the array ‘A’ should also become sorted.

Here, groups means a consecutive set of array ‘A’ elements.

There can be multiple beautiful distributions, so you are interested in the one where the number of groups is maximized.

Your task is to find the maximum number of groups possible in a beautiful distribution.

Example :
‘N’ = 5, ‘A’ = [2, 1, 4, 4 ,3]
Here we can form 2 groups, ‘[2, 1]’ and ‘[4, 4, 3]’. After individually sorting them, the array will be ‘[1, 2, 3, 4, 4]’ and is sorted. And it can be proved that this is the best answer.
Hence, the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^9

It’s guaranteed that sum of ‘N’ over all cases doesn’t exceed 10^5.
Time limit: 1 sec
Sample Input 1 :
2
5
2 3 5 3 5 
5
3 3 3 4 4 
Sample Output 1 :
4
5
Explanation For Sample Input 1 :
For test case 1: 
We can create the 4 groups in the following way: [2], [3], [5, 3], and [5]. If we sort all groups, [5 3] will become [3 5], and the final array will be sorted.
Hence, the answer is 4.

For test case 2:
The array is already sorted so that we can create ‘N’ groups, each group consisting of a single element.
Hence, the answer is 5.
Sample Input 2 :
2
4
2 1 3 2
6
4 3 3 2 3 4 
Sample Output 2 :
2
2
Full screen
Console