Last Updated: 26 Aug, 2021
Minimum Cost
Moderate
Asked in company
You are given an array of ‘N’ integers and your task is to sort the array using the following operations.
In one operation you can select a sub-array of the array and sort it. The cost of performing such an operation will be the square of the length of the sub-array you are sorting.
You task is to find the minimum cost of sorting the whole array.
Example:-
You are given,
array ARR=[4,3,2,1]
So, the output is 16 as we can take the sub-array [4,3,2,1](from index 0 to index 4) and sort it. So the total cost is 4*4 (16).
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.
The first line of each test case contains one integers ‘N’ denoting the number of elements in the array.
The next line of each test case contains ‘N’ integers of the array( ARR).
Output Format :
For each test case, return the minimum cost required to sort the whole array.
The output of each test case should 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 <= 5
3 <= N <= 10^5
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
First, we keep a sorted version of the array arr. Now we start iterating in the original array. If the count of the elements in the original array is equal to the count of the elements in the sorted array we sort this sub-array and go on.
Algorithm:-
- Create a duplicate array named SORTEDARR and sort this array.
- Initialize a map named COUNT.
- Initialize a variable named ANS with value 0 and a variable named LAST with -1.
- Iterate from 0 to N (Let’s say the iterator is i).
- Increment COUNT[ARR[i]] by 1 and decrement COUNT[SORTEDARR[i]] by 1.(If the values in the map COUNT are all 0, it implies that the frequency of all the elements in the original and final array are same).
- Initialize a variable named FLAG with value True.
- Iterate through the map COUNT (Let’s say the iterator is j).
- If COUNT[j] is equal to 0, continue.
- Else, update FLAG as False and break.
- If FLAG is equal to True,
- If i-LAST is not equal to 1,(array of length 1 is always sorted)
- Increment ans by (i-LAST)*(i-LAST)
- Update last as i.
- If i-LAST is not equal to 1,(array of length 1 is always sorted)
- Increment COUNT[ARR[i]] by 1 and decrement COUNT[SORTEDARR[i]] by 1.(If the values in the map COUNT are all 0, it implies that the frequency of all the elements in the original and final array are same).
- Return ans.
First, we keep a sorted version of the array arr. Now we start iterating in the original array. If the count of the elements in the original array is equal to the count of the elements in the sorted array we sort this sub-array and go on. We use an ordered map to search more efficiently.
Algorithm:-
- Create a duplicate array named SORTEDARR and sort this array.
- Initialize a map named COUNT.
- Initialize a variable named ANS with value 0 and a variable named LAST with -1.
- Iterate from 0 to N (Let’s say the iterator is i).
- Increment COUNT[ARR[i]] by 1 and decrement COUNT[SORTEDARR[i]] by 1.(If the values in the map COUNT are all 0, it implies that the frequency of all the elements in the original and final array are same).
- If the value of COUNT[ARR[i]] is equal to 0, we delete the key.
- If the value of COUNT[SORTEDARR[i]] is equal to 0, we delete the key.
- If the size of COUNT is 0,
- If i-LAST is not equal to 1,(array of length 1 is always sorted)
- Increment ans by (i-LAST)*(i-LAST).
- Update last as i.
- If i-LAST is not equal to 1,(array of length 1 is always sorted)
- Return ans.