Create Sorted Array through Instructions

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
4 upvotes
Asked in companies
SamsungAccolite

Problem statement

You are given an array ‘ARR’. You are supposed to create a sorted array beginning with an empty array in the order given in the array ‘ARR’. The cost of inserting an element is the minimum of the number of elements that are strictly less than ARR[i] and the number of elements strictly greater than ARR[i] currently present in the array that you are supposed to create.

For example, if the NEW_ARR[] = [4, 5, 6, 7, 8]. Now suppose that we want to insert 5 in this array then, in order to insert 5, the number of elements strictly lesser than 5 is 1, and the number of elements strictly greater than 5 is 3. So, the cost of inserting 5 is min(1, 3) = 1.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains integer ‘N’, which denotes the number of elements in the array ‘ARR’.

The second line contains 'N' integers denoting the elements of the array ‘ARR’.
Output Format: 
For each test case, return the total cost to insert all the elements in the array under the given conditions.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function
Constraints: 
1<= T <= 50
1 <= N <= 10^4
1 <= ARR[i] <= 10^4

Time Limit: 1 sec
Sample Input 1:
2
4
2 1 4 2
4
1 2 3 4
Sample Output 1:
1
0
Explanation for Sample Input 1:
In the first test case, the given array is [2, 1, 4, 2].
We start from an empty array ‘TEMP’.
Let ‘X’ be the number of elements strictly greater than the current element and ‘Y’ be the number of elements strictly lesser than the current element.
Array ‘TEMP’    -   ARR[i]  -   x   -   y   -   cost = min(x,y)
[]          -   2   -   0   -   0   -   0
[2]         -   1   -   1   -   0   -   0   
[2, 1]      -   4   -   0   -   2   -   0
[2, 1, 4]       -   2   -   1   -   1   -   1
Hence the total cost is 0+0+0+1 = 1.

In the second test case, the given array is [1, 2, 3, 4].
We start from an empty array ‘TEMP’.
Let ‘X’ be the number of elements strictly greater than the current element and ‘Y’ be the number of elements strictly lesser than the current element.
Array ‘TEMP’    -   ARR[i]  -   x   -   y   -   cost = min(x,y)
[]          -   1   -   0   -   0   -   0
[1]         -   2   -   0   -   1   -   0   
[1, 2]      -   3   -   0   -   2   -   0
[1, 2, 3]       -   4   -   0   -   3   -   0
Hence the total cost is 0+0+0+0 = 0.
Sample Input 2:
2
7
1 2 2 1 4 1 2
10
10 1 9 2 8 3 7 4 6 5
Sample Output 2:
1
20
Hint

Can you count the number of elements strictly smaller and strictly greater than the given element and take the minimum of both?

Approaches (2)
Brute Force

The idea is to traverse all the elements and count the number of elements strictly lesser and strictly greater than the current element.

 

The steps are as follows:

  • Initialize an integer ‘COST’ to 0.
  • Declare an empty array ‘TEMP’ in which elements will be inserted.
  • Iterate over all the elements:
    • Initialize two integers - ‘STRICTLY_LESS’ and ‘STRICTLY_MORE’ to 0.
    • Iterate over the array ‘TEMP’:
      • If the current element in ‘ARR’ is strictly greater than the current element in ‘TEMP’, increment ‘STRICTLY_MORE’.
      • If the current element in ‘ARR’ is strictly lesser than the current element in ‘TEMP’, increment ‘STRICTLY_LESS’.
    • Take the minimum of both ‘STRICTLY_LESS’ and ‘STRICTLY_MORE’ and add it to ‘cost’.
    • Push the current element in the array ‘TEMP’.
  • Return ‘COST’ as the final answer.

 

Time Complexity

O(N^2), where ‘N’ is the number of elements in the array ‘ARR’.

 

As we are having two nested loops each traversing the whole array. Hence the time complexity is O(N^2).

Space Complexity

O(N), where ‘N’ is the number of elements in the array ‘ARR’.

 

As we are using an extra array ‘temp’ to perform instruction upon. Hence, the overall space complexity is O(N). 

Code Solution
(100% EXP penalty)
Create Sorted Array through Instructions
Full screen
Console