LeetCode Problem 321

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Stack, Greedy, Monotonic Stack

Solution

LeetCode 321 - Create Maximum Number

Problem Understanding

This problem asks us to build the lexicographically largest possible number of length k using digits taken from two arrays, nums1 and nums2.

Each array represents a sequence of digits from a number. We are allowed to choose some digits from nums1 and some digits from nums2, but we must preserve the original relative order of digits inside each individual array.

The key detail is that we are not rearranging digits arbitrarily. If we pick digits from nums1, they must appear in the same order as they originally appeared in nums1. The same rule applies to nums2.

The final result must contain exactly k digits.

For example:

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

One optimal selection is:

• Take [6,5] from nums1
• Take [9,8,3] from nums2

Then merge them carefully into:

[9,8,6,5,3]

which forms the largest possible number.

The constraints are important:

• m and n can each be up to 500
• k can be as large as m + n

This immediately tells us that brute force generation of all subsequences is impossible. The number of subsequences grows exponentially.

The problem combines several ideas:

• Greedy selection
• Monotonic stack
• Lexicographical comparison
• Careful merging

There are several edge cases that can easily break naive implementations:

• One array may contribute all digits while the other contributes none
• Many repeated digits may exist, making merge decisions tricky
• Two candidate sequences may share long equal prefixes
• Choosing the locally largest digit is not always globally optimal
• Arrays can already be decreasing, meaning no removals should happen

The problem guarantees:

• Digits are between 0 and 9
• k is always valid
• Arrays do not contain leading zeros as numbers, although internal zeros are allowed

Approaches

Brute Force Approach

The brute force idea is to generate every possible subsequence of every valid length from both arrays.

For every split:

take i digits from nums1
take k - i digits from nums2

we would:

1. Generate all subsequences of length i from nums1
2. Generate all subsequences of length k - i from nums2
3. Merge every pair
4. Keep the lexicographically largest result

This approach is correct because it explores every possible valid construction.

However, it is far too slow.

An array of length 500 has an enormous number of subsequences. Even generating all subsequences of length 250 is computationally impossible.

We need a more intelligent strategy.

Key Insight

The problem can be divided into three smaller greedy problems:

1. Pick the maximum subsequence of a fixed length from one array
2. Merge two subsequences into the largest possible result
3. Try every valid split between the two arrays

The critical insight is that the best subsequence of length t from one array can be found greedily using a monotonic decreasing stack.

When building a subsequence:

• If the current digit is larger than the previous chosen digit
• And we still have enough remaining digits
• Then removing the smaller digit improves the final number

This is exactly the same logic used in monotonic stack problems.

After extracting optimal subsequences from both arrays, we greedily merge them:

• At each step, compare the remaining suffixes
• Choose the larger suffix lexicographically

This ensures globally optimal merging.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Generates all subsequences
Optimal	O(k(m + n + k))	O(m + n + k)	Greedy subsequence extraction and lexicographical merge

Algorithm Walkthrough

Step 1: Iterate Through All Valid Splits

We try every possible way to divide the k digits between the two arrays.

If we take i digits from nums1, then we must take k - i digits from nums2.

The valid range is:

max(0, k - n) <= i <= min(k, m)

This guarantees we never request more digits than an array contains.

Step 2: Build the Maximum Subsequence from One Array

For a fixed length t, we greedily construct the largest subsequence using a monotonic stack.

We are allowed to discard:

len(nums) - t

digits.

As we scan the array:

1. While the stack is nonempty
2. The current digit is larger than the top
3. We still have removals available

we pop the smaller digit.

Then we push the current digit.

This ensures earlier positions contain the largest possible digits.

For example:

nums = [3,4,6,5]
t = 2

We can remove 2 digits.

Process:

Digit	Stack	Action
3	[3]	push
4	[4]	pop 3, push 4
6	[6]	pop 4, push 6
5	[6,5]	push

Result:

[6,5]

Step 3: Merge Two Subsequences

Now we merge two optimal subsequences.

The greedy rule is:

• Compare the remaining suffixes lexicographically
• Take from the larger suffix

Suppose:

a = [6,7]
b = [6,0,4]

At the first position:

[6,7] > [6,0,4]

because the second digit 7 > 0.

So we take from a.

This is crucial. Comparing only the current digit is insufficient.

Step 4: Keep the Best Overall Result

After generating a merged candidate for every split:

• Compare it lexicographically with the current best answer
• Keep the larger one

Eventually, the global maximum is found.

Why it works

The algorithm works because each stage is independently optimal.

The monotonic stack guarantees the lexicographically largest subsequence of a given length. The merge step guarantees the lexicographically largest possible interleaving of the two chosen subsequences. Trying every valid split guarantees that no valid construction is missed.

Together, these properties ensure the globally optimal answer.

Python Solution

from typing import List

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def max_subsequence(nums: List[int], length: int) -> List[int]:
            drop = len(nums) - length
            stack = []

            for digit in nums:
                while drop and stack and stack[-1] < digit:
                    stack.pop()
                    drop -= 1

                stack.append(digit)

            return stack[:length]

        def greater(nums1: List[int], i: int,
                    nums2: List[int], j: int) -> bool:
            
            while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
                i += 1
                j += 1

            if j == len(nums2):
                return True

            if i < len(nums1) and nums1[i] > nums2[j]:
                return True

            return False

        def merge(nums1: List[int], nums2: List[int]) -> List[int]:
            merged = []
            i = 0
            j = 0

            while i < len(nums1) or j < len(nums2):
                if greater(nums1, i, nums2, j):
                    merged.append(nums1[i])
                    i += 1
                else:
                    merged.append(nums2[j])
                    j += 1

            return merged

        m = len(nums1)
        n = len(nums2)

        best = []

        start = max(0, k - n)
        end = min(k, m)

        for i in range(start, end + 1):
            subseq1 = max_subsequence(nums1, i)
            subseq2 = max_subsequence(nums2, k - i)

            candidate = merge(subseq1, subseq2)

            if candidate > best:
                best = candidate

        return best

The implementation is divided into three helper functions.

The max_subsequence function constructs the largest subsequence of a specified length using a monotonic decreasing stack. The variable drop tracks how many digits can still be removed.

The greater function performs lexicographical comparison between suffixes. This is one of the most important parts of the solution. Simply comparing current digits would produce incorrect results when prefixes are equal.

The merge function greedily builds the final merged sequence. At every step, it chooses the sequence whose remaining suffix is larger.

The main loop iterates through every valid split between the two arrays. For each split:

• Compute optimal subsequences
• Merge them
• Update the best result

Because Python lists support lexicographical comparison directly, we can compare candidates using:

candidate > best

which keeps the code concise and clean.

Go Solution

func maxNumber(nums1 []int, nums2 []int, k int) []int {

	maxSubsequence := func(nums []int, length int) []int {
		drop := len(nums) - length
		stack := []int{}

		for _, digit := range nums {
			for drop > 0 && len(stack) > 0 && stack[len(stack)-1] < digit {
				stack = stack[:len(stack)-1]
				drop--
			}

			stack = append(stack, digit)
		}

		return stack[:length]
	}

	var greater func([]int, int, []int, int) bool

	greater = func(nums1 []int, i int, nums2 []int, j int) bool {

		for i < len(nums1) && j < len(nums2) && nums1[i] == nums2[j] {
			i++
			j++
		}

		if j == len(nums2) {
			return true
		}

		if i < len(nums1) && nums1[i] > nums2[j] {
			return true
		}

		return false
	}

	merge := func(nums1 []int, nums2 []int) []int {
		merged := []int{}
		i := 0
		j := 0

		for i < len(nums1) || j < len(nums2) {
			if greater(nums1, i, nums2, j) {
				merged = append(merged, nums1[i])
				i++
			} else {
				merged = append(merged, nums2[j])
				j++
			}
		}

		return merged
	}

	maxLex := func(a []int, b []int) bool {
		for i := 0; i < len(a) && i < len(b); i++ {
			if a[i] != b[i] {
				return a[i] > b[i]
			}
		}
		return len(a) > len(b)
	}

	m := len(nums1)
	n := len(nums2)

	best := []int{}

	start := max(0, k-n)
	end := min(k, m)

	for i := start; i <= end; i++ {
		subseq1 := maxSubsequence(nums1, i)
		subseq2 := maxSubsequence(nums2, k-i)

		candidate := merge(subseq1, subseq2)

		if len(best) == 0 || maxLex(candidate, best) {
			best = candidate
		}
	}

	return best
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version but requires explicit helper functions for lexicographical comparison because slices cannot be compared directly.

Go slices are dynamic views over arrays, so stack operations are implemented using slicing syntax:

stack = stack[:len(stack)-1]

Unlike Python, Go does not provide built in lexicographical comparison for slices, so the maxLex helper function performs element by element comparison manually.

Integer overflow is not a concern because all digits are between 0 and 9.

Worked Examples

Example 1

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

Valid splits:

nums1 digits	nums2 digits
0	5
1	4
2	3
3	2
4	1

Consider split:

2 from nums1
3 from nums2

Build max subsequence from nums1:

Step	Digit	Stack
1	3	[3]
2	4	[4]
3	6	[6]
4	5	[6,5]

Result:

[6,5]

Build max subsequence from nums2:

Step	Digit	Stack
1	9	[9]
2	1	[9,1]
3	2	[9,2]
4	5	[9,5]
5	8	[9,8]
6	3	[9,8,3]

Merge:

Remaining A	Remaining B	Pick
[6,5]	[9,8,3]	9
[6,5]	[8,3]	8
[6,5]	[3]	6
[5]	[3]	5
[]	[3]	3

Final:

[9,8,6,5,3]

Example 2

nums1 = [6,7]
nums2 = [6,0,4]
k = 5

We must take every digit.

Merge process:

Remaining A	Remaining B	Pick
[6,7]	[6,0,4]	6 from A
[7]	[6,0,4]	7
[]	[6,0,4]	6
[]	[0,4]	0
[]	[4]	4

Result:

[6,7,6,0,4]

Example 3

nums1 = [3,9]
nums2 = [8,9]
k = 3

Possible split:

1 from nums1
2 from nums2

Best subsequences:

[9]
[8,9]

Merge:

Remaining A	Remaining B	Pick
[9]	[8,9]	9
[]	[8,9]	8
[]	[9]	9

Final:

[9,8,9]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k(m + n + k))	Try all splits, build subsequences, merge results
Space	O(m + n + k)	Stacks and merged candidates

For each possible split, we:

• Build one subsequence from nums1
• Build one subsequence from nums2
• Merge sequences of total length k

There are at most k + 1 splits.

Each subsequence extraction is linear, and merging can require lexicographical suffix comparisons, leading to the additional k factor.

Given the constraints of at most 500, this solution is efficient enough.

Test Cases

from typing import List

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def max_subsequence(nums: List[int], length: int) -> List[int]:
            drop = len(nums) - length
            stack = []

            for digit in nums:
                while drop and stack and stack[-1] < digit:
                    stack.pop()
                    drop -= 1

                stack.append(digit)

            return stack[:length]

        def greater(nums1, i, nums2, j):
            while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
                i += 1
                j += 1

            if j == len(nums2):
                return True

            if i < len(nums1) and nums1[i] > nums2[j]:
                return True

            return False

        def merge(nums1, nums2):
            result = []
            i = 0
            j = 0

            while i < len(nums1) or j < len(nums2):
                if greater(nums1, i, nums2, j):
                    result.append(nums1[i])
                    i += 1
                else:
                    result.append(nums2[j])
                    j += 1

            return result

        best = []

        for i in range(max(0, k - len(nums2)),
                       min(k, len(nums1)) + 1):

            candidate = merge(
                max_subsequence(nums1, i),
                max_subsequence(nums2, k - i)
            )

            if candidate > best:
                best = candidate

        return best

solution = Solution()

assert solution.maxNumber(
    [3,4,6,5],
    [9,1,2,5,8,3],
    5
) == [9,8,6,5,3]  # official example 1

assert solution.maxNumber(
    [6,7],
    [6,0,4],
    5
) == [6,7,6,0,4]  # official example 2

assert solution.maxNumber(
    [3,9],
    [8,9],
    3
) == [9,8,9]  # official example 3

assert solution.maxNumber(
    [9,1,2],
    [3,4],
    2
) == [9,4]  # choose best across both arrays

assert solution.maxNumber(
    [5,5,1],
    [5,5,2],
    4
) == [5,5,5,5]  # repeated digits

assert solution.maxNumber(
    [8,9],
    [3,9],
    3
) == [9,8,9]  # tie handling during merge

assert solution.maxNumber(
    [1,2,3],
    [4,5,6],
    6
) == [4,5,6,1,2,3]  # take all digits

assert solution.maxNumber(
    [9,8,7],
    [6,5,4],
    3
) == [9,8,7]  # all digits from one array

assert solution.maxNumber(
    [0,0,0],
    [0,0],
    4
) == [0,0,0,0]  # all zeros

assert solution.maxNumber(
    [2,5,6,4,4,0],
    [7,3,8,0,6,5,7,6,2],
    15
) == [7,3,8,2,5,6,4,4,0,6,5,7,6,2,0]  # large mixed case

Test Summary

Test	Why
Official example 1	Standard mixed selection
Official example 2	Must take all digits
Official example 3	Lexicographical merge tie
Small mixed arrays	Cross array optimization
Repeated digits	Equal prefix handling
Tie during merge	Correct suffix comparison
k = m + n	No removals allowed
All from one array	Valid extreme split
All zeros	Zero handling
Large mixed case	Stress test for greedy logic

Edge Cases

Edge Case 1: All Digits Come from One Array

Consider:

nums1 = [9,8,7]
nums2 = [1,2,3]
k = 3

The optimal solution ignores nums2 entirely.

A buggy implementation might incorrectly force usage from both arrays. Our implementation correctly iterates through every valid split, including taking all digits from a single array.

Edge Case 2: Equal Prefixes During Merge

Consider:

nums1 = [6,7]
nums2 = [6,0,4]

At the first position both arrays begin with 6.

If we only compare current digits, the choice becomes ambiguous and may produce the wrong answer.

Our implementation compares the entire remaining suffix lexicographically, which correctly determines that:

[6,7] > [6,0,4]

because 7 > 0.

Edge Case 3: Repeated Digits

Consider:

nums1 = [5,5,1]
nums2 = [5,5,2]

Repeated digits are difficult because many local decisions appear equivalent.

The suffix comparison logic ensures that when prefixes match, the algorithm continues comparing deeper positions until it finds a difference.

This guarantees the globally optimal merge.

Edge Case 4: Strictly Decreasing Arrays

Consider:

nums1 = [9,8,7,6]

The monotonic stack never pops elements because every next digit is smaller.

A buggy implementation might over remove digits or mishandle the remaining removal count.

Our implementation safely preserves the best prefix and truncates only if necessary using:

stack[:length]

which guarantees the correct subsequence length.