321. Create Maximum Number

• Difficulty: Hard

• Topics: Dynamic Programming, Greedy

• Similar Questions:

  • Remove K Digits

  • Maximum Swap

Problem:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

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

Example 2:

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

Example 3:

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

Solutions:

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ret;
        for (int i = 0; i <= nums1.size(); ++i) {
            int deleteNum1 = nums1.size() - i;
            int deleteNum2 = nums2.size() - (k - i);

            if (deleteNum1 < 0 || deleteNum2 < 0 || k - i < 0) continue; // sanity check

            vector<int> deleted1 = deleteDigit(nums1, deleteNum1);
            vector<int> deleted2 = deleteDigit(nums2, deleteNum2);

            vector<int> num = merge(deleted1, deleted2);
            ret = max(ret, num);
        }

        return ret;
    }

private:
    bool greater(vector<int>& num1, vector<int>& num2) { // it is not necessary to define it ourself
        for (int i = 0; i < min(num1.size(), num2.size()); ++i) {
            if (num1[i] > num2[i])  return true;
            if (num1[i] < num2[i])  return false;
        }

        return (num1.size() >= num2.size());
    }

    vector<int> deleteDigit(vector<int> nums, int k) {
        nums.push_back(10);
        vector<int> stk;

        for (auto& num : nums) {
            while (!stk.empty() && k > 0 && stk.back() < num) {
                stk.pop_back();
                --k;
            }
            stk.push_back(num);
        }

        stk.pop_back();
        return stk;
    }

    vector<int> merge(const vector<int> nums1, const vector<int> nums2) {
        vector<int> ans(nums1.size() + nums2.size());
        auto s1 = nums1.cbegin();
        auto e1 = nums1.cend();
        auto s2 = nums2.cbegin();
        auto e2 = nums2.cend();        
        int index = 0;
        while (s1 != e1 || s2 != e2)
            ans[index++] = 
              lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++;
        return ans;
    }
};