AlgoInsight

DSA problem

Create Maximum Number

HardMonotonic StackPattern: Monotonic Stacktop600GoogleAmazonMicrosoftBloomberg

You are given two integer arrays nums1 and nums2 of lengths m and n representing the digits of two numbers. You are also given an integer k. Create the maximum number of length k (where k <= m + n) from digits of the two numbers, preserving the relative order of digits within each input array. Return the answer as an array of k digits representing the number.

The problem decomposes nicely. For each split k1 + k2 = k with 0 <= k1 <= m and 0 <= k2 <= n:

  1. Pick the maximum-valued subsequence of length k1 from nums1 (preserving relative order). This is a classic "monotonic non-increasing stack" task: build a stack of digits while allowing m - k1 removals; whenever the current digit is greater than the stack's top and removals remain, pop.
  2. Pick the maximum-valued subsequence of length k2 from nums2 the same way.
  3. Merge the two subsequences greedily into a length-k sequence by always taking the digit that produces a lexicographically larger remaining tail.

Among all candidate splits, return the lexicographically maximum result. The greedy merge needs a careful tie-breaker: when the two heads have the same digit, compare the remainders of the two arrays lexicographically and take from the side whose remainder is larger.

The overall complexity is O((m + n)² * k) or thereabouts, dominated by the merges across all valid splits. For the given constraints this is comfortably fast.

Examples

Example 1
Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]
Explanation: Choose subsequences [6,5] from nums1 and [9,8,3] from nums2; merging them lexicographically maximally gives [9,8,6,5,3].
Example 2
Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]
Explanation: We must use all 5 available digits, so both arrays contribute everything; merging gives [6,7,6,0,4].
Example 3
Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]
Explanation: Take [9] from nums1 and [8,9] from nums2; merge to [9,8,9].

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

monotonic-stackstackgreedyarray

Browse all DSA problems