Last Updated: 5 Apr, 2021
Create Sorted Array through Instructions
Moderate
Asked in companies
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.
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
Approaches
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.
The idea is to pre-process the given array and break it down and represent it in the form of a tree.
For this question, two types of queries are needed - Update and COUNT_MIN_MAX.
- Update - We will insert the element in the segment tree. For this query, a subtree of the tree will be modified.
- COUNT_MIN_MAX - For the minimum and maximum query, we will iterate over the subtrees and count the number of nodes strictly smaller and greater. For this, some subtree or complete tree will be visited.
The data structure which provides these functionalities is known as a segment tree. It is also used for a number of queries like finding the sum, minimum, maximum, GCD, etc in log(N) time.
How to create the segment tree?
The segment tree is represented in the form of an array. Each node contains information answers for a range or subarray. For any index ‘i’(not a leaf node), its children are at index 2*i and 2*i + 1, respectively.
1. Build Segment tree/ Pre-processing:
- Declare an array 'SEGMENT_TREE' of size 4*N as 4*N size is enough to store all the nodes. It stores the number of elements in the given range.
- The bottom-up approach is used to build a segment tree. An iterative approach can also be used, but generally, the bottom-up approach is used. It takes O(N) time as we traverse each node exactly twice.
- But in this question, we have to count the number of elements strictly greater or smaller than the current element and then insert it in the segment tree. So, there is no need to build the segment tree. We will insert the elements in the update operation.
2. Update:
- Define a recursive function 'UPDATE' which takes 5 arguments 'SEGMENT_TREE', 'CURRENT_INDEX','VALUE', 'LOW', 'HIGH', that denotes the segment tree that we are cerating, the current index at which we are present, the VALUE that we have to insert, the lowest index, and the highest index for the current sub-segment tree.
- If 'LOW' is equal to 'HIGH', It means that it is the leaf node. So, increment SEGMENT_TREE[CURRENT_INDEX] by 1 and return.
- Find the middle of 'LOW' and 'HIGH' and store it in a variable 'MID'.
- If the 'VALUE' is greater than 'MID', call for the right sub-tree ie update(SEGMENT_TREE,2*CURRENT_INDEX + 1, VALUE, LOW, MID).
- Else call for the left sub tree ie. update(SEGMENT_TREE,2*CURRENT_INDEX + 2, VALUE, MID+1, HIGH).
- Now store the VALUE at the current index as the sum of its left and right children.
3. COUNT_MIN_MAX:
- Define a recursive function ‘COUNT_MIN_MAX’ which takes 5 arguments 'CURRENT_INDEX', 'LOW', 'HIGH',’l’, ‘h’, that denotes the current index of the node at which we are present, the lowest and highest node VALUEs for the current sub-segment tree, the range of VALUEs for which we are looking for. It returns an integer denoting the number of elements in the range l to r.
- If the range for which we are looking for completely lies inside the range of the current sub-segment tree. Return the VALUE of the current node as it should be included completely in the answer.
- If the range for which we are looking for completely lies outside the range of the current sub-segment tree, then return 0.
- Find the middle 'MID' of 'LOW' and 'HIGH' as the average of 'LOW' and 'HIGH'.
- Call for the left sub-segment tree for the same range that we are looking for i.e. COUNT_MIN_MAX(SEGMENT_TREE,2*CURRENT_INDEX + 1, LOW, MID, l, r) and store it in a variable 'LEFT_ANSWER'.
- Call for the right sub-segment tree for the same range that we are looking for i.e. COUNT_MIN_MAX(SEGMENT_TREE,2*CURRENT_INDEX + 2, MID+1, HIGH, l, r), and store it in a variable ‘RIGHT_ANSWER’.
- Return 'LEFT_ANSWER' + 'RIGHT_ANSWER' as the final answer.
Similar problems