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

<p>Create the maximum number of length <code>k &lt;= m + n</code> from digits of the two numbers. The relative order of the digits from the same array must be preserved.</p>

<p>Return an array of the <code>k</code> digits representing the answer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
<strong>Output:</strong> [9,8,6,5,3]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [6,7], nums2 = [6,0,4], k = 5
<strong>Output:</strong> [6,7,6,0,4]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [3,9], nums2 = [8,9], k = 3
<strong>Output:</strong> [9,8,9]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == nums1.length</code></li>
	<li><code>n == nums2.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 9</code></li>
	<li><code>1 &lt;= k &lt;= m + n</code></li>
</ul>

class Solution {
public:
    vector<int> mostCompetitive(const vector<int>& nums, const int k) {
        if (k == 0)
            return {};

        vector<int> results = {10};
        int kk = nums.size() - k;

        for (const int i : nums) {
            while (kk > 0 && results.back() < i) {
                results.pop_back();
                kk--;
            }

            results.push_back(i);
        }

        results.erase(results.begin());

        while (results.size() > k)
            results.pop_back();

        return results;
    }

    vector<int> merge1(const vector<int> &n1, const vector<int> &n2, int r1, int r2) {
    const int s1 = n1.size(), s2 = n2.size();
    vector<int> results;
    while (r1 < s1 || r2 < s2) {
        if (r1 == s1) {
            while (r2 != n2.size()) {
                results.push_back(n2[r2]);
                r2++;
            }
            break;
        }

        if (r2 == s2) {
            while (r1 != n1.size()) {
                results.push_back(n1[r1]);
                r1++;
            }
            break;
        }

        if (n1[r1] >= n2[r2]) {
            results.push_back(n1[r1]);
            r1++;
        } else {
            results.push_back(n2[r2]);
            r2++;
        }
    }

    return results;
}

vector<int> merge2(const vector<int> &n1, const vector<int> &n2, int r1, int r2) {
    const int s1 = n1.size(), s2 = n2.size();
    vector<int> results;
    while (r1 < s1 || r2 < s2) {
        if (r1 == s1) {
            while (r2 != n2.size()) {
                results.push_back(n2[r2]);
                r2++;
            }
            break;
        }

        if (r2 == s2) {
            while (r1 != n1.size()) {
                results.push_back(n1[r1]);
                r1++;
            }
            break;
        }

        if (n1[r1] > n2[r2]) {
            results.push_back(n1[r1]);
            r1++;
        } else {
            results.push_back(n2[r2]);
            r2++;
        }
    }

    return results;
}

vector<int> merge(const vector<int> &n1, const vector<int> &n2) {
    const int s1 = n1.size(), s2 = n2.size();
    vector<int> results;
    int r1 = 0, r2 = 0;
    while (r1 < s1 || r2 < s2) {
        if (r1 == s1) {
            while (r2 != n2.size()) {
                results.push_back(n2[r2]);
                r2++;
            }
            break;
        }

        if (r2 == s2) {
            while (r1 != n1.size()) {
                results.push_back(n1[r1]);
                r1++;
            }
            break;
        }

        if (n1[r1] > n2[r2]) {
            results.push_back(n1[r1]);
            r1++;
        } else if (n1[r1] < n2[r2]) {
            results.push_back(n2[r2]);
            r2++;
        } else {
            // both r1 and r2 are equal
            // we need to find a tie breaker;
            int r1d = r1, r2d = r2;

            vector<int> result1 = merge1(n1, n2, r1, r2);
            vector<int> result2 = merge2(n1, n2, r1, r2);
            bool flag = true;
            for (int i = 0; i < result2.size(); i++) {
                if (result2[i] < result1[i]) {
                    results.push_back(n1[r1]);
                    r1++;
                    flag = false;
                    break;
                }

                if (result2[i] > result1[i]) {
                    flag = false;
                    results.push_back(n2[r2]);
                    r2++;
                    break;
                }
            }

            if (flag) {
                results.push_back(n1[r1]);
                r1++;
            }
        }
    }

    return results;
}

    vector<int> maxNumber(const vector<int>& n1, const vector<int>& n2,
                          const int k) {
        const int s1 = n1.size(), s2 = n2.size();

        vector<int> result = vector<int>(k, 0);

        for (int i = max(0, k - s2); i <= min(k, s1); i++) {
            vector<int> a = mostCompetitive(n1, i);
            vector<int> b = mostCompetitive(n2, k - i);

            vector<int> r = merge(a, b);

            // for (const int& i : r) {
            //     cout << i << " ";
            // }
            // cout << '\n';

            bool flag = true;
            for (int i = 0; i < k; i++) {
                if (r[i] > result[i]) {
                    flag = true;
                    break;
                }

                if (r[i] < result[i]) {
                    flag = false;
                    break;
                }
            }

            if (flag)
                result = r;
        }

        return result;
    }
};
202437