Rearrange Array to maximise sum of MEX of all Subarrays ranging from first index

Given an array arr[] of N components starting from 0 to N-1(each included), the duty is to rearrange the array such that the sum of all of the MEX from each subarray ranging from index 0 is most. Duplicates might be current within the array.

MEX of an array is the primary non-negative component that’s lacking from the array.

Examples:

Enter: N = 3, arr[] = {2, 1, 0}
Output: 6
Clarification: Initially for subarray {2} the lacking component is 0.
For {2, 1} the lacking component is 0, and for {2, 1, 0} the lacking component is 3. 
On this means the reply is 0 + 0 + 3 = 3.
But when the array is rearranged like {0, 1, 2}, the reply can be 1 + 2 + 3 = 6.

Enter: N = 5, arr[] = {0, 0, 0, 0, 0}
Output: 5

Strategy:

The thought is to place the smaller components within the begining of latest array to get highest potential lacking complete numbers  for every subarray, but when we’ve duplicates then the duplicates could be inserted in the long run of the brand new arrray.

Observe the steps to unravel the issues:

• Type the array.
• Initialize 2 variables cur to retailer the present smallest lacking complete quantity and rely to retailer the variety of occasions the smallest complete quantity could be smallest for the following subarrays.
  • If the present component is bigger than cur, then for all the following subarrays the smallest complete quantity could be cur, because the array is sorted. So add the variety of remaining subarrays to rely and break the loop.
  • Else if we discover the duplicates then improve the rely variable so as to add the worth in the long run.
  • Else, for every index replace cur and add the values into an ans variable that can include the ultimate reply.
• In the long run, if cur isn’t 0, means there are subarrays which have cur because the smallest complete quantity and that aren’t added to ans, so add cur * rely to the ans and return it.

Illustration:

Think about N = 6, arr[] = {4, 2, 0, 4, 1, 0}

Initialize, ans = 0, cur = 0, rely = 0

Type the array, so arr[] = {0, 0, 1, 2, 4, 4}

For index 0:
        => arr[i] = cur,  
        => thus cur could be cur + 1 = 1 
        => ans could be ans + cur = 0 + 1 = 1

For index 1: 
        => arr[i] = cur – 1 
        => Means it’s a duplicate 
        => Enhance the rely variable, rely = 0 + 1 = 1

For index 2: 
        => arr[i] = cur
        => cur could be cur + 1 = 2
        => ans could be ans + cur = 1 + 2 = 3

For index 3: 
        => arr[i] = cur,  
        => Thus cur could be cur + 1 = 3
        => ans could be ans + cur = 3 + 3 = 6

For index 4: 
        => arr[i] > cur
        => cur could be the identical for all of the remaining subarrays. 
        => Thus, rely = rely + 6 – 4 = 1 + 2(remaining subarrays) = 3 and break the loop.

In the long run add cur * rely to ans, thus ans = 6 + 3 * 3 = 15

Beneath is the implementation of this strategy:

Time Complexity: O(N * log N)
Auxiliary House: O(1)