Last Updated: 2 Sep, 2022

Beautiful Distribution

Moderate

Solve now

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.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains a single integer, ‘N'.
The following line contains ‘N’ single space-separated integers, denoting the array ‘A’.

Output Format :

For each test case, return the maximum number of groups in a beautiful distribution.

Output for each test case will be printed on 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 ≤ 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

Solve now

Approaches

01 Approach

Approach:
Let’s keep the sorted version of the given array and store it in ‘S’.
Assume that we have 3 groups whose endings are ‘X1’, ‘X2’, and ‘N’.
Then we know that if we sort ‘[0…X1]’ of array ‘A’, it should become the same as ‘[0…X1]’ of ‘S’. And similar is the case for ‘[X1+1….X2]’ and’ ‘[X2+1…N]’.
We can keep the suffix minimum and the prefix maximum to check if the above condition is met.
Let’s say we want to check if we can end the current group at the ‘ith’ index. Then, the prefix maximum till ‘i’ must be smaller than or equal to the suffix maximum till ‘i+1’.
If the above condition is not satisfied, we cannot end a group because there is an element smaller than some value in the prefix, so it must be added to the group.
If the above condition is met, we can create a group because there is no value smaller than the maximum prefix.
After checking, the condition for all indexes, we can return the ‘count + 1’ as the final answer. Because there are ‘count’ endpoints, there are ‘count + 1’ groups.

Algorithm:

Declare ‘ans’ = 1, and ‘n’ = ‘a.size()’.
Declare an array ‘sufMin’ of size ‘n’ to keep track of the minimum value till each suffix.
Iterate through the array from back ‘i’ from [‘n-1’ to 0] and create the suffix minimum.
‘sufMin[i] = a[i]’.
If ‘i+1 < n’ -> ‘sufMin[i] = min(sufMin[i], sufMin[i+1])’
Declare ‘curr’ = ‘a[0]’ to keep track of prefix maximum.
Iterate through the array from [0, ‘n-1’] and let the current element be ‘i’.
‘curr = max(curr, a[i])’
If ‘i+1 <n’ and ‘curr <= sufMin[i+1]’ -> ‘ans++’
Return ‘ans’ as the final answer.

Solve now