Last Updated: 9 Apr, 2021
Beauty Shuffle
Moderate
Asked in companies
You are given two arrays ‘arr1’ and ‘arr2’ of the same length. The beauty of ‘arr1’ is defined as the count of the total number of indices ‘i’ such that ‘arr1[i]’ > ‘arr2[i]’.
In order to maximize the beauty of ‘arr1’ you can reorder its element in any way you want i.e you can swap any possible pair of indexes in ‘arr1’ any number of times.
You need to return any array that is made from ‘arr1’ after reordering its element such that the beauty of the returned array is maximum possible.
Note :
There can be more than one possible array with maximum beauty. In that case, you can return any of them.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains an integer ‘N’ denoting the size of arrays.
The second line of each test case contains ‘N’ space-separated integers, representing the elements of the first array, ‘arr1’.
The last line of the test cases contains ‘N’ space-separated integers, representing the elements of the second array, ‘arr2’.
Output Format :
For each test case, the output will be “1” if you have returned the correct answer, else it will be “0”.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 5000
1 <= arr1[i], arr2[i] <= 10 ^ 9
Time Limit: 1sec
Approaches
Check all the possible permutations of ‘arr1’ and return the one with maximum beauty.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’.
- Sort the ‘arr1’
- Declare a variable say ‘maxBeauty’.
- Declare a 2-D array say ‘allPermutation’ to store all permutations of ‘arr1’.
- Run a loop for each permutations of ‘arr1’
- Declare a variable ‘temp’
- Run a loop through ‘arr1’
- If ‘arr1[i]’ > ‘arr2[i]’
- Increment temp by 1 i.e. do ‘temp’ += 1
- If ‘arr1[i]’ > ‘arr2[i]’
- Update ‘maxBeauty’ i.e. do ‘maxBeauty’ := max( ‘maxBeauty’, ‘temp’)
- Add ‘arr1’ to ‘allPermutation’
- Update ‘arr1’ to next permutations of ‘arr1’.
- Run a loop through each array ‘arr1’ in ‘allPermutation’
- Declare a variable ‘temp’
- Run a loop from i = 0 to length ‘arr1’ - 1
- If ‘arr1[i]’ > ‘arr2[i]’
- Increment temp by 1 i.e. do ‘temp’ += 1.
- If ‘arr1[i]’ > ‘arr2[i]’
- If ‘temp’ == ‘maxBeauty’
- Return ‘arr1’
The given problem can be viewed as choosing ‘arr1[i]’ from the given elements in ‘arr1’ against ‘arr2[i]’ for each ‘i’ such that beauty can be maximized. So for a given ‘arr2[i]’ we want to choose an element from ‘arr1’ that hasn’t been chosen before such that it should be greater than ‘arr2[i]’. Now suppose there are ‘K’ available elements in ‘arr1’ that are greater than ‘arr2[i]’. It will be best to choose ‘arr1[i]’ as the minimum from these ‘K’ elements because other ‘K-1’ remaining elements can be used for any other ‘arr2[j]’ ( j != 1). But if ‘K’ is 0 i.e. there is no element in ‘arr1’ that is greater than ‘arr2[i]’, then it will be best to choose ‘arr[i]’ as the minimum of all elements remaining in ‘arr1’ because elements other than minimum element can be choose for any other ‘arr2[j]’ (j != i) . So the idea is to iterate through the given ‘arr2’ array and choose the nearest maximum element of each ‘arr2[i]’ from remaining ‘arr1’ if available else choose the minimum element, then remove this element from available ‘arr1’.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’.
- Declare an empty array say ‘result’ to store the resultant ‘arr1’.
- Run a loop from ‘i’ = 0 to length ‘arr2’ - 1 to traverse the array ‘arr2’.
- Let the current element in ‘arr2’ be ‘arr2[i]’
- Declare a variable say ‘nextGreater’ to store the minimum element in remaining arr1 such that that it is greater than ‘arr2[i]’.
- Initialize the ‘nextGreater’ with infinite.
- Run a loop from ‘j’ = 0 to length ‘arr1’ - 1 to traverse the array ‘arr1’.
- If ‘arr1[j]’ > ‘arr2[i]’.
- Set ‘nextGreater’ to min ( ‘nextGreater’, ‘arr1[j]’ ).
- If ‘arr1[j]’ > ‘arr2[i]’.
- If ‘nextGreater’ is not infinite:
- Add ‘nextGreater’ in ‘result’.
- Remove ‘nextGreater’ from ‘arr1’
- Else:
- Add min element from ‘arr1’ in ‘result’
- Remove min element from ‘arr1’.
- Return ‘result’
In order to maximize the beauty of ‘arr1’ we greedily choose elements from ‘arr1’ for each element in ‘arr2’. For a given element in ‘arr2’ say ‘x’ we need to find an element from ‘arr1’ say ‘y’ such that ‘y’ should be a minimum number that is greater than ‘x’ and ‘y’ must not be chosen before for any element in ‘arr2’. If such ‘y’ do not exist, we select the minimum element from the un-used ‘arr1’ as this will ensure that elements other than minimum element could be chosen for some other ‘x’ in ‘arr2’. To avoid searching for ‘y’ every time for each ‘x’ in ‘arr2’, we can use a multiset data structure to store all elements of ‘arr1’ and efficiently find the upper bound of ‘x’ i.e. finding minimum element greater than ‘x’ in the set.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’.
- Declare an empty array say ‘result’ to store the resultant ‘arr1’.
- Declare a multiset of integers say ‘elements’ to store the elements of ‘arr1’.
- Run a loop from ‘i’ = 0 to length of ‘arr1’ - 1.
- Add ‘arr1[i]’ into ‘elements’
- Run a loop from ‘i’ = 0 to length of ‘arr2‘ - 1.
- If the upper bound of ‘arr2[i]’ in ‘elements’ exists
- Add the upper bound of ‘arr2[i]’ into the results.
- Remove the upper bound of ‘arr2[i]’ from ‘elements’.
- Else
- Add the minimum element from ‘elements’ into the results.
- Remove the minimum element from ‘elements’.
- If the upper bound of ‘arr2[i]’ in ‘elements’ exists
- Return results.
Suppose for a maximum element in ‘arr2’ say ‘currMax’, we need to select a corresponding element from ‘arr1’. In this case we just need to check the maximum element in ‘arr1’ if it is greater than ‘currMax’, then it will be the corresponding element of ‘currMax’, else there is no element in ‘arr1’ that has a value greater than ‘currMax’, so regardless of selecting any corresponding element, this element does not contribute in the beauty of ‘arr1’. That’s why we will select the minimum element of ‘arr1’ as a corresponding element because elements other than minimum have more chance to contribute to the beauty of ‘arr1’ i.e. other elements may be used as a corresponding element for some elements in ‘arr2’. So the Idea is If the current maximum non-used element in ‘arr1’ is greater than the maximum non-used element in ‘arr2’, we assign the value of ‘arr1’ to the index of the maximum element in ‘arr2’. Or else, we assign the minimum non-used element to the index of the maximum element in ‘arr2’. We can use the max heap to iterate through elements in ‘arr2’. And sort the array ‘arr1’ to find the maximum and minimum element.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’ of size ‘N’
- Declare an empty array of size ‘N’ say ‘result’ to store the resultant ‘arr1’.
- Sort the array ‘arr1’ in ascending order.
- Declare two variables say ‘min’, ‘max’ to store the index of minimum and maximum element in ‘arr1’.
- ‘min’ = 0 , ‘max’ = ‘N’ - 1;
- Declare a max heap to store the elements of ‘arr2’ with their indices. The top element of the max heap will contain an element of ‘arr2’ with maximum value and its index.
- Push all elements of ‘arr2’ with their index in a max heap.
- Run a loop while the max heap is not empty.
- Pop element from heap say ‘currElement’
- If ‘currElement -> value’ < ‘arr1[max]’
- Result[ ‘currElement -> index’ ] = ‘arr1[max]’
- Decrement ‘max’ by 1 i.e. do ‘max’ -= 1.
- Else,
- Result[ ‘currElement -> index’ ] = ‘arr1[min]’
- Increment min by 1 i.e. do ‘min’ += 1.
- Return Result.
As discussed in the previous approach, instead of using heap to order elements of ‘arr2’, we can just simply sort ‘arr2’ while keeping track of indices of each element. And then iterate over ‘arr2’ in descending order and use two pointers in ‘arr1’ to keep track of the current minimum and maximum element in ‘arr1’.
Algorithm:
- Let the given array be ‘arr1’ and ‘arr2’ of size ‘N’
- Declare an empty array of size ‘N’ say ‘result’ to store the resultant ‘arr1’.
- Sort the array ‘arr1’ in ascending order.
- Declare two variables say ‘min’, ‘max’ to store the index of minimum and maximum element in ‘arr1’.
- ‘min’ = 0 , ‘max’ = ‘N’ - 1;
- Declare a 2D array say ‘arr[N][2]’ to store the elements of ‘arr2’ with their indices.
- Run a loop from ‘i’ = 0 to the length of ‘arr2’.
- Store value of ‘arr2’ at ‘i -th’ index in ‘arr[i][0]’ i.e. ‘arr[i][0]’ = ‘arr2[i]’
- Store index ‘i’ in ‘arr[i][1]’, i.e. ‘arr[i][1]’ = i.
- Sort the ‘arr’ in descending order.
- Run a loop from ‘i’ = 0 to ‘N’ - 1.
- Declare a variable say ‘currElement’ to store the current element of ‘arr’, i.e. ‘currElement’ = ‘arr[i][0]’.
- If ‘currElement’ < ‘arr1[max]’
- ‘result[ ‘arr[i][1]’ ]’ = ‘arr1[max]’
- Decrement ‘max’ by 1 i.e. do ‘max’ -= 1.
- Else,
- ‘result[ ‘arr[i][1]’ ]’ = ‘arr1[min]’
- Increment min by 1 i.e. do ‘min’ += 1.
- Return ‘result’.