Create Maximum Number

Problem#

Given digit arrays nums1 (length n) and nums2 (length m), pick a length-i subsequence of nums1 and a length-(k-i) subsequence of nums2. Merge them preserving each subsequence’s order so the resulting k-digit number is lexicographically largest. Return the digits.

Examples#

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

Constraints#

1 <= n, m, 1 <= k <= n + m, digits in [0, 9].

Hints#

Hint 1

For each split i, separately compute the largest length-i subsequence of nums1 via monotonic stack, do the same for nums2, then merge.

Hint 2

Merging on ties needs lookahead: pick the side whose remaining suffix is lex-larger.

Approach#

Three primitives:

maxSubsequence(arr, t): largest length-t subsequence — monotonic stack, popping smaller predecessors while we still have leftover digits.
merge(a, b): merge two arrays into the lex-largest result, breaking ties by suffix comparison.
Try every i ∈ [max(0,k-m), min(k,n)], combine, keep the best.

Solution#

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        const int n = nums1.size(), m = nums2.size();
        vector<int> best;
        for (int i = max(0, k - m); i <= min(k, n); ++i) {
            auto a = pickMax(nums1, i);
            auto b = pickMax(nums2, k - i);
            auto cand = merge(a, b);
            if (cand > best) best = move(cand);
        }
        return best;
    }
private:
    vector<int> pickMax(const vector<int>& a, int t) {
        vector<int> stk; stk.reserve(t);
        int drop = a.size() - t;
        for (int x : a) {
            while (!stk.empty() && drop > 0 && stk.back() < x) {
                stk.pop_back(); --drop;
            }
            stk.push_back(x);
        }
        stk.resize(t);
        return stk;
    }
    vector<int> merge(const vector<int>& a, const vector<int>& b) {
        vector<int> out; out.reserve(a.size() + b.size());
        int i = 0, j = 0;
        while (i < (int)a.size() || j < (int)b.size()) {
            if (greaterSuffix(a, i, b, j)) out.push_back(a[i++]);
            else out.push_back(b[j++]);
        }
        return out;
    }
    bool greaterSuffix(const vector<int>& a, int i, const vector<int>& b, int j) {
        while (i < (int)a.size() && j < (int)b.size() && a[i] == b[j]) { ++i; ++j; }
        if (j == (int)b.size()) return true;
        if (i == (int)a.size()) return false;
        return a[i] > b[j];
    }
};

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    n, m := len(nums1), len(nums2)
    lo, hi := 0, k
    if k-m > lo {
        lo = k - m
    }
    if n < hi {
        hi = n
    }
    var best []int
    for i := lo; i <= hi; i++ {
        a := pickMax(nums1, i)
        b := pickMax(nums2, k-i)
        cand := mergeMax(a, b)
        if greater(cand, 0, best, 0) {
            best = cand
        }
    }
    return best
}

func pickMax(a []int, t int) []int {
    stk := make([]int, 0, t)
    drop := len(a) - t
    for _, x := range a {
        for len(stk) > 0 && drop > 0 && stk[len(stk)-1] < x {
            stk = stk[:len(stk)-1]
            drop--
        }
        stk = append(stk, x)
    }
    if len(stk) > t {
        stk = stk[:t]
    }
    return stk
}

func mergeMax(a, b []int) []int {
    out := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) || j < len(b) {
        if greater(a, i, b, j) {
            out = append(out, a[i])
            i++
        } else {
            out = append(out, b[j])
            j++
        }
    }
    return out
}

func greater(a []int, i int, b []int, j int) bool {
    for i < len(a) && j < len(b) && a[i] == b[j] {
        i++
        j++
    }
    if j == len(b) {
        return true
    }
    if i == len(a) {
        return false
    }
    return a[i] > b[j]
}

from typing import List

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        n, m = len(nums1), len(nums2)

        def pick_max(a: List[int], t: int) -> List[int]:
            stk: List[int] = []
            drop = len(a) - t
            for x in a:
                while stk and drop > 0 and stk[-1] < x:
                    stk.pop()
                    drop -= 1
                stk.append(x)
            return stk[:t]

        def merge(a: List[int], b: List[int]) -> List[int]:
            out: List[int] = []
            i = j = 0
            while i < len(a) or j < len(b):
                if a[i:] > b[j:]:
                    out.append(a[i])
                    i += 1
                else:
                    out.append(b[j])
                    j += 1
            return out

        best: List[int] = []
        for i in range(max(0, k - m), min(k, n) + 1):
            cand = merge(pick_max(nums1, i), pick_max(nums2, k - i))
            if cand > best:
                best = cand
        return best

function maxNumber(nums1, nums2, k) {
    const n = nums1.length, m = nums2.length;

    const pickMax = (a, t) => {
        const stk = [];
        let drop = a.length - t;
        for (const x of a) {
            while (stk.length && drop > 0 && stk[stk.length - 1] < x) {
                stk.pop();
                drop--;
            }
            stk.push(x);
        }
        return stk.slice(0, t);
    };

    const greaterSuffix = (a, i, b, j) => {
        while (i < a.length && j < b.length && a[i] === b[j]) { i++; j++; }
        if (j === b.length) return true;
        if (i === a.length) return false;
        return a[i] > b[j];
    };

    const merge = (a, b) => {
        const out = [];
        let i = 0, j = 0;
        while (i < a.length || j < b.length) {
            if (greaterSuffix(a, i, b, j)) out.push(a[i++]);
            else out.push(b[j++]);
        }
        return out;
    };

    const cmp = (a, b) => {
        for (let i = 0; i < a.length && i < b.length; i++) {
            if (a[i] !== b[i]) return a[i] - b[i];
        }
        return a.length - b.length;
    };

    let best = [];
    for (let i = Math.max(0, k - m); i <= Math.min(k, n); i++) {
        const cand = merge(pickMax(nums1, i), pickMax(nums2, k - i));
        if (cmp(cand, best) > 0) best = cand;
    }
    return best;
}

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int n = nums1.length, m = nums2.length;
        int[] best = new int[0];
        for (int i = Math.max(0, k - m); i <= Math.min(k, n); i++) {
            int[] a = pickMax(nums1, i);
            int[] b = pickMax(nums2, k - i);
            int[] cand = merge(a, b);
            if (compare(cand, 0, best, 0) > 0) best = cand;
        }
        return best;
    }

    private int[] pickMax(int[] a, int t) {
        int[] stk = new int[t];
        int top = 0;
        int drop = a.length - t;
        for (int x : a) {
            while (top > 0 && drop > 0 && stk[top - 1] < x) {
                top--;
                drop--;
            }
            if (top < t) stk[top++] = x;
            else drop--;
        }
        return stk;
    }

    private int[] merge(int[] a, int[] b) {
        int[] out = new int[a.length + b.length];
        int i = 0, j = 0, p = 0;
        while (i < a.length || j < b.length) {
            if (compare(a, i, b, j) > 0) out[p++] = a[i++];
            else out[p++] = b[j++];
        }
        return out;
    }

    private int compare(int[] a, int i, int[] b, int j) {
        while (i < a.length && j < b.length && a[i] == b[j]) {
            i++;
            j++;
        }
        if (j == b.length) return 1;
        if (i == a.length) return -1;
        return a[i] - b[j];
    }
}

function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
    const n = nums1.length, m = nums2.length;

    const pickMax = (a: number[], t: number): number[] => {
        const stk: number[] = [];
        let drop = a.length - t;
        for (const x of a) {
            while (stk.length && drop > 0 && stk[stk.length - 1] < x) {
                stk.pop();
                drop--;
            }
            stk.push(x);
        }
        return stk.slice(0, t);
    };

    const greaterSuffix = (a: number[], i: number, b: number[], j: number): boolean => {
        while (i < a.length && j < b.length && a[i] === b[j]) { i++; j++; }
        if (j === b.length) return true;
        if (i === a.length) return false;
        return a[i] > b[j];
    };

    const merge = (a: number[], b: number[]): number[] => {
        const out: number[] = [];
        let i = 0, j = 0;
        while (i < a.length || j < b.length) {
            if (greaterSuffix(a, i, b, j)) out.push(a[i++]);
            else out.push(b[j++]);
        }
        return out;
    };

    const cmp = (a: number[], b: number[]): number => {
        for (let i = 0; i < a.length && i < b.length; i++) {
            if (a[i] !== b[i]) return a[i] - b[i];
        }
        return a.length - b.length;
    };

    let best: number[] = [];
    for (let i = Math.max(0, k - m); i <= Math.min(k, n); i++) {
        const cand = merge(pickMax(nums1, i), pickMax(nums2, k - i));
        if (cmp(cand, best) > 0) best = cand;
    }
    return best;
}

Editorial#

Decomposing into “best subsequence per array” + “best merge” is the canonical reduction. pickMax is monotonic-stack with an explicit “drop budget” — we pop a smaller top only if we can afford to drop it (drop > 0). Merging is not a straight max-of-fronts because ties matter: when a[i] == b[j], the correct next digit is the one whose suffix is lex-larger, so we compare entire remaining segments.

Complexity#

Time: O(k · (n + m + k)²) — outer split × merge cost.
Space: O(k).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#