LESSON 336 OF 441 · STACK

Create Maximum Number in C#: Monotonic Stack and Merge

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

STEP 1 OF 28

Guided

Ctrl + Enter to check

C# · STACK

Create Maximum Number in C#, explained

Problem overview

The method MaxNumber receives two int[] arrays, nums1 and nums2, whose items are digits from 0 to 9, and an int named k with 1 <= k <= m + n. It must pick k digits from the two arrays so that the number they form is as large as possible, and return those digits as an int[]. The digits taken from one array must keep their original relative order, but digits from the two arrays can be interleaved freely. Each array has up to 500 digits.

With nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3] and k = 5, the answer is [9, 8, 6, 5, 3]. With [6, 7], [6, 0, 4] and k = 5, every digit is used and the answer is [6, 7, 6, 0, 4]. With [3, 9], [8, 9] and k = 3, it is [9, 8, 9].

Approach: split, shrink each side, merge

An answer takes i digits from nums1 and k - i from nums2, for some i. Trying every i from 0 to k covers all answers. For one fixed split, the problem breaks into three smaller ones:

Find the largest number of i digits that can be kept from nums1, in order.
Find the same for k - i digits of nums2.
Merge the two results into the largest possible number of k digits, each side keeping its order.

Then the best candidate over all splits is the answer. Two candidates always have k digits, so comparing them as numbers is the same as comparing them digit by digit from the left.

Largest subsequence of a given size. Read the digits left to right and keep them on a stack. When a digit is bigger than the top, dropping the top moves the bigger digit one place left, which makes the number larger, so pop the top. The pop is allowed only while enough digits remain to still fill the stack to size.

For [9, 1, 2, 5, 8, 3] and size 3: 9 is pushed, 1 is pushed, then 2 pops 1, 5 pops 2, 8 pops 5, and 3 is pushed on top of 8. The result is [9, 8, 3].

Merging. The next digit should come from the array whose remaining part is greater. Comparing only the two next digits is not enough when they are equal. For [6, 7] and [6, 0, 4], both start with 6. Taking the 6 from the second array first gives [6, 6, 7, 0, 4], while taking it from the first gives the larger [6, 7, 6, 0, 4]. Comparing everything that remains, [6, 7] against [6, 0, 4], shows that the first is greater, because 7 beats 0 at the first difference.

On the first example, the splits give the candidates [9, 2, 5, 8, 3] (0 digits from nums1), [9, 6, 5, 8, 3], [9, 8, 6, 5, 3], [9, 8, 4, 6, 5] and [9, 3, 4, 6, 5] (4 digits from nums1). The third is the largest.

Step by step

Start with best as an empty int[], new int[0]. Any candidate beats it.
Loop i from 0 to k inclusive. It is the number of digits taken from nums1.
Skip impossible splits. Require i <= nums1.Length and k - i <= nums2.Length.
Shrink each side with MaxSubsequence(nums1, i) into first and MaxSubsequence(nums2, k - i) into second.
Merge them into candidate with Merge(first, second).
Keep the larger. If IsGreater(candidate, 0, best, 0), replace best with candidate. The two zeros mean that both comparisons start at index 0.
Return best after the loop.
Declare MaxSubsequence(int[] nums, int size) as a private helper that returns an int[].
Create the stack: an int[] called stack of length size, and count, how many digits it holds. The top is stack[count - 1].
Loop over the indices of nums. The index tells how many digits are still to come.
Pop while it helps. A while loop runs as long as count > 0, the top is smaller than nums[i], and count + nums.Length - i > size. The last condition says the digits not yet read, including this one, plus the digits that stay on the stack after the pop, still make size.
Pop by decreasing count. The old digit stays in the array until the next push overwrites it.
Push if there is room. If count < size, store nums[i] at stack[count] and increase count. A digit that finds the stack full is dropped.
Return stack.
Declare Merge(int[] a, int[] b), another private helper returning int[], and create result with length a.Length + b.Length.
Keep two indices, i into a and j into b, both 0.
Loop while either array has digits left: i < a.Length || j < b.Length. Each turn places exactly one digit.
Choose by the remainders. If IsGreater(a, i, b, j), store a[i] at result[i + j] and advance i. Otherwise store b[j] at result[i + j] and advance j. Exactly i + j digits are placed so far, so the next goes at index i + j.
Return result.
Declare IsGreater(int[] a, int i, int[] b, int j) returning bool. It tells whether a from index i is greater than b from index j.
Skip equal digits: a while loop advances both indices while both arrays have digits and a[i] == b[j].
Decide at the first difference. Return whether b ran out, or a still has a digit that is bigger than b[j].

The solution in C#

class Solution {
    public int[] MaxNumber(int[] nums1, int[] nums2, int k) {
        int[] best = new int[0];
        for (int i = 0; i <= k; i++) {
            if (i <= nums1.Length && k - i <= nums2.Length) {
                int[] first = MaxSubsequence(nums1, i);
                int[] second = MaxSubsequence(nums2, k - i);
                int[] candidate = Merge(first, second);
                if (IsGreater(candidate, 0, best, 0)) {
                    best = candidate;
                }
            }
        }
        return best;
    }
    private int[] MaxSubsequence(int[] nums, int size) {
        int[] stack = new int[size];
        int count = 0;
        for (int i = 0; i < nums.Length; i++) {
            while (count > 0 && stack[count - 1] < nums[i] && count + nums.Length - i > size) {
                count--;
            }
            if (count < size) {
                stack[count] = nums[i];
                count++;
            }
        }
        return stack;
    }
    private int[] Merge(int[] a, int[] b) {
        int[] result = new int[a.Length + b.Length];
        int i = 0, j = 0;
        while (i < a.Length || j < b.Length) {
            if (IsGreater(a, i, b, j)) {
                result[i + j] = a[i];
                i++;
            } else {
                result[i + j] = b[j];
                j++;
            }
        }
        return result;
    }
    private bool IsGreater(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]);
    }
}

The C# details worth knowing:

Arrays as stacks. The int[] has a fixed length, so count marks the top. A pop only lowers count, and the next push overwrites the old digit. The returned array always has exactly size digits: the pop condition keeps enough digits available to fill it.
new int[0] is a valid empty array. MaxSubsequence(nums, 0) returns one, and Merge then returns a copy of the other side's digits.
Parameters are local copies. IsGreater advances its own i and j without affecting the caller's variables. Only the arrays are shared references, and the method never writes to them.
Short-circuit || and &&. In IsGreater, j == b.Length is checked first, so b[j] is read only when it exists. In the second part, i < a.Length comes before a[i]. C# arrays are bounds-checked, so an out-of-range read would throw IndexOutOfRangeException.
Empty sides in IsGreater. With b empty, j == b.Length is true at once, so any candidate beats the initial best. With a used up and b not, the result is false, so Merge takes from b.
Equal arrays. When all compared digits are equal and b runs out first or at the same time, IsGreater returns true. In Merge this means ties are broken toward a, which gives the same number either way.

Complexity

Let m and n be the lengths of the arrays.

Time. There are at most k + 1 splits. For each split, the two MaxSubsequence calls take O(m + n) in total: each digit is pushed at most once and popped at most once. Merge places k digits, and each IsGreater call may scan up to k digits when the remainders start with long equal runs, so one merge costs O(k²) in the worst case. Comparing the candidate with best costs O(k). The total is at most O(k × (m + n + k²)); it is much smaller when the digits differ early, since the comparisons then stop quickly.

Space: O(m + n). Each split allocates arrays of at most k digits, and best holds k more.

Edge cases and common mistakes

Taking all digits. With k = m + n, only the split i = m is possible, and the problem reduces to the merge. [6, 7] and [6, 0, 4] gives [6, 7, 6, 0, 4].
Splits that don't fit. For [3, 9], [8, 9], k = 3, the candidates are [9, 8, 9] (one digit from nums1) and [9, 3, 9] (two digits). The splits that would need three digits from one array are skipped because neither array has three.
Merging by the next digit only. For [6, 7] and [6, 0, 4], that choice gives [6, 6, 7, 0, 4], which is smaller than [6, 7, 6, 0, 4].
Popping without the remaining-digits check. The stack could end up shorter than size, with zeros in its unused cells. The count + nums.Length - i > size test prevents that.
Zeros. The digits can be 0, so the answer may contain zeros, even at the front: [0, 0] and [0] with k = 2 gives [0, 0]. The result is an array of digits, so no leading zero is lost.

Testing

[3, 4, 6, 5], [9, 1, 2, 5, 8, 3], k = 5 gives [9, 8, 6, 5, 3].
[6, 7], [6, 0, 4], k = 5 gives [6, 7, 6, 0, 4].
[3, 9], [8, 9], k = 3 gives [9, 8, 9].
[1], [2], k = 1 gives [2].
[0, 0], [0], k = 2 gives [0, 0].

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free