321. Create Maximum Number

HardStackGreedyMonotonic Stack
Leetcode Link

Problem Description

You are tasked with creating the largest possible number by selecting k digits from two given integer arrays nums1 and nums2, where nums1 has a length m and nums2 has a length n. The number that you form must have the digits in the same relative order as they appear in their original arrays. The value k satisfies the condition k <= m + n, meaning the number of digits you select cannot be more than the total number of digits in both arrays combined.

Intuition

To solve this problem, we must break it down into smaller, manageable steps:

  1. The core idea is to find the maximum number from each array by selecting x digits from nums1 and k-x digits from nums2, where x ranges from max(0, k - n) to min(k, m). This implies that x needs to be in the range where it's valid for both arrays, considering their lengths.

  2. To get the maximum possible digits from a single array, we use a greedy approach with a stack. The function f(nums, k) in the solution uses a stack to build the maximum number of length k from an array nums. It goes through the digits of nums and ensures that:

    • If the current digit is greater than the top of the stack and we still have more digits than we need (remain > 0), we pop from the stack.
    • We maintain a remain counter which allows us to discard digits we do not need, aiming to have exactly k digits in the stack.
    • We keep the stack filled up to k by pushing the current digit into it if not full.

  3. Once we have the maximum digits from both arrays, we merge them into the largest possible number using the merge(nums1, nums2) function. This merge part maintains the relative order of the digits from both arrays.

  4. The merging is done by comparing the digits available to be merged: we take one digit at a time and pick the larger of the two unless they are equal. If they are equal, we look ahead and choose the digit from the number that has a larger following digit (compare(nums1, nums2, i, j)). This effectively ensures we are always picking the larger number that can be formed.

  5. To get the final answer, we iterate over all valid x and merge the respective maximum numbers possible, then compare them to find the best (maximum) combination of digits to form the actual largest number.

The given solution combines all these elements into a comprehensive algorithm to solve the problem. It finely balances between a greedy approach and careful selection to construct the largest number while adhering to the constraints imposed by the order of digits in the given arrays.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The solution uses a combination of greedy strategy and dynamic programming to approach this problem. Several key algorithms and patterns are applied in the solution code:

  1. Greedy stack-based approach for subarray maximum: The f(nums, k) function implements a greedy strategy with a stack to select k digits from a given array nums while preserving their order to form the maximum possible number. It uses a stack (stk) where each insertion is done using the following logic:

    • While the stack is not empty, the top of the stack is less than the current element (stk[top] < x), and there are more elements remaining to consider (remain > 0), the top element is removed. This ensures only the largest elements are retained in the final selection.
    • An element is pushed to the stack if there is room (top + 1 < k), which represents potential digits for our final answer.
    • The remain count is a balance to maintain the proper number of digits. It's reduced whenever an element is not used.

  2. Comparison function for lexicographical order: The compare(nums1, nums2, i, j) function determines which of two sequences will lead to a larger number if we start merging from them. The function is based on lexicographical comparison: it starts comparing digit by digit and keeps on going until it finds a larger digit or reaches the end of one array. This is a essential for properly merging two arrays to form the largest number.

  3. Merging two sequences preserving order: The merge(nums1, nums2) function is used to merge two sequences into the largest possible number while preserving the original relative order of digits within nums1 and nums2. This function uses compare to choose the larger value at each step of the merge.

  4. Dynamic programming to test different combinations: The solution iterates over all valid values of x, where x is the number of digits taken from nums1 and k-x from nums2. By using the functions f(nums1, x) and f(nums2, k-x) for generating the two maximum numbers (with x and k-x digits respectively) and then using the merge function, the code tests all possible combinations to create the largest number of length k.

  5. Use of a simple for loop to find the best combination: A for loop ranging from l to r (for x in range(l, r + 1)) serves to generate all valid arr1 and arr2 combinations and then merges them. The loop constructs and compares the different combinations to keep track of the overall maximum (ans).

The solution uses immensely crucial data structures, like the stack, which greatly simplifies adding and removing elements while maintaining the maximum digit ordering. It also heavily relies on the recursion (in compare) to handle the comparison of the two sequences, and structural iteration to check each possible combination for the most optimal result.

Each function is dedicated to a specific part of the problem, modularizing the code and making the overall approach quite robust and efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's illustrate the solution approach with a simple example. Consider the two integer arrays nums1 = [3, 4, 6] and nums2 = [9, 1, 2], and let k = 5 (we want to create the largest possible number by selecting k digits from nums1 and nums2).

1. Greedy stack-based approach for subarray maximum

  • For x = 2 (selecting 2 digits from nums1): Apply f(nums1, 2) resulting in [4, 6]. Here's how:

    • Start with an empty stack and nums1[0] = 3. remain will be 1 (k-x=3). Push 3 to the stack.
    • Next, nums1[1] = 4. Since 4 > 3 (top of the stack), pop 3 and push 4.
    • Finally, nums1[2] = 6 which is greater than the top again, so push 6.
    • The stack now has [4, 6].

  • For k-x = 3 (selecting 3 digits from nums2): Apply f(nums2, 3) and get [9, 2]. The process is similar to the above.

    • Since f(nums2, 3) would initially pick [9, 1, 2], but 1 would be popped out for 2 considering the same logic expressed above.

2. Merging two sequences preserving order

  • Merge [4, 6] and [9, 2] by selecting the highest digit available from the front of each array while maintaining relative order using merge.
    • First, compare 4 and 9, choose 9.
    • Then, compare 4 and 2, choose 4.
    • Next, 6 is the only digit left in nums1 so choose 6.
    • Finally, 2 is the only digit left from nums2 so choose 2.
    • The merged array is [9, 4, 6, 2].

3. Use of a for loop to find the best combination

  • Repeat steps 1 and 2 for all valid values of x (0 to 3 in this case) and keep track of the largest result (ans).
    • If x = 0, this means all digits are selected from nums2: Merge [] and [9, 1, 2] to get [9, 1, 2].
    • If x = 1, select 1 from nums1 and 4 from nums2. Merge [6] and [9, 2] to get [9, 6, 2].
    • If x = 3, all digits are selected from nums1: Merge [3, 4, 6] and [] to get [3, 4, 6].

Final Result

Compare all the results and select the largest one:

  • [9, 1, 2] is not the largest since we can have a larger digit in front by selecting from nums1.
  • [9, 6, 2] is larger than [9, 1, 2].
  • [9, 4, 6, 2] is the largest since it starts with 9 and is followed by larger digits as compared with the alternatives.

So the largest number that can be created by selecting k = 5 digits from nums1 and nums2 is [9, 4, 6, 2].

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
5        # Function to find the maximum number formed by k digits from the given list
6        def find_max_sequence(nums: List[int], k: int) -> List[int]:
7            stack = [0] * k  # Initialize a stack to store the max number sequence
8            to_remove = len(nums) - k  # Calculate how many digits we can remove
9            top = -1
10
11            for num in nums:
12                while top >= 0 and stack[top] < num and to_remove > 0:
13                    top -= 1  # Pop from stack
14                    to_remove -= 1
15                if top + 1 < k:  # If there is space in stack, push the current number
16                    top += 1
17                    stack[top] = num
18                else:
19                    to_remove -= 1
20
21            return stack
22
23        # Compare two sequences to determine which one is greater
24        def is_greater(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
25            while i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
26                i += 1
27                j += 1
28            return j == len(nums2) or (i < len(nums1) and nums1[i] > nums2[j])
29
30        # Merge two sequences into the largest possible number
31        def merge(nums1: List[int], nums2: List[int]) -> List[int]:
32            merged = []
33            i = j = 0
34            while i < len(nums1) or j < len(nums2):
35                if is_greater(nums1, nums2, i, j):
36                    merged.append(nums1[i])
37                    i += 1
38                else:
39                    merged.append(nums2[j])
40                    j += 1
41            return merged
42      
43        # Iterate through all possible splits of k between nums1 and nums2
44        best_sequence = [0] * k
45        for count in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
46            candidate1 = find_max_sequence(nums1, count)
47            candidate2 = find_max_sequence(nums2, k - count)
48            candidate_merged = merge(candidate1, candidate2)
49            if best_sequence < candidate_merged:
50                best_sequence = candidate_merged
51              
52        return best_sequence
53
1class Solution {
2    // Main function to calculate maximum number by combining two arrays with length k
3    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
4        int m = nums1.length, n = nums2.length;
5        int leftBound = Math.max(0, k - n), rightBound = Math.min(k, m);
6        int[] result = new int[k];
7      
8        // Iterate from the leftBound to the rightBound to find all possible combinations
9        for (int i = leftBound; i <= rightBound; ++i) {
10            int[] subsequence1 = getMaxSubsequence(nums1, i);
11            int[] subsequence2 = getMaxSubsequence(nums2, k - i);
12            int[] mergedArray = merge(subsequence1, subsequence2);
13          
14            // Check if the current merged array is greater than the result we have
15            if (compare(mergedArray, result, 0, 0)) {
16                result = mergedArray;
17            }
18        }
19        return result;
20    }
21
22    // Helper function to get the maximum subsequence of length k from nums array
23    private int[] getMaxSubsequence(int[] nums, int k) {
24        int n = nums.length;
25        int[] stack = new int[k];
26        int top = -1;
27        int remaining = n - k;
28        for (int num : nums) {
29            // If the current element nums is greater than the last element of stack
30            // and we have more remaining elements to dispose, pop from stack
31            while (top >= 0 && stack[top] < num && remaining > 0) {
32                --top;
33                --remaining;
34            }
35            // Push the current element nums to stack if it's not full
36            if (top + 1 < k) {
37                stack[++top] = num;
38            } else {
39                --remaining;
40            }
41        }
42        return stack;
43    }
44
45    // Merge the two subsequences to a single array in lexicographically maximum order
46    private int[] merge(int[] nums1, int[] nums2) {
47        int m = nums1.length, n = nums2.length;
48        int[] result = new int[m + n];
49        int i = 0, j = 0;
50      
51        // Merge the two arrays by selecting the larger current head element every time
52        for (int k = 0; k < m + n; ++k) {
53            if (compare(nums1, nums2, i, j)) {
54                result[k] = nums1[i++];
55            } else {
56                result[k] = nums2[j++];
57            }
58        }
59        return result;
60    }
61
62    // Compare two arrays from the given indices to find which array's number is greater
63    private boolean compare(int[] nums1, int[] nums2, int i, int j) {
64        int m = nums1.length, n = nums2.length;
65        // If we have reached the end of nums1, return false
66        if (i >= m) return false;
67        // If we have reached the end of nums2, return true
68        if (j >= n) return true;
69        // Compare the values at the current indices
70        if (nums1[i] > nums2[j]) return true;
71        if (nums1[i] < nums2[j]) return false;
72        // If values are the same, recursively compare the next indices
73        return compare(nums1, nums2, i + 1, j + 1);
74    }
75}
76
1#include <vector>
2#include <algorithm>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    // Create the maximum number from a single vector by choosing exactly k elements.
10    vector<int> getMaxNumberFromSingleVector(vector<int>& nums, int k) {
11        int n = nums.size();
12        vector<int> stack(k);
13        int top = -1;
14        int remain = n - k;
15        for (int x : nums) {
16            // If the current element is greater than the top element of stack
17            // and we still have elements to remove, then pop the stack.
18            while (top >= 0 && stack[top] < x && remain > 0) {
19                --top;
20                --remain;
21            }
22            // Push to the stack if it's not full.
23            if (top + 1 < k) {
24                stack[++top] = x;
25            } else {
26                // Decrease the count of remaining elements we can skip.
27                --remain;
28            }
29        }
30        return stack;
31    }
32
33    // Compare two vectors to decide which vector can provide larger number in lexical order.
34    bool compareVectors(vector<int>& nums1, vector<int>& nums2, int i, int j) {
35        if (i >= nums1.size()) {
36            return false;
37        }
38        if (j >= nums2.size()) {
39            return true;
40        }
41        if (nums1[i] > nums2[j]) {
42            return true;
43        }
44        if (nums1[i] < nums2[j]) {
45            return false;
46        }
47        // If both numbers are equal, compare the next pair of elements.
48        return compareVectors(nums1, nums2, i + 1, j + 1);
49    }
50
51    // Merge two vectors into one in a way that forms the largest number
52    // by lexical order.
53    vector<int> mergeVectors(vector<int>& nums1, vector<int>& nums2) {
54        int m = nums1.size(), n = nums2.size();
55        int i = 0, j = 0;
56        vector<int> result(m + n);
57        for (int k = 0; k < m + n; ++k) {
58            // Choose the larger element from nums1 or nums2 to add to the result.
59            if (compareVectors(nums1, nums2, i, j)) {
60                result[k] = nums1[i++];
61            } else {
62                result[k] = nums2[j++];
63            }
64        }
65        return result;
66    }
67
68    // Main method to merge and find the maximum number formed by nums1 and nums2 of length k.
69    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
70        int m = nums1.size(), n = nums2.size();
71        int start = max(0, k - n), end = min(k, m);
72        vector<int> ans(k, 0);
73        for (int x = start; x <= end; ++x) {
74            vector<int> subNums1 = getMaxNumberFromSingleVector(nums1, x);
75            vector<int> subNums2 = getMaxNumberFromSingleVector(nums2, k - x);
76            vector<int> merged = mergeVectors(subNums1, subNums2);
77            // Update the ans to the largest number.
78            if (ans < merged) {
79                ans = std::move(merged);
80            }
81        }
82        return ans;
83    }
84};
85
1function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
2    const nums1Length = nums1.length;
3    const nums2Length = nums2.length;
4    const leftBound = Math.max(0, k - nums2Length);
5    const rightBound = Math.min(k, nums1Length);
6    let maxSequence: number[] = Array(k).fill(0);
7
8    // Try all possible sizes combinations for sequences taken from nums1 and nums2
9    for (let sizeFromNums1 = leftBound; sizeFromNums1 <= rightBound; ++sizeFromNums1) {
10        const sequenceFromNums1 = getMaxSequence(nums1, sizeFromNums1);
11        const sequenceFromNums2 = getMaxSequence(nums2, k - sizeFromNums1);
12        const mergedSequence = mergeSequences(sequenceFromNums1, sequenceFromNums2);
13
14        // Update the result if the new sequence is greater
15        if (compareSequences(mergedSequence, maxSequence, 0, 0)) {
16            maxSequence = mergedSequence;
17        }
18    }
19    return maxSequence;
20}
21
22// Get the maximum sequence of given length k from nums
23function getMaxSequence(nums: number[], k: number): number[] {
24    const stack: number[] = Array(k).fill(0);
25    let top = -1;
26    let remaining = nums.length - k;
27
28    // Construct the maximum sequence
29    for (const num of nums) {
30        while (top >= 0 && stack[top] < num && remaining > 0) {
31            --top;
32            --remaining;
33        }
34        if (top + 1 < k) {
35            stack[++top] = num;
36        } else {
37            --remaining;
38        }
39    }
40    return stack;
41}
42
43// Compare two sequences to see if nums1 is greater than nums2 starting from indices i and j
44function compareSequences(nums1: number[], nums2: number[], i: number, j: number): boolean {
45    // If we reached the end of nums1, nums2 is greater or equal
46    if (i >= nums1.length) {
47        return false;
48    }
49    // If we reached the end of nums2, nums1 is greater
50    if (j >= nums2.length) {
51        return true;
52    }
53    // Direct comparison if elements are different
54    if (nums1[i] > nums2[j]) {
55        return true;
56    }
57    if (nums1[i] < nums2[j]) {
58        return false;
59    }
60    // If elements are the same, move to the next element
61    return compareSequences(nums1, nums2, i + 1, j + 1);
62}
63
64// Merge two sequences into the largest possible sequence
65function mergeSequences(nums1: number[], nums2: number[]): number[] {
66    const nums1Length = nums1.length;
67    const nums2Length = nums2.length;
68    const merged: number[] = Array(nums1Length + nums2Length).fill(0);
69    let index1 = 0;
70    let index2 = 0;
71
72    // Merge two sequences by choosing the greater element at each step
73    for (let k = 0; k < merged.length; ++k) {
74        if (compareSequences(nums1, nums2, index1, index2)) {
75            merged[k] = nums1[index1++];
76        } else {
77            merged[k] = nums2[index2++];
78        }
79    }
80    return merged;
81}
82
Not Sure What to Study? Take the 2-min Quiz๏ผš

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

The given Python code defines a problem of combining two numbers (nums1 and nums2) into the largest number possible of length k, where only elements from the same array maintain their original order.

Time Complexity:

The overall time complexity of the algorithm can be broken down into three parts: finding the maximum sub-sequence of a certain length from one array, comparing two sequences to see which one is greater, and merging the two sequences into one.

  1. Finding Maximum Sub-sequence (f function): For one array (say nums1 of length m), finding a maximum sub-sequence of length x requires a single pass through the original numbers, which takes O(m). This sub-sequence process needs to be done at most min(k, m) - max(0, k - n) + 1 times, where k is the required total length, m is the length of nums1, and n is the length of nums2.

  2. Comparing Two Sequences (compare function): This recursive comparison function has the feature of early termination when a different pair of numbers is encountered. In the worst case, it might need to go through the entire lengths of both nums1 and nums2, which are m and n respectively. So, the time complexity in the worst case would be O(m + n). However, this function tends to perform better than the worst case in practice.

  3. Merging Two Sequences (merge function): Merging two sequences of lengths x and k-x involves looking at each of the k elements once, resulting in a time complexity of O(k) for every merge.

The combined time complexity of these processes, considering the loop that tries every valid combination of lengths x from nums1 and k-x from nums2, is O((min(k, m) - max(0, k - n) + 1) * (m + n + k)). Given the worst-case scenario where the difference between min(k, m) and max(0, k - n) is maximal, this results in O(k * (m + n + k)).

Space Complexity:

The space complexity is primarily determined by the storage required for the stack in f function, the merging operation, and internal stack usage for recursion in comparison (in the compare function):

  1. Stack in f function: A stack of size k is used, leading to a space complexity of O(k) for the stack.

  2. Merging Two Sequences: The merge function uses a temporary list to store the merged sequence, also of size k, contributing O(k) to the space complexity.

  3. Comparing Two Sequences (Recursion Overhead): The recursion used in the compare function can potentially go as deep as m + n, so in the worst case, there is an additional space complexity of O(m + n) due to recursion stack.

Therefore, considering these separate contributions, the overall space complexity of the algorithm is O(k + m + n). This accounts for the stack in the f function, the merged array, and the potential system stack usage during the compare recursive calls.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ