Create Maximum Number

Approach

We can think of an approach that, given a fixed length s, finds the optimal subsequences of lengths s and k - s from arrays nums1 and nums2, respectively, without considering all possible subsequences.

This approach aims to find the maximum subsequence consisting of s digits from nums1 and the maximum subsequence consisting of k - s digits from nums2, where s varies from 0 to k. Then merge these two subsequences using the merge procedure described above. We will compare all such subsequences while s varies and output the largest one.

Concept of Monotonic Stack

We can use monotonic stacks to find the maximum subsequence of size s out of an array of size n where s <= n. 

1. Create a stack st to hold the largest subsequence. Iterate through the given array and let i be the index of the current element curr. 
    
2. Pop the topmost element in st  while the following conditions are satisfied:
   
   
   1. st is not empty.
       
   2. The topmost element is less than the current.
       
   3. Size of stack + n - i > s. This ensures that even after removing the topmost element, we are still left with enough digits to form a subsequence of size s.
       
3. Create an array that holds the elements of the stack from bottom to top and return it. This array contains the digits of the optimal subsequence.

Algorithm

1. Create nums1 and nums2 arrays of size m and n respectively. Iterate i from 0 to k inclusive.
2. Create the maxSubsequence function, which takes an array and size of the subsequence as parameters. Find the maximum subsequence using the concept of the monotonic stack described above.
3. Calculate maximum subsequences of sizes i and k - i from nums1 and nums2 respectively, using the maxSubsequence function.
4. Merge the two subsequences found in the previous step using the merge procedure.
5. Compare and store the maximum one.

Dry Run

Nums1 = 4, 5, 8, 9, 1 
Nums2 = 8, 9, 7, 4, 1, 5, 3, 3, 1};
K = 6;

For every maxSubsequence function call:

Every time before the next call, reverse the stack in array ans and return. It pops the stack and decreases the size by 1. Please remember this point.

Next Call

Next Call

Next Call

Next Call

Next Call

Program

#include<bits/stdc++.h>
using namespace std;


vector<int> modified_merge(vector<int>& arr1, int m, vector<int>& arr2, int n, int k){
    vector<int> ans(k); // to store the merged answer.
    int index = 0, a1 = 0, a2 = 0;

    while(a1 < m && a2 < n && index < k){
        // pick the largest of the two digits in consideration.
        if(arr1[a1] > arr2[a2]){
            ans[index++] = arr1[a1++];
        }
        else if(arr1[a1] < arr2[a2]){
            ans[index++] = arr2[a2++];
        }
        else{
            // if both digits are equal, pick the next largest digit from either array
            int i = a1+1, j = a2+1;
            while(i < m && j < n && arr1[i] == arr2[j]){
                i++; j++;
            }
            if(j == n || (i < m && arr1[i] > arr2[j])) ans[index++] = arr1[a1++];
            else ans[index++] = arr2[a2++];
        }
    }

    while(a1 < m){
        // copy the left outs.
        ans[index++] = arr1[a1++];
    }

    while(a2 < n){
        // copy the left outs.
        ans[index++] = arr2[a2++];
    }

    return ans;
}



vector<int> maxSubsequence(vector<int>& nums, int n, int s){


    // monotonic stack.
    stack<int> st;
    for(int i = 0; i < n; i++){


      // conditions explained above.
        while(!st.empty() && st.top() < nums[i] && st.size() + n - i > s){
            st.pop();
        }


        // if size of stack is less than s then simply push it.
        if(st.size() < s) st.push(nums[i]);
    }
  
    vector<int> ans(s);


    // reverse the stack in array ans and return.
    for(int i = s - 1; i >= 0; i--){
        ans[i] = st.top();
        st.pop();
    }


    return ans;
}


int main(){

    // taking inputs of below vector length.
    int m=5,n=9;
  

    vector<int> nums1{4, 5, 8, 9, 1 };vector<int> nums2{8, 9, 7, 4, 1, 5, 3, 3, 1};
    int k=6;
  
  
    // array to hold the largest number consisting of k digits.
    vector<int> final_ans(k, INT_MIN);
    for(int i = 0; i <= k; i++){

        // Proceed only if the size of nums1 is greater than i and size of nums2 is greater than k - i.
        // It is because the size of a subsequence of an array is always less than or equal to the size of the array.
        if(m >= i && n >= k - i){
            vector<int> v1 = maxSubsequence(nums1, m, i), v2 = maxSubsequence(nums2, n, k - i);

            // merge the optimal subsequences so found.
            vector<int> merged_result = modified_merge(v1, i, v2, k - i, k);

            // compare over all the possibilities.
            final_ans = max(final_ans, merged_result);
        }
    }

    for(int i = 0; i < k; i++){

      // output the answer.
        cout<<final_ans[i]<<" ";
    }
    cout<<endl;
}

Output

Time Complexity

• The time complexity of the above algorithm is O(k * (m + n)).
   
• The time complexity of the merge procedure is O(k) <= O(m + n) as k <= m + n.
   
• The time complexity of the maxSubsequence function is O(size of the array provided). \
   

Thus, the total time complexity of each iteration - 

T(each iteration) = O(m) + O(n) + O(k)

                             = O(m + n + k) = O(m + n) as k <= m + n.

Thus, total time complexity of the algorithm is O(k * (m + n)).

Space Complexity

The space complexity of the above algorithm is O(k). As even in the worse case, we are creating an array of size k. 

Let’s discuss some FAQs related to the topic.

Frequently Asked Questions

What is a subsequence in programming?

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

What is the difference between a subsequence and a substring?

A substring is a contiguous sequence of characters in a string, while a subsequence is not necessarily contiguous and can be derived from any sequence, not just a string.

What is the monotonic stack in programming?

The monotonic stack is a stack data structure that stores elements in non-increasing or non-decreasing order. It is used to solve various problems related to finding the maximum or minimum element in a sequence.

What is merge sort in programming?

Merge sort is an efficient sorting algorithm that uses a divide-and-conquer approach to sort an array or list of elements. It works by dividing the input into smaller parts, sorting them individually, and then merging them back together.

How does the maxSubsequence function work in this problem?

The maxSubsequence function takes an array and the desired size of the subsequence as input, and uses the monotonic stack approach to find the largest subsequence of the given size. It returns an array containing the digits of the optimal subsequence.

Conclusion

This article aimed at discussing an interesting problem based on arrays and merge sort. It tried to explain each of the topics involved precisely. Problems based on arrays are sometimes easy to implement, but an effective algorithm remains a challenge.

Hence learning never stops, and there is a lot more to learn.

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

• Course Schedule.
   
• Count of increasing substrings in given String.
   
• Count duplicates in a Linked List