Minimum Cost

Moderate
0/80
Average time to solve is 20m
13 upvotes
Asked in company
Disney + Hotstar

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
4 
4 3 2 1
Sample Output 1 :
16
Explanation for Sample Output 1 :
In the first test case, we take the whole array [4,3,2,1] and sort it. So, the cost required is 4*4 as the length of the sub-array we have taken is 4.
Sample Input 2 :
1
6
2 3 1 6 4 5
Sample Output 2 :
18
Hint

Check if sorting a particular sub-array sort the array in that range of indexes.

Approaches (2)
Greedy

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:-

 

  1. Create a duplicate array named SORTEDARR and sort this array.
  2. Initialize a map named COUNT.
  3. Initialize a variable named ANS with value 0 and a variable named LAST with -1.
  4. 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.
  5. Return ans.
Time Complexity

O(N*N), where N is the length of all the array arr.

 

We are checking the count of every number for every index, so the total time taken is O(N*N).

Space Complexity

O(N) where N is the length of all the array arr.

 

We are storing the count of every element in the array, so the space complexity is O(N).

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