<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>

#include <ranges>
#include <sstream>

struct MyFormat {
    template <typename T>
    static std::ostream& format(std::ostream& os, const T& obj) {
        os << obj;
        return os;
    }
};

template <>
std::ostream&
MyFormat::format<std::pair<int, int>>(std::ostream& os,
                                      const std::pair<int, int>& obj) {
    os << "(" << obj.first << ", " << obj.second << ")";
    return os;
}

template <std::ranges::range R> std::string printArr(R&& r) {
    using T = std::ranges::range_value_t<R>;

    std::ostringstream ss;
    auto it = std::ranges::begin(r);
    const auto end = std::ranges::end(r);

    ss << "[";

    bool first = true;
    while (it != end) {
        if (!first)
            ss << ", ";
        else
            first = false;

        MyFormat::format<T>(ss, *it);
        ++it;
    }
    ss << "]";
    return std::move(ss).str();
}

class Solution {

    static bool mergeTwo(const int k, const std::vector<int>& src1,
                         const std::vector<int>& src2, std::vector<int>& out,
                         std::vector<char>& seen,
                         int idx, int i1, int i2, bool better) {


        const int KEY = i1*(src2.size() + 1) + i2;
        if (!better && seen[KEY] != 0) {
            return seen[KEY] == 2;
        }

        if (idx == k) {
            return better;
        }

        // std::cout << "Entering with: " << k << ", idx= " << idx << ", i1=" <<
        // i1 << ", i2=" << i2 << ", better=" << better << "\n";
        const int B1 = src1.size();
        const int B2 = src2.size();

        while (i1 != B1 && i2 != B2) {
            const int a = src1[i1];
            const int b = src2[i2];

            const int cand = std::max(a, b);
            if (better) {
                out[idx++] = cand;
            } else {
                if (cand == out[idx]) {
                    idx++;
                } else if (out[idx] < cand) {
                    better = true;
                    out[idx++] = cand;
                } else {
                    break;
                }
            }

            if (idx == k)
                break;

            if (a < b) {
                i2++;
            } else if (b < a) {
                i1++;
            } else {
                // They are the same. We continue scanning until we find one
                // of the elements who are not the same.
                int i = 1;
                while (idx < k && i1 + i < B1 && i2 + i < B2) {
                    if (src1[i1 + i] == src2[i2+i]) {
                        i++;
                    } else {
                        break;
                    }
                }



                // Ok, now we know the length of the prefix.

/*
                std::cout << "Tricky:\n";
                std::cout << "SRC1: " <<
                printArr(std::ranges::subrange(src1.begin()+i1,
                src1.end())) << "\n"; std::cout << "SRC2: " <<
                printArr(std::ranges::subrange(src2.begin()+i2,
                src2.end())) << "\n";
                */

                if (i1+i == B1) {
                    i2++;
                } else if (i2+i == B2) {
                    i1++;
                } else if (src1[i1+i] < src2[i2+i]) {
                    i2++;
                } else {
                    i1++;
                }
                /*
                bool betterA =
                    mergeTwo(k, src1, src2, out, seen, idx, i1 + i, i2, better);

                auto newBetter = better;
                if (betterA)
                    newBetter = false;

                bool betterB =
                    mergeTwo(k, src1, src2, out, seen, idx, i1, i2 + i, newBetter);

                seen[KEY] = 1 + (betterA || betterB);
                return betterA || betterB;
                */
            }
        }

        while (idx < k && i1 < B1) {
            const auto cand = src1[i1++];
            if (better) {
                out[idx++] = cand;
            } else {
                if (out[idx] < cand) {
                    better = true;
                    out[idx++] = cand;
                } else if (out[idx] == cand) {
                    idx++;
                } else {
                    seen[KEY] = 1;
                    return false;
                }
            }
        }

        while (idx < k && i2 < B2) {
            const auto cand = src2[i2++];
            if (better) {
                out[idx++] = cand;
            } else {
                if (out[idx] < cand) {
                    better = true;
                    out[idx++] = cand;
                } else if (out[idx] == cand) {
                    idx++;
                } else {
                    seen[KEY] = 1;
                    return false;
                }
            }
        }

        seen[KEY] = 1 + better;
        return better;

        /*
        if (better) {
           std::cout << "We improved: " << printArr(out) << "\n";
        }
        */
    }

public:
    static std::vector<int> maxNumber(const std::vector<int>& nums1,
                                      const std::vector<int>& nums2,
                                      const int k) {

        const int N1 = nums1.size();
        const int N2 = nums2.size();
        /*
        std::cout << "Nums1: " << printArr(nums1) << "\n";
        std::cout << "Nums2: " << printArr(nums2) << "\n";
        */
        // Find the most competative array of at least size K
        constexpr auto getBestK = [](const std::vector<int>& src, const int K) {
            const int SN = src.size();
            std::vector<int> st;
            for (int i = 0; i < SN; i++) {
                const auto x = src[i];
                while (!st.empty() && st.back() < x) {
                    // ok, how many elements are left
                    const int left = SN - i;
                    const int sz = st.size();
                    if ((left + sz) <= K)
                        break;

                    st.pop_back();
                }

                st.push_back(x);
            }
            return st;
        };

        // The longer it is, the worse the overall number is going to be,
        // since it's a lower bound.
        std::vector<int> out(k, 0);

        int neededK1 = k - N2;
        int rounds = 100;
        while (neededK1 <= N1) {
            const auto bestHere1 = getBestK(nums1, neededK1);
            const int neededK2 = k - bestHere1.size();
            const auto bestHere2 = getBestK(nums2, neededK2);

            std::cout << "nK1 = " << neededK1 << ", nK2 = " << neededK2 << "\n";

            // we might have to try something better.
            neededK1 =
                std::max(neededK1, static_cast<int>(bestHere1.size())) + 1;

            // std::cout << "B1: " << printArr(bestHere1) << "\n";
            //  std::cout << "B2: " << printArr(bestHere2) << "\n";

            std::vector<char> seen((bestHere1.size()+1)*(bestHere2.size()+1), 0);

            if (mergeTwo(k, bestHere1, bestHere2, out, seen, 0, 0, 0, false)) {
                std::cout << "We improved: " << printArr(out) << "\n";
            }
        }

        return out;
    }
};
61157