Jobs

Interviews

Discussions

Create Maximum Number

Hard

Asked by:

More companies

43 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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.

Try coding it in LeetCode

Create Maximum Number

Hard

Asked by:

43 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the numbers within the input arrays?
Can the input arrays be empty or null?
If it's impossible to construct a number of the desired length k, what should I return?
If there are multiple ways to construct the maximum number, is any valid solution acceptable?
Can k be zero?

Brute Force Solution

Approach

The brute force method aims to find the largest possible number by exploring every possible combination of picking digits from the input numbers. It involves trying out all ways to select a certain number of digits from each given number and then merging them to form a new number.

Here's how the algorithm would work step-by-step:

Consider every possible split of the total number of digits you need to pick between the two given numbers.
For each split, go through every possible way to pick the required number of digits from the first number, making sure to keep the order of the digits the same as in the original number.
Do the same for the second number: go through every possible way to pick the required number of digits, keeping their original order.
Now, for each pair of digit selections (one from the first number, one from the second), try every possible way to merge these two selections together to form a new number, making sure to maintain the relative order of digits from each number.
Compare each new number formed during the merging process to the largest number found so far.
If the new number is larger than the current largest number, update the largest number.
After trying all possible splits, digit selections, and merges, return the largest number found.

Code Implementation

def create_maximum_number_brute_force(first_number, second_number, total_digits):
    maximum_number = []

    for first_number_digits in range(max(0, total_digits - len(second_number)), min(total_digits, len(first_number)) + 1):
        second_number_digits = total_digits - first_number_digits

        # Generate all possible sub-sequences for the first number
        first_number_subsequences = generate_all_subsequences(first_number, first_number_digits)

        # Generate all possible sub-sequences for the second number
        second_number_subsequences = generate_all_subsequences(second_number, second_number_digits)

        for first_subsequence in first_number_subsequences:
            for second_subsequence in second_number_subsequences:

                # Merge subsequences to create a candidate number
                merged_number = merge_subsequences(first_subsequence, second_subsequence)

                if not maximum_number or merged_number > maximum_number:
                    maximum_number = merged_number

    return maximum_number

def generate_all_subsequences(number, subsequence_length):
    if subsequence_length == 0:
        return [[]]

    if not number:
        return []

    if subsequence_length > len(number):
        return []

    subsequences = []
    if subsequence_length == len(number):
        subsequences.append(number[:])
    else:
        # Include the first digit
        include_first = generate_all_subsequences(number[1:], subsequence_length - 1)
        for subsequence in include_first:
            subsequences.append([number[0]] + subsequence)

        # Exclude the first digit
        exclude_first = generate_all_subsequences(number[1:], subsequence_length)
        subsequences.extend(exclude_first)

    return subsequences

def merge_subsequences(first_subsequence, second_subsequence):
    merged_number = []
    first_index = 0
    second_index = 0

    # Compare and select digits from both subsequences
    while first_index < len(first_subsequence) and second_index < len(second_subsequence):
        if first_subsequence[first_index:] > second_subsequence[second_index:]:
            merged_number.append(first_subsequence[first_index])
            first_index += 1
        else:
            merged_number.append(second_subsequence[second_index])
            second_index += 1

    # Add any remaining digits
    merged_number.extend(first_subsequence[first_index:])
    merged_number.extend(second_subsequence[second_index:])

    return merged_number

Big(O) Analysis

Time Complexity

O((m+n)C(m,k) * C(n,k) * k^2) – Let m and n be the lengths of the two input arrays, nums1 and nums2, and let k be the length of the desired result. The algorithm explores all possible splits of k between the two arrays, requiring combinations C(m, i) and C(n, k-i) where i ranges from 0 to k (effectively, calculating C(m,k) * C(n,k)). For each combination, merging the two sub-sequences of length i and k-i takes O(k) time, and comparing the merged sequence to the current maximum also takes O(k) time. Therefore, the merge and comparison is O(k^2). Summing over all splits, the overall time complexity is roughly O((m+n)C(m,k) * C(n,k) * k^2), where (m+n) accounts for generating all possible merges.

Space Complexity

O(N) – The brute force algorithm described involves creating multiple temporary lists or arrays to store digit selections from the two input numbers and the merged results. In the worst-case scenario, these lists can grow up to the size of the desired number of digits to pick, which can be as large as the combined length of the input numbers. Therefore, the auxiliary space required depends on the total number of digits, denoted as N. The space used grows linearly with N, leading to O(N) space complexity.

Optimal Solution

Approach

The goal is to create the largest possible number by carefully combining sub-sequences from the given numbers. The core idea is to think of each number as a collection of digits and strategically pick the best digits to create a combined number that is the biggest.

Here's how the algorithm would work step-by-step:

Consider each input number and figure out how to pick a certain number of digits from it to make the biggest possible sub-sequence. For instance, if you want 3 digits from the number '9125834', you need to find the largest 3-digit number within that sequence.
Develop a way to compare two different sub-sequences (from possibly different input numbers) to see which one is larger. This is like comparing two numbers digit by digit to see which is greater.
Now, imagine you have to combine two of these best sub-sequences (from potentially different input numbers) to make an even bigger number. Explore all possible combinations by choosing digits from both sequences, always picking the larger digit between them, until you've created the desired combined length.
Repeat this combining process for all the input numbers. Every time you combine, compare the result with the current largest number you've found. Keep track of the absolute largest number you can form with all the digits.
At the end, the largest number you have tracked is the answer, carefully built by picking the biggest digits from each original number and smartly combining them.

Code Implementation

def create_maximum_number(numbers1, numbers2, k):
    def find_maximum_subsequence(numbers, subsequence_length):
        stack = []
        drop_count = len(numbers) - subsequence_length
        for number in numbers:
            while stack and drop_count > 0 and stack[-1] < number:
                stack.pop()
                drop_count -= 1
            stack.append(number)
        return stack[:subsequence_length]

    def greater_than(subsequence1, index1, subsequence2, index2):
        while index1 < len(subsequence1) and index2 < len(subsequence2):
            if subsequence1[index1] > subsequence2[index2]:
                return True
            if subsequence1[index1] < subsequence2[index2]:
                return False
            index1 += 1
            index2 += 1
        return index1 != len(subsequence1)

    def merge_subsequences(subsequence1, subsequence2):
        merged_subsequence = []
        index1 = 0
        index2 = 0
        # Always pick the larger digit to create the largest number
        while index1 < len(subsequence1) or index2 < len(subsequence2):
            if greater_than(subsequence1, index1, subsequence2, index2):
                merged_subsequence.append(subsequence1[index1])
                index1 += 1
            else:
                merged_subsequence.append(subsequence2[index2])
                index2 += 1
        return merged_subsequence

    maximum_number = []
    for i in range(max(0, k - len(numbers2)), min(k, len(numbers1)) + 1):
        subsequence1 = find_maximum_subsequence(numbers1, i)
        subsequence2 = find_maximum_subsequence(numbers2, k - i)
        merged_subsequence = merge_subsequences(subsequence1, subsequence2)

        # Compare the merged subsequence to current maximum
        if not maximum_number or greater_than(merged_subsequence, 0, maximum_number, 0):
            maximum_number = merged_subsequence

    return maximum_number

Big(O) Analysis

Time Complexity

O((m+n) * (m+n+k)) – Let m and n be the lengths of the two input arrays, and k be the desired length of the combined array. The 'maxArray' function, which extracts the largest subsequence of a certain length, iterates through the input array once (O(m) or O(n)). The 'merge' function, which combines two subsequences, iterates up to k times, comparing digits in both subsequences (O(k)). The core algorithm considers all possible combinations of lengths from the two input arrays (up to m+n = k), invoking 'maxArray' for each length and then 'merge' to combine the subsequences. Therefore, the overall time complexity is approximately O((m+n)*(m+n+k)).

Space Complexity

O(N) – The algorithm uses auxiliary space primarily for storing sub-sequences of digits and the combined results of these sub-sequences. In the worst-case scenario, these sub-sequences and combined numbers can have a length proportional to the total number of digits in the input numbers, which we denote as N. Therefore, temporary lists of size up to N may be created to hold these sequences. This leads to an auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Both input arrays are empty	Return an empty array as there are no digits to create a number from.
k is zero	Return an empty array, as the length of the combined number is zero.
k is larger than the combined length of nums1 and nums2	Return an empty array because the combined length isn't long enough.
Input arrays contain only zeros	The `max_number` function should correctly combine and return the largest possible number formed by zeros.
One array is much larger than the other	The algorithm should efficiently handle different array sizes without unnecessary computations or memory issues.
Arrays with identical prefixes that lead to different better solutions later	The `greater` function must compare arrays lexicographically until a difference is found, even if the prefixes are identical.
Maximum array size (or very large k) leading to stack overflow with recursion	Ensure the solution uses an iterative approach to prevent stack overflow issues.
Arrays with many repeating subsequences causing redundant comparisons	The code must not get stuck in repeated comparisons of subsequences - can be solved by memoization in `greater` or other approaches to avoiding redundant lookups.

Both input arrays are empty

How to Handle:

Return an empty array as there are no digits to create a number from.

k is zero

How to Handle:

Return an empty array, as the length of the combined number is zero.

k is larger than the combined length of nums1 and nums2

How to Handle:

Return an empty array because the combined length isn't long enough.

Input arrays contain only zeros

How to Handle:

The `max_number` function should correctly combine and return the largest possible number formed by zeros.

One array is much larger than the other

How to Handle:

The algorithm should efficiently handle different array sizes without unnecessary computations or memory issues.

Arrays with identical prefixes that lead to different better solutions later

How to Handle:

The `greater` function must compare arrays lexicographically until a difference is found, even if the prefixes are identical.

Maximum array size (or very large k) leading to stack overflow with recursion

How to Handle:

Ensure the solution uses an iterative approach to prevent stack overflow issues.

Arrays with many repeating subsequences causing redundant comparisons

How to Handle:

The code must not get stuck in repeated comparisons of subsequences - can be solved by memoization in `greater` or other approaches to avoiding redundant lookups.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the numbers within the input arrays?
Can the input arrays be empty or null?
If it's impossible to construct a number of the desired length k, what should I return?
If there are multiple ways to construct the maximum number, is any valid solution acceptable?
Can k be zero?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible split of the total number of digits you need to pick between the two given numbers.
For each split, go through every possible way to pick the required number of digits from the first number, making sure to keep the order of the digits the same as in the original number.
Do the same for the second number: go through every possible way to pick the required number of digits, keeping their original order.
Now, for each pair of digit selections (one from the first number, one from the second), try every possible way to merge these two selections together to form a new number, making sure to maintain the relative order of digits from each number.
Compare each new number formed during the merging process to the largest number found so far.
If the new number is larger than the current largest number, update the largest number.
After trying all possible splits, digit selections, and merges, return the largest number found.

Code Implementation

def create_maximum_number_brute_force(first_number, second_number, total_digits):
    maximum_number = []

    for first_number_digits in range(max(0, total_digits - len(second_number)), min(total_digits, len(first_number)) + 1):
        second_number_digits = total_digits - first_number_digits

        # Generate all possible sub-sequences for the first number
        first_number_subsequences = generate_all_subsequences(first_number, first_number_digits)

        # Generate all possible sub-sequences for the second number
        second_number_subsequences = generate_all_subsequences(second_number, second_number_digits)

        for first_subsequence in first_number_subsequences:
            for second_subsequence in second_number_subsequences:

                # Merge subsequences to create a candidate number
                merged_number = merge_subsequences(first_subsequence, second_subsequence)

                if not maximum_number or merged_number > maximum_number:
                    maximum_number = merged_number

    return maximum_number

def generate_all_subsequences(number, subsequence_length):
    if subsequence_length == 0:
        return [[]]

    if not number:
        return []

    if subsequence_length > len(number):
        return []

    subsequences = []
    if subsequence_length == len(number):
        subsequences.append(number[:])
    else:
        # Include the first digit
        include_first = generate_all_subsequences(number[1:], subsequence_length - 1)
        for subsequence in include_first:
            subsequences.append([number[0]] + subsequence)

        # Exclude the first digit
        exclude_first = generate_all_subsequences(number[1:], subsequence_length)
        subsequences.extend(exclude_first)

    return subsequences

def merge_subsequences(first_subsequence, second_subsequence):
    merged_number = []
    first_index = 0
    second_index = 0

    # Compare and select digits from both subsequences
    while first_index < len(first_subsequence) and second_index < len(second_subsequence):
        if first_subsequence[first_index:] > second_subsequence[second_index:]:
            merged_number.append(first_subsequence[first_index])
            first_index += 1
        else:
            merged_number.append(second_subsequence[second_index])
            second_index += 1

    # Add any remaining digits
    merged_number.extend(first_subsequence[first_index:])
    merged_number.extend(second_subsequence[second_index:])

    return merged_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each input number and figure out how to pick a certain number of digits from it to make the biggest possible sub-sequence. For instance, if you want 3 digits from the number '9125834', you need to find the largest 3-digit number within that sequence.
Develop a way to compare two different sub-sequences (from possibly different input numbers) to see which one is larger. This is like comparing two numbers digit by digit to see which is greater.
Now, imagine you have to combine two of these best sub-sequences (from potentially different input numbers) to make an even bigger number. Explore all possible combinations by choosing digits from both sequences, always picking the larger digit between them, until you've created the desired combined length.
Repeat this combining process for all the input numbers. Every time you combine, compare the result with the current largest number you've found. Keep track of the absolute largest number you can form with all the digits.
At the end, the largest number you have tracked is the answer, carefully built by picking the biggest digits from each original number and smartly combining them.

Code Implementation

def create_maximum_number(numbers1, numbers2, k):
    def find_maximum_subsequence(numbers, subsequence_length):
        stack = []
        drop_count = len(numbers) - subsequence_length
        for number in numbers:
            while stack and drop_count > 0 and stack[-1] < number:
                stack.pop()
                drop_count -= 1
            stack.append(number)
        return stack[:subsequence_length]

    def greater_than(subsequence1, index1, subsequence2, index2):
        while index1 < len(subsequence1) and index2 < len(subsequence2):
            if subsequence1[index1] > subsequence2[index2]:
                return True
            if subsequence1[index1] < subsequence2[index2]:
                return False
            index1 += 1
            index2 += 1
        return index1 != len(subsequence1)

    def merge_subsequences(subsequence1, subsequence2):
        merged_subsequence = []
        index1 = 0
        index2 = 0
        # Always pick the larger digit to create the largest number
        while index1 < len(subsequence1) or index2 < len(subsequence2):
            if greater_than(subsequence1, index1, subsequence2, index2):
                merged_subsequence.append(subsequence1[index1])
                index1 += 1
            else:
                merged_subsequence.append(subsequence2[index2])
                index2 += 1
        return merged_subsequence

    maximum_number = []
    for i in range(max(0, k - len(numbers2)), min(k, len(numbers1)) + 1):
        subsequence1 = find_maximum_subsequence(numbers1, i)
        subsequence2 = find_maximum_subsequence(numbers2, k - i)
        merged_subsequence = merge_subsequences(subsequence1, subsequence2)

        # Compare the merged subsequence to current maximum
        if not maximum_number or greater_than(merged_subsequence, 0, maximum_number, 0):
            maximum_number = merged_subsequence

    return maximum_number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input arrays are empty	Return an empty array as there are no digits to create a number from.
k is zero	Return an empty array, as the length of the combined number is zero.
k is larger than the combined length of nums1 and nums2	Return an empty array because the combined length isn't long enough.
Input arrays contain only zeros	The `max_number` function should correctly combine and return the largest possible number formed by zeros.
One array is much larger than the other	The algorithm should efficiently handle different array sizes without unnecessary computations or memory issues.
Arrays with identical prefixes that lead to different better solutions later	The `greater` function must compare arrays lexicographically until a difference is found, even if the prefixes are identical.
Maximum array size (or very large k) leading to stack overflow with recursion	Ensure the solution uses an iterative approach to prevent stack overflow issues.
Arrays with many repeating subsequences causing redundant comparisons	The code must not get stuck in repeated comparisons of subsequences - can be solved by memoization in `greater` or other approaches to avoiding redundant lookups.

Both input arrays are empty

How to Handle:

Return an empty array as there are no digits to create a number from.

k is zero

How to Handle:

Return an empty array, as the length of the combined number is zero.

k is larger than the combined length of nums1 and nums2

How to Handle:

Return an empty array because the combined length isn't long enough.

Input arrays contain only zeros

How to Handle:

The `max_number` function should correctly combine and return the largest possible number formed by zeros.

One array is much larger than the other

How to Handle:

The algorithm should efficiently handle different array sizes without unnecessary computations or memory issues.

Arrays with identical prefixes that lead to different better solutions later

How to Handle:

The `greater` function must compare arrays lexicographically until a difference is found, even if the prefixes are identical.

Maximum array size (or very large k) leading to stack overflow with recursion

How to Handle:

Ensure the solution uses an iterative approach to prevent stack overflow issues.

Arrays with many repeating subsequences causing redundant comparisons

How to Handle:

The code must not get stuck in repeated comparisons of subsequences - can be solved by memoization in `greater` or other approaches to avoiding redundant lookups.