[LeetCode 321] Create Maximum Number [C] [Runtime : 12 MS]

1. Runtime Distribution

2. Submission Details

3. Description

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

4. Example

Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]
Example 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

5. Code

Code

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int * getMaxN(int * nums, int n, int numsSize)
{
    int * stack = (int *)malloc(sizeof(int) * n);
    int top = 0;
    for (int i = 0; i < numsSize; i++)
    {
        while (top > 0 && stack[top - 1] < nums[i] && numsSize - i + top > n) top--;
        if (top < n)
        {
            stack[top++] = nums[i];
        }
    }
    return stack;
}

bool compareTwoArrayFromSpecialIndex(int * array1, int i, int array1Size, int * array2, int j, int array2Size)
{
    while (i < array1Size && j < array2Size && array1[i] == array2[j])
    {
        i++; j++;
    }

    if (j == array2Size || i < array1Size && array1[i] > array2[j])
    {
        return true;
    }
    return false;
}

int * getMaxNum(int * array1, int array1Size, int * array2, int array2Size)
{
    int n = array1Size + array2Size;
    int * result = (int *)malloc(sizeof(int) * n);
    int count = 0, i = 0, j = 0;

    while (count < n)
    {
        result[count++] = compareTwoArrayFromSpecialIndex(array1, i, array1Size, array2, j, array2Size) ? array1[i++] : array2[j++];
    }
    return result;
}

int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) {

    int * max = NULL;
    for (int i = MAX(0, k - nums2Size); i <= k && i <= nums1Size; i++)
    {
        int * maxIInNums1 = getMaxN(nums1, i, nums1Size);
        int * maxK_IInNums2 = getMaxN(nums2, k - i, nums2Size);
        int * result = getMaxNum(maxIInNums1, i, maxK_IInNums2, k - i);
        if (max == NULL || compareTwoArrayFromSpecialIndex(result, 0, k, max, 0, k))
        {
            max = result;
        }
        else
        {
            free(result);
        }
    }
    *returnSize = k;
    return max;
}

Test

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

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int * getMaxN(int * nums, int n, int numsSize)
{
    int * stack = (int *)malloc(sizeof(int) * n);
    int top = 0;
    for (int i = 0; i < numsSize; i++)
    {
        while (top > 0 && stack[top - 1] < nums[i] && numsSize - i + top > n) top--;
        if (top < n)
        {
            stack[top++] = nums[i];
        }
    }
    return stack;
}

bool compareTwoArrayFromSpecialIndex(int * array1, int i, int array1Size, int * array2, int j, int array2Size)
{
    while (i < array1Size && j < array2Size && array1[i] == array2[j])
    {
        i++; j++;
    }

    if (j == array2Size || i < array1Size && array1[i] > array2[j])
    {
        return true;
    }
    return false;
}

int * getMaxNum(int * array1, int array1Size, int * array2, int array2Size)
{
    int n = array1Size + array2Size;
    int * result = (int *)malloc(sizeof(int) * n);
    int count = 0, i = 0, j = 0;

    while (count < n)
    {
        result[count++] = compareTwoArrayFromSpecialIndex(array1, i, array1Size, array2, j, array2Size) ? array1[i++] : array2[j++];
    }
    return result;
}

int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) {

    int * max = NULL;
    for (int i = MAX(0, k - nums2Size); i <= k && i <= nums1Size; i++)
    {
        int * maxIInNums1 = getMaxN(nums1, i, nums1Size);
        int * maxK_IInNums2 = getMaxN(nums2, k - i, nums2Size);
        int * result = getMaxNum(maxIInNums1, i, maxK_IInNums2, k - i);
        if (max == NULL || compareTwoArrayFromSpecialIndex(result, 0, k, max, 0, k))
        {
            max = result;
        }
        else
        {
            free(result);
        }
    }
    *returnSize = k;
    return max;
}

int main()
{
    int returnSize = 0;
    int nums1[] = { 2,5,6,4,4,0 };
    int nums2[] = { 7,3,8,0,6,5,7,6,2, };
    int * result = maxNumber(nums1, 6, nums2, 9, 15, &returnSize);
    for (int i = 0; i < returnSize; i++)
    {
        printf("%d", result[i]);
    }
    printf("\n");
    system("pause");
    return 0;
}