Is Create Maximum Number easy or hard?

Create Maximum Number is classified as a hard problem on most coding platforms. The difficulty comes from combining multiple techniques: greedy selection, monotonic stacks, subsequence extraction, and lexicographic merging. Implementing the merge comparison correctly is often the trickiest part.

How to solve Create Maximum Number in O(n)?

A pure O(n) solution does not exist because the algorithm must evaluate multiple splits between the two arrays. The closest efficient approach is the greedy monotonic stack method, which extracts optimal subsequences in O(n) time per array and merges them. The overall complexity becomes roughly O((m+n)*k).

What is the best approach for Create Maximum Number?

The best approach uses a greedy strategy with a monotonic decreasing stack. First extract the maximum subsequence of a given length from each array, then merge the two sequences by always choosing the lexicographically larger remaining suffix. By trying every split of k digits between the arrays, this method guarantees the optimal result with about O((m+n)*k) time complexity.

Is Create Maximum Number asked at Google/Amazon/Meta?

Create Maximum Number is a classic hard interview problem frequently associated with companies like Google and Meta. It tests advanced greedy reasoning, lexicographical comparison, and stack-based subsequence extraction. Candidates are expected to combine multiple algorithmic techniques in one solution.

What data structure is used in Create Maximum Number?

The key data structure is a monotonic stack used to construct the largest possible subsequence from each array. During iteration, smaller digits are popped while removals are allowed so that larger digits can appear earlier in the final sequence. Array comparisons are then used during the merge step.

What is the time complexity of Create Maximum Number?

The optimal greedy solution runs in O((m+n)*k) time. For each possible split of k digits between the two arrays, you compute maximum subsequences in linear time and merge them in O(k). Space complexity is O(m+n) to store intermediate subsequences.

Create Maximum Number Python or Java solution approach?

Python and Java implementations typically follow the greedy monotonic stack approach. A helper function extracts the maximum subsequence from each array, and another function merges two sequences by comparing their remaining suffixes. The logic is identical across languages, differing mainly in syntax.

Description Solution Video 10:14

321. Create Maximum Number

Hard37.3% acceptance7 companies

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

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]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

Constraints:

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n
nums1 and nums2 do not have leading zeros.

Asked at 7 companies

Flipkart Accolite

Google Oracle Amazon Microsoft Bloomberg

Topics

10:14

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

321. Create Maximum Number

Asked at 7 companies

Topics

Similar problems