Create Maximum Number

Hard
1457.

Create Maximum Number

Create Maximum Number is a hard coding problem on arrays, greedy and stack, asked in Amazon and Google interviews.

Two arrays nums1 and nums2 hold the digits of two numbers (each element is a digit 0–9). Pick exactly k digits in total from the two arrays and line them up into a new number. The digits taken from the same array must keep their original relative order; digits from the two arrays may be interleaved freely.

Return the largest number you can build, as an array of its k digits.

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]
Explanation
All five digits are used; starting with `nums1`'s 6 lets the 7 come second.

Example 3

Input
nums1 = [2,8,1], nums2 = [7,3,9], k = 3
Output
[9,8,1]
Explanation
Take the 9 from `nums2` first, then 8 and 1 from `nums1`.

Constraints

  • m == nums1.length
  • n == nums2.length
  • 1 <= m, n <= 500
  • 0 <= nums1[i], nums2[i] <= 9
  • 1 <= k <= m + n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var maxNumber = function(nums1, nums2, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Create Maximum Number — Solution in Python, Java & C++

Create Maximum Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and greedy.

Create Maximum Number is a hard coding problem on arrays, greedy and stack, asked in Amazon and Google interviews.

Problem statement

Two arrays nums1 and nums2 hold the digits of two numbers (each element is a digit 0–9). Pick exactly k digits in total from the two arrays and line them up into a new number. The digits taken from the same array must keep their original relative order; digits from the two arrays may be interleaved freely.

Return the largest number you can build, as an array of its k digits.

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]
Explanation: All five digits are used; starting with `nums1`'s 6 lets the 7 come second.

Example 3

Input: nums1 = [2,8,1], nums2 = [7,3,9], k = 3
Output: [9,8,1]
Explanation: Take the 9 from `nums2` first, then 8 and 1 from `nums1`.

Constraints

  • m == nums1.length
  • n == nums2.length
  • 1 <= m, n <= 500
  • 0 <= nums1[i], nums2[i] <= 9
  • 1 <= k <= m + n

Hints for Create Maximum Number

  1. Hint 1

    Split the job: take s digits from nums1 and k - s from nums2, for every feasible s.

  2. Hint 2

    The best t digits of a single array, in order, come from a monotonic stack: pop a smaller top while you can still afford to drop digits.

  3. Hint 3

    Merge the two picks like merge sort, but when the heads are equal compare the remaining suffixes to decide which array to take from. Keep the best merged result over all s.

How to solve Create Maximum Number

Any answer takes some s digits from nums1 and k - s from nums2. For a fixed s, the best choice from each array is its lexicographically largest subsequence of that length, and the best interleaving of two sequences is a greedy merge that compares suffixes.

Approach

  1. For s from max(0, k - n) to min(k, m):
  2. Pick the largest length-s subsequence of nums1 with a stack: for each digit, while digits may still be dropped and the top is smaller, pop; then push. Keep the first s. Do the same for nums2 with k - s.
  3. Merge: repeatedly take the head of the sequence whose remaining suffix is lexicographically larger (a suffix that is a prefix of the other counts as smaller).
  4. Keep the largest merged array over all s and return it.

Why it works

Fix how many digits come from each array. The merged number is maximised by maximising each part (a lexicographically larger part can never yield a smaller merge), and the stack produces the largest subsequence of a given length because each pop replaces a digit by a larger one at an earlier position. In the merge, comparing whole suffixes on a tie picks the array whose next differing digit is larger, which can only be reached sooner by taking from it first.

Complexity

  • Time — O(k · (m + n)^2) in the worst case
  • Space — O(m + n)

Pitfalls

  • On equal heads, comparing only the next digit is not enough — compare the full remaining suffixes (e.g. [6,7] vs [6,0,4]).
  • The range of s is limited by both lengths: max(0, k - n) <= s <= min(k, m).
  • In the stack, track how many digits may still be dropped; stop popping when that runs out.

Reference solution

Python

from typing import List

def maxNumber(nums1: List[int], nums2: List[int], k: int) -> List[int]:
    def pick(a, t):
        st = []
        drop = len(a) - t
        for x in a:
            while drop > 0 and st and st[-1] < x:
                st.pop()
                drop -= 1
            st.append(x)
        return st[:t]

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

    m, n = len(nums1), len(nums2)
    best = []
    for s in range(max(0, k - n), min(k, m) + 1):
        cand = merge(pick(nums1, s), pick(nums2, k - s))
        if cand > best:
            best = cand
    return best

Java

private static int[] pickMaxMN(int[] a, int t) {
    int[] st = new int[a.length];
    int top = 0, drop = a.length - t;
    for (int x : a) {
        while (drop > 0 && top > 0 && st[top - 1] < x) { top--; drop--; }
        st[top++] = x;
    }
    return Arrays.copyOf(st, t);
}

private static boolean greaterMN(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]);
}

public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int m = nums1.length, n = nums2.length;
    int[] best = new int[0];
    for (int s = Math.max(0, k - n); s <= Math.min(k, m); s++) {
        int[] a = pickMaxMN(nums1, s), b = pickMaxMN(nums2, k - s);
        int[] cand = new int[k];
        int i = 0, j = 0, p = 0;
        while (i < a.length || j < b.length) {
            if (greaterMN(a, i, b, j)) cand[p++] = a[i++];
            else cand[p++] = b[j++];
        }
        if (greaterMN(cand, 0, best, 0)) best = cand;
    }
    return best;
}

C++

static vector<int> pickMaxMN(const vector<int>& a, int t) {
    vector<int> st;
    int drop = (int)a.size() - t;
    for (int x : a) {
        while (drop > 0 && !st.empty() && st.back() < x) { st.pop_back(); drop--; }
        st.push_back(x);
    }
    st.resize(t);
    return st;
}

static bool greaterMN(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++; }
    return j == (int)b.size() || (i < (int)a.size() && a[i] > b[j]);
}

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    int m = nums1.size(), n = nums2.size();
    vector<int> best;
    for (int s = max(0, k - n); s <= min(k, m); s++) {
        vector<int> a = pickMaxMN(nums1, s), b = pickMaxMN(nums2, k - s);
        vector<int> cand;
        int i = 0, j = 0;
        while (i < (int)a.size() || j < (int)b.size()) {
            if (greaterMN(a, i, b, j)) cand.push_back(a[i++]);
            else cand.push_back(b[j++]);
        }
        if (greaterMN(cand, 0, best, 0)) best = cand;
    }
    return best;
}

JavaScript

var maxNumber = function(nums1, nums2, k) {
    var pickMax = function(a, t) {
        var st = [], drop = a.length - t;
        for (var i = 0; i < a.length; i++) {
            while (drop > 0 && st.length > 0 && st[st.length - 1] < a[i]) { st.pop(); drop--; }
            st.push(a[i]);
        }
        return st.slice(0, t);
    };
    var greater = function(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]);
    };
    var merge = function(a, b) {
        var res = [], i = 0, j = 0;
        while (i < a.length || j < b.length) {
            if (greater(a, i, b, j)) res.push(a[i++]);
            else res.push(b[j++]);
        }
        return res;
    };
    var m = nums1.length, n = nums2.length;
    var best = [];
    for (var s = Math.max(0, k - n); s <= Math.min(k, m); s++) {
        var cand = merge(pickMax(nums1, s), pickMax(nums2, k - s));
        if (greater(cand, 0, best, 0)) best = cand;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms