Create Maximum Number Problem


Description

LeetCode Problem 321.

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:

1
2
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

1
2
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

1
2
Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

Constraints:

  • m == nums1.length
  • n == nums2.length
  • 1 <= m, n <= 500
  • 0 <= nums1[i], nums2[i] <= 9
  • 1 <= k <= m + n


Sample C++ Code

Basic Idea of this problem is that we have two arrays, so we find the largest ‘i’ digit number from nums1 and largest ‘k-i’ digit number from nums2. After having these two, we merge them using merge sort algorithm. We use merge sort because it can be proved that largest number will always be sorted in descending order. The only thing to keep in mind while merging is the case where array elements are equal. In that case, we have to loop untill we find a greater element in one of the two arrays and then act accordingly.

So after finding a i digit number from nums1 and k-i digit number from nums2, we merge them to form the maximum k digit number from these two arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector <int>res;

        for(int i = 0; i<=k; i++){
            vector <int> a = fun(nums1, i);
            vector <int> b = fun(nums2, k-i);

            vector <int> m;
            merge(a, b, m);

            if(m.size()==k) res = max(res,m);
        }
        return res;
    }
protected:
    // This function finds the k digit maximum number possible
    vector <int> fun(vector <int>&nums, int k){
        if(k>nums.size()) return {};
        vector <int> res;
        stack <int> st;
        int rem = k, n = nums.size();
        for(int i = 0; i<n; i++){
            if(st.empty()) st.push(nums[i]), rem--;
            else{
                int avail = n-i;
                while(!st.empty() and st.top()<nums[i] and rem<k and avail>rem) st.pop(), rem++;
                st.push(nums[i]), rem--;
            }
        }
        while(st.size()>k) st.pop();
        while(!st.empty()) res.push_back(st.top()), st.pop();
        reverse(res.begin(), res.end());
        return res;
    }
    void merge(vector <int>&a, vector <int>&b, vector <int>&res){
        int i = 0, j = 0, k = 0;
        // This is the only case which we need to take care of. 
        // Here, we loop until we find a number greater than another 
        // number in other array. When we do that, we push the element 
        // in result array accordingly. 
        while(i<a.size() and j<b.size()){
            if(a[i]==b[j]){
                int ti = i, tj = j;
                while(ti<a.size() and tj<b.size() and a[ti]==b[tj]) ti++, tj++;

                if(tj==b.size()) res.push_back(a[i]), i++;
                else
                if(ti<a.size() and a[ti]>b[tj]) res.push_back(a[i]), i++;
                else res.push_back(b[j]), j++;
            }
            else
            if(a[i]>b[j]) res.push_back(a[i]), i++;
            else res.push_back(b[j]), j++;
        }
        while(i<a.size()) res.push_back(a[i]), i++;
        while(j<b.size()) res.push_back(b[j]), j++;
    }
};




Related Posts

Create Maximum Number Problem

LeetCode 321. You are given two integer arrays nums1 and...

Gas Station Problem

LeetCode 134. There are n gas stations along a circular...

Candy Problem

LeetCode 135. There are n children standing in a line....

Jump Game II Problem

LeetCode 45. Given an array of non-negative integers nums, you...

Container With Most Water Problem

LeetCode 11. Given n non-negative integers a_1, a_2, …, a_n...