Create Maximum Number

Hard Monotonic Stack Monotonic Stack Original on LeetCode

Reported atFlipkart

Create Maximum Number is a hard monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (monotonic stack + greedy merge), runs in O(k · (m + n + k²)) time and O(m + n + k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (window scans for each split) up.

Problem

You are given two arrays of single digits, nums1 of length m and nums2 of length n, each standing for the digits of a number. You are also given an integer k with k <= m + n.

Build the largest possible number of exactly k digits using digits from both arrays. Digits taken from the same array must keep their original relative order, but digits from the two arrays can be interleaved freely.

Return the result as an array of its k digits.

Examples

Example 1

Input
nums1 = [4, 9, 1], nums2 = [7, 2, 8], k = 4
Output
[9, 7, 8, 1]
Why
Take 9, 1 from nums1 and 7, 8 from nums2 and interleave them. Taking only 9 from nums1 would force 7, 2, 8 and give the smaller 9, 7, 2, 8.

Example 2

Input
nums1 = [3, 8], nums2 = [3, 1, 5], k = 5
Output
[3, 8, 3, 1, 5]
Why
Every digit is used. Both arrays start with 3; taking nums1's 3 first lets its 8 come next, which beats 3, 3, 8, 1, 5.

Example 3

Input
nums1 = [2, 0], nums2 = [1], k = 3
Output
[2, 1, 0]
Why
All digits must be used; interleaving them as 2, 1, 0 beats 2, 0, 1 and 1, 2, 0.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (window scans for each split)O(k · (m + n) · k)O(k)
Optimal (monotonic stack + greedy merge)O(k · (m + n + k²))O(m + n + k)

1Brute force (window scans for each split)

TimeO(k · (m + n) · k)For each of up to k + 1 splits, each picked digit scans up to m or n values, and the merge costs up to k² in the worst case.
SpaceO(k)The two picked sequences and the merged candidate.

For every split (i digits from nums1, k - i from nums2), build the largest subsequence of each array by picking digits one at a time: the next digit is the largest value in the window that still leaves enough digits after it. Merge the two picks greedily and keep the best result.

  1. For i from max(0, k - n) to min(k, m): a = pick(nums1, i), b = pick(nums2, k - i).
  2. pick(arr, t): for each of the t positions, scan arr[start .. len - remaining] for the first maximum, take it and continue after it.
  3. Merge a and b: repeatedly take from the sequence whose remaining suffix is larger.
  4. Keep the lexicographically largest merged array.
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[] best = new int[k];
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
            int[] cand = merge(pick(nums1, i), pick(nums2, k - i));
            if (greater(cand, 0, best, 0)) best = cand;
        }
        return best;
    }

    private int[] pick(int[] arr, int t) {
        int[] res = new int[t];
        int start = 0;
        for (int p = 0; p < t; p++) {
            int last = arr.length - (t - p);
            int bestIdx = start;
            for (int j = start; j <= last; j++) {
                if (arr[j] > arr[bestIdx]) bestIdx = j;
            }
            res[p] = arr[bestIdx];
            start = bestIdx + 1;
        }
        return res;
    }

    private int[] merge(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0, j = 0;
        for (int p = 0; p < res.length; p++) {
            res[p] = greater(a, i, b, j) ? a[i++] : b[j++];
        }
        return res;
    }

    private 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]);
    }
}

2Optimal (monotonic stack + greedy merge)

TimeO(k · (m + n + k²))Each split costs O(m + n) to build both subsequences and at most O(k²) to merge (ties are usually short, so it is close to O(k) in practice).
SpaceO(m + n + k)The stacks and the merged candidate.

Same split-and-merge plan, but each best subsequence is built in one pass with a decreasing stack: while the incoming digit is larger than the top and there are still digits we are allowed to drop (len - t in total), pop the top. Push the digit if the stack holds fewer than t digits. The merge is unchanged: on a tie, the sequence with the larger remaining suffix goes first.

  1. For i from max(0, k - n) to min(k, m): a = maxSubsequence(nums1, i), b = maxSubsequence(nums2, k - i).
  2. maxSubsequence(arr, t): drop = arr.length - t; for each digit, pop while drop > 0 and the top is smaller (drop--), then push if the stack has fewer than t digits.
  3. Merge a and b by comparing suffixes, and keep the largest merged array.
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[] best = new int[k];
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
            int[] cand = merge(maxSubsequence(nums1, i), maxSubsequence(nums2, k - i));
            if (greater(cand, 0, best, 0)) best = cand;
        }
        return best;
    }

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

    private int[] merge(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0, j = 0;
        for (int p = 0; p < res.length; p++) {
            res[p] = greater(a, i, b, j) ? a[i++] : b[j++];
        }
        return res;
    }

    private 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]);
    }
}

Edge cases to test

  • k equals m + n: every digit is used and only the merge order matters
  • All digits taken from one array
  • Equal digits at the front of both sequences during the merge: look further ahead to break the tie
  • Many zeros and repeated digits

Hints

Hint 1

Fix how many digits i come from nums1; the other k - i come from nums2. Try every valid i.

Hint 2

For a fixed count, the best subsequence of one array is found greedily with a monotonic stack (drop a smaller top while you can still afford to drop digits).

Hint 3

Merging two sequences is like merge sort, but on a tie compare the remaining suffixes and take from the larger one.

FAQ

What is the best time complexity for Create Maximum Number?

Optimal (monotonic stack + greedy merge) runs in O(k · (m + n + k²)) time and O(m + n + k) extra space. Each split costs O(m + n) to build both subsequences and at most O(k²) to merge (ties are usually short, so it is close to O(k) in practice).

Which pattern does Create Maximum Number use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Create Maximum Number?

Yes. Brute force (window scans for each split) takes O(k · (m + n) · k) time and O(k) space. For every split (i digits from nums1, k - i from nums2), build the largest subsequence of each array by picking digits one at a time: the next digit is the largest value in the window that still leaves enough digits after it.

Which edge cases should I test for Create Maximum Number?

k equals m + n: every digit is used and only the merge order matters; All digits taken from one array; Equal digits at the front of both sequences during the merge: look further ahead to break the tie; Many zeros and repeated digits.