Create Maximum Number - Practice Coding Problems

Create Maximum Number - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: [9,8,6,5,3]

💡 Note: Taking all elements and arranging optimally: start with 9 (largest), then 8, then 6 from nums1, then 5 (can be from either), then 3. The merged result maintains relative order from each array.

Example 2 — Limited Selection

$ Input: nums1 = [6,7], nums2 = [6,0,4], k = 3

› Output: [6,7,6]

💡 Note: We need exactly 3 elements. Best strategy is to take [6,7] from nums1 and [6] from nums2. When merging, we compare [6,7] vs [6,0,4] → [6,7] is larger, so pick 6 from nums1, then 7, then 6 from nums2.

Example 3 — Small k

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

› Output: [9,8,9]

💡 Note: Take 2 from nums1 ([3,9]) and 1 from nums2 ([8] - we pick the best subsequence). Merge: compare [3,9] vs [8] → [8] > [3,9], so pick 8. Then compare [3,9] vs [] → pick 3,9. But wait, we need optimal subsequences first: [9] from nums1, [8,9] from nums2 → merge gives [9,8,9].

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
1 ≤ nums1.length + nums2.length ≤ 2000
0 ≤ nums1[i], nums2[i] ≤ 9
1 ≤ k ≤ nums1.length + nums2.length

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays of digits with specific lengths

Select & Merge

Pick k digits total while maintaining relative order within each array

Maximum Result

Lexicographically largest possible number

Key Takeaway

🎯 Key Insight: Break into subproblems - find optimal subsequences using monotonic stack, then merge greedily by comparing remaining elements

Asked in

G Google 25 a Amazon 18 Apple 12 M Microsoft 8

The key insight is to break this into two subproblems: finding optimal subsequences from each array using monotonic stack, then merging them greedily. The optimal approach uses a greedy strategy with monotonic stack to find maximum subsequences, then merges by comparing remaining elements. Time: O(k*(m+n)), Space: O(m+n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Monotonic Stack	O(k*(m+n))	O(m+n)	Use monotonic stack to find optimal subsequences, then merge greedily
Brute Force - Try All Combinations	O(C(m,i) * C(n,k-i) * k)	O(2^(m+n))	Generate all possible subsequences and find the maximum

Greedy with Monotonic Stack — Algorithm Steps

Step 1: For each split i (from nums1) and k-i (from nums2), find maximum subsequences
Step 2: Use monotonic stack to maintain decreasing subsequence while respecting length constraint
Step 3: Merge two subsequences greedily by comparing remaining elements
Step 4: Return the lexicographically maximum result among all splits

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Best Subsequences

Use monotonic stack to get maximum subsequence from each array

Greedy Merge

Compare remaining elements to decide which array to pick from

Try All Splits

Test all valid ways to distribute k elements between arrays

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* maxSubsequence(int* nums, int numsSize, int length, int* returnSize) {
    *returnSize = length;
    if (length == 0) return NULL;
    if (length >= numsSize) {
        int* result = (int*)malloc(numsSize * sizeof(int));
        memcpy(result, nums, numsSize * sizeof(int));
        *returnSize = numsSize;
        return result;
    }
    
    int* stack = (int*)malloc(numsSize * sizeof(int));
    int stackSize = 0;
    int drop = numsSize - length;
    
    for (int i = 0; i < numsSize; i++) {
        while (stackSize > 0 && stack[stackSize-1] < nums[i] && drop > 0) {
            stackSize--;
            drop--;
        }
        stack[stackSize++] = nums[i];
    }
    
    int* result = (int*)malloc(length * sizeof(int));
    for (int i = 0; i < length; i++) {
        result[i] = stack[i];
    }
    free(stack);
    return result;
}

int compare(int* a, int aSize, int aStart, int* b, int bSize, int bStart) {
    while (aStart < aSize && bStart < bSize) {
        if (a[aStart] != b[bStart]) {
            return a[aStart] - b[bStart];
        }
        aStart++; bStart++;
    }
    return (aSize - aStart) - (bSize - bStart);
}

int* merge(int* a, int aSize, int* b, int bSize, int* returnSize) {
    *returnSize = aSize + bSize;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    int i = 0, j = 0, k = 0;
    
    while (i < aSize && j < bSize) {
        if (compare(a, aSize, i, b, bSize, j) > 0) {
            result[k++] = a[i++];
        } else {
            result[k++] = b[j++];
        }
    }
    
    while (i < aSize) result[k++] = a[i++];
    while (j < bSize) result[k++] = b[j++];
    
    return result;
}

int* solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) {
    *returnSize = k;
    int* maxResult = (int*)malloc(k * sizeof(int));
    int hasResult = 0;
    
    int start = (k - nums2Size > 0) ? k - nums2Size : 0;
    int end = (k < nums1Size) ? k : nums1Size;
    
    for (int i = start; i <= end; i++) {
        int size1, size2, mergedSize;
        int* subseq1 = maxSubsequence(nums1, nums1Size, i, &size1);
        int* subseq2 = maxSubsequence(nums2, nums2Size, k - i, &size2);
        int* merged = merge(subseq1, size1, subseq2, size2, &mergedSize);
        
        if (!hasResult || compare(merged, mergedSize, 0, maxResult, k, 0) > 0) {
            memcpy(maxResult, merged, k * sizeof(int));
            hasResult = 1;
        }
        
        free(subseq1);
        free(subseq2);
        free(merged);
    }
    
    return maxResult;
}

int main() {
    int nums1[1000], nums2[1000];
    int nums1Size = 0, nums2Size = 0, k;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line + 1, ",]");
    while (token) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(nums1, nums1Size, nums2, nums2Size, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k*(m+n))

For each of k splits, we process both arrays once using monotonic stack

✓ Linear Growth

Space Complexity

O(m+n)

Stack space for monotonic stack operations and temporary arrays

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~35 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler