Create Lexicographically Greatest Array

The resulting array may have ‘i’ elements from ‘arr1’ and ‘K’ - ‘i’ elements from ‘arr2’, where ‘i’ can be any integer from ‘0’ to min(‘K’, size of ‘arr1’). So we can iterate through all these ‘i’ and find a resultant array which is lexicographically maximum. First thing to observe is that if we choose a subsequence ‘X’ of length ‘K1’ from ‘arr1’ and subsequence ‘Y’ of length ‘K2’ form ‘arr2’ such that ‘K1’ + ‘K2’ = ‘K’, and after merging ‘X’ and ‘Y’ we will get a array say ‘result’ that is lexicographically maximum, then ‘X’ and ‘Y’ must be lexicographically maximum possible also. For example let ‘X be [ ‘x1’, ‘x2’]  and ‘Y’ be [ ‘y1’, ‘y2’ ] and ‘result’ be [ ‘ x1’ , ‘y1’, ‘x2’, ‘y2’], Now we say that the ‘result’ is lexicographically maximum, and let there exists another subsequence in ‘arr1’ of length 2 such that it is lexicographically greater than ‘X’ but then ‘result’ cannot be lexicographically maximum.

So now, the problem can be divided into two parts.

1. Finding lexicographically maximum subsequences from ‘arr1’ for each length ‘X’, and  lexicographically maximum subsequences from ‘arr2’ of length ‘K’ - ‘X’, where ‘X’ is from 0 to length of ‘arr1’
2. Merging two subsequences in a way to obtain a lexicographically maximum array.

To find lexicographically maximum subsequences from an array, we can use stack. We will maintain a non-increasing stack of size of ‘K’ elements. We iterate over the array and pop the elements in the stack until the current element is greater than the top element in the stack and push the current element. 

For example, let the array be [ 6, 8, 5, 4, 2, 6, 6, 10 ] and we need a subsequence of size 3.

• We start with pushing ‘6’ into the stack, stack: [ 6 ]
• 8 is greater than 6 so we pop 6 from the stack and push 8, stack: [ 8 ]
• 5 is less than 8, so push 5, stack : [ 8, 5 ].
• 4 is less than 5, so push 4, stack : [ 8, 5, 4 ]
• 2 is less than 4, but stack size is already 3 so we don’t push anymore.
• 6 is greater than 4 and 5 so pop both and push 6, stack : [ 8, 6 ]
• 6 is equal to 6, so we will push 6, stack: [ 8, 6, 6 ]
• 10 is greater than 6 but we now only pop one 6 because popping second 6 cannot make a subsequence with size 3. As 10 is the last element in the array. So the final stack becomes [8, 6, 10].

To merge two subsequences such that we obtain a lexicographically maximum array, we just use the merge technique as done in merge sort, with a slight modification i.e to add each element into a merged array we not only check the current element from both arrays, we have to check subarrays of both arrays starting from the current element to the length of the arrays, and then we add the element of an array whose subarray is lexicographically greater. For example, if the arrays are [2, 2, 4] and [2, 2, 2, 5]. For the first element of the merged array, we don’t check only the first element of both arrays as done in merge sort, here we have to check subarrays of both arrays starting from index 0 to length of both arrays i.e [2, 2, 4] and [2, 2, 2, 5]. And we can see that the first array is lexicographically bigger. So we add ‘2’ of the first array into ‘merged’.

Algorithm:

• Let ‘arr1’ and ‘arr2’ be the given first and second array with length ‘N’ and ‘M’.
• Declare a function say ‘getSeq’ to find the lexicographically maximum subsequence of size ‘x’ in an array.
• Declare a function say ‘isGreater’ to find a lexicographically greater array from the given two arrays.
• Declare a function say ‘merge’ to merge two sequences into one array.
• Declare an empty array say ‘result’ to store the resultant array.
• Run a loop from i = 0 to min (‘K’ , ‘N’ )
  • If ‘K’ - ‘i’  < ‘M’, which means we can take a subsequence of size ‘i’ from ‘arr1’ and subsequence of size ‘K’ - ‘i’ from ‘arr2’.
    • Find the lexicographically maximum subsequence of size ‘i’ in ‘arr1’ by calling the function ‘getSeq’ and store this array in ‘seq1’.
    • Find the lexicographically maximum subsequence of size ‘K’ - ‘i’ in ‘arr2’ by calling the function ‘getSeq’ and store this array in ‘seq2’.
    • Call merge(‘seq1’, ‘seq2’) and store the returned array in ‘temp’.
    • If ‘temp’ array is lexicographically greater than ‘result’
      • Then update the ‘result’ array to temp.

Description of ‘isGreater’ function

The Function compares two arrays for lexicographic order, it will return true if the subarray ‘firstArr[ ‘idx1’ : size of ‘firstArr’ ]’ is lexicographically bigger than ‘secArr [ ‘idx2’ : size of ‘secArr’ ]’ .  

The function will take two parameters:

• ‘firstArr’: first array
• ‘secArr’: second array.
• ‘idx1’: start index of first array to compare
• ‘idx2’: start index of second array to compare.

bool isGreater ( ‘firstArr’, ‘secArr’, ‘idx1’, ‘idx2’ ):

• Run a while loop until ‘idx1’ is less than the size of ‘firstArr’ and  ‘idx2’ is less than size of ‘secArr’  and ‘firstArr[idx]’ == ‘secArr[i]’.
  • Increment ‘idx1’ and ‘idx2’ by 1. I.e ‘idx1’ += 1, ‘idx2’ += 1.
• If ‘idx2’ == ‘secArr’, that means all the elements of ‘secArr’ form initial ‘idx2’ to size of ‘secArr’ are equal to elements of ‘firstArr’ from initial ‘idx1’ to size of ‘secArr’. So either ‘firstArr’ will be greater than ‘secArr’ or equal
  • Return true.
• If ‘idx1’ < size of ‘firstArr’  and ‘firstArr[idx1]’ > ‘secArr[idx2]’
  • Return true, as the ‘first’  array is greater than ‘secArr’.
• Return false as ‘secArr’ is greater than ‘firstArr’.

Description of ‘getSeq’ function

This function will return the lexicographically maximum possible subsequence of length ‘len’ from ‘arr’. 

The function will take two parameters:

• ‘arr’: array to get subsequence
• ‘len’: length of subsequence required.

array getSeq ( ‘arr’, ‘len’ ):

• Declare a stack to find lexicographically max subsequence.
• Run a loop from i = 0  to size of ‘arr’ - 1.
  • Run a while loop until the stack is not empty and top element of the stack is less than arr[i] and size of stack + remaining elements in ‘arr’ is not less than ‘len’
    • Pop an element from the stack.
• Return the elements of the stack in reverse order.

Description of ‘merge’ function

This function will merge two given arrays such that the merged array is lexicographically maximum.

The function will take two parameters:

• ‘firstArr’: the first array
• ‘secArr’: the second array.

array merge ( ‘firstArr’, ‘secArr’, ‘idx1’, ‘idx2’ ):

• Declare an empty array say ‘merged’ to store the merged array.
• Declare two variables say ‘idx1’ and ‘idx2’ to keep track of current elements on both given arrays.
• Run a loop until ‘idx1’ is less than the size of ‘firstArr’ or ‘idx2’ is less than the size of ‘secArr’
  • The subarray of ‘firstArr’ from ‘idx1’ to length of ‘firstArr’ is lexicographically greater than the subarray of ‘secArr’ from ‘idx2’ to length of ‘secArr’.
    • Add the element of ‘firstArr’ into ‘merged’ i.e ‘firstArr[idx1]’.
    • Increment ‘idx1’ by 1.
  • Else, add the element of ‘secArr’ into ‘merged’ i.e. ‘secArr[idx2]’ and increment ‘idx2’ by 1.
• Return ‘merged’.

O(K * (N + M + K ^ 2)), where ‘K’ is the size of the required array, ‘N’ and ‘M’ are the size of the given array.

In the worst-case ‘getSeq’ function will take O(N) time for the first array and O (M) for the second array. ‘merge’ function takes O (K ^ 2) time in the worst case, as an array to merge can have maximum length ‘K’ and its inner loop i.e. ‘isGreater’ function takes O(K) in the worst case. And we are calling these functions ‘K’ times. Hence the overall time complexity will be O(K) * ( O( N  + M ) + O( K ^ 2) ) =  O (K * (N + M + K ^ 2)).

O(K), where ‘K’ is the size of the required array.

In the worst case, we are using an array of size ‘K’ for the ‘getSeq’ function and a stack that can have max length ‘K’, and also an array to store the resulting array.