Create Maximum Number

hard monotonic stack greedy

Problem

Given two arrays of digits (representing numbers) and an integer k, return the largest k-digit number formable by taking k digits in order across both arrays.

Inputnums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5

Output[9,8,6,5,3]

Split k=2+3: stack on nums1 → [6,5]; on nums2 → [9,8,3]; merge → 98653.

nums1

nums2

def max_number(nums1, nums2, k):
    def max_sub(nums, t):
        stack = []; drop = len(nums) - t
        for x in nums:
            while stack and drop > 0 and stack[-1] < x:
                stack.pop(); drop -= 1
            stack.append(x)
        return stack[:t]
    def merge(a, b):
        out = []
        while a or b:
            out.append((a if a > b else b)[0])
            if a > b: a = a[1:]
            else: b = b[1:]
        return out
    best = []
    for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
        cand = merge(max_sub(nums1, i), max_sub(nums2, k - i))
        if cand > best: best = cand
    return best

function maxNumber(nums1, nums2, k) {
  function maxSub(nums, t) {
    const stack = []; let drop = nums.length - t;
    for (const x of nums) {
      while (stack.length && drop > 0 && stack[stack.length - 1] < x) { stack.pop(); drop--; }
      stack.push(x);
    }
    return stack.slice(0, t);
  }
  function greater(a, i, b, j) {
    while (i < a.length && j < b.length && a[i] === b[j]) { i++; j++; }
    return j === b.length || (i < a.length && a[i] > b[j]);
  }
  function merge(a, b) {
    const out = []; let i = 0, j = 0;
    while (i < a.length || j < b.length) {
      out.push(greater(a, i, b, j) ? a[i++] : b[j++]);
    }
    return out;
  }
  let best = [];
  for (let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
    const cand = merge(maxSub(nums1, i), maxSub(nums2, k - i));
    if (cand.join() > best.join()) best = cand;
  }
  return best;
}

class Solution {
    public int[] maxNumber(int[] n1, int[] n2, int k) {
        int[] best = new int[k];
        for (int i = Math.max(0, k - n2.length); i <= Math.min(k, n1.length); i++) {
            int[] cand = merge(maxSub(n1, i), maxSub(n2, k - i));
            if (greater(cand, 0, best, 0)) best = cand;
        }
        return best;
    }
    int[] maxSub(int[] a, int t) {
        int[] stack = new int[t]; int top = 0, drop = a.length - t;
        for (int x : a) {
            while (top > 0 && drop > 0 && stack[top - 1] < x) { top--; drop--; }
            if (top < t) stack[top++] = x; else drop--;
        }
        return stack;
    }
    int[] merge(int[] a, int[] b) {
        int[] r = new int[a.length + b.length];
        int i = 0, j = 0, idx = 0;
        while (i < a.length || j < b.length) r[idx++] = greater(a, i, b, j) ? a[i++] : b[j++];
        return r;
    }
    boolean greater(int[] a, int i, int[] b, int j) {
        while (i < a.length && j < b.length && a[i] == b[j]) { i++; j++; }
        return j == b.length || (i < a.length && a[i] > b[j]);
    }
}

class Solution {
public:
    vector maxNumber(vector& n1, vector& n2, int k) {
        vector best;
        for (int i = max(0, k - (int)n2.size()); i <= min(k, (int)n1.size()); i++) {
            auto cand = merge(maxSub(n1, i), maxSub(n2, k - i));
            if (greater(cand, 0, best, 0)) best = cand;
        }
        return best;
    }
    vector maxSub(vector& a, int t) {
        vector st; int drop = a.size() - t;
        for (int x : a) { while (!st.empty() && drop > 0 && st.back() < x) { st.pop_back(); drop--; } st.push_back(x); }
        st.resize(t); return st;
    }
    vector merge(vector a, vector b) {
        vector r;
        while (!a.empty() || !b.empty()) {
            if (greater(a, 0, b, 0)) { r.push_back(a.front()); a.erase(a.begin()); }
            else { r.push_back(b.front()); b.erase(b.begin()); }
        }
        return r;
    }
    bool greater(vector& a, int i, vector& b, int j) {
        while (i < (int)a.size() && j < (int)b.size() && a[i] == b[j]) { i++; j++; }
        return j == (int)b.size() || (i < (int)a.size() && a[i] > b[j]);
    }
};

Explanation

We must pick k digits total across two arrays, keeping each array's order, to build the largest possible number. The trick is to break it into two well-known pieces: pick the best subsequence from each array, then merge them greedily.

The helper max_sub(nums, t) finds the largest t-digit subsequence of one array using a monotonic stack. As we scan, while the stack top is smaller than the current digit and we still have room to drop digits, we pop it — pushing bigger digits to the front makes the number larger. We are allowed to drop exactly len(nums) - t digits.

Since we do not know how many digits to take from each array, we try every split: take i from nums1 and k - i from nums2, for all valid i. For each split we merge the two subsequences, always choosing from whichever side is lexicographically larger from that point on. We keep the best candidate across all splits.

Example: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5. The split 2+3 gives best subsequences [6,5] and [9,8,3]; merging them yields [9,8,6,5,3], which beats every other split.

The careful "greater" comparison in merge looks ahead when digits tie, so the merge never makes a locally-good but globally-worse choice.

Time: O(k(m+n)) Space: O(k)