LeetCode //C - 2542. Maximum Subsequence Score

2542. Maximum Subsequence Score

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, …, ik - 1, your score is defined as:

• The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
• It can defined simply as: (nums1[i0] + nums1[i1] +…+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], … ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, …, n-1} by deleting some or no elements.
 

Example 1:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Example 2:

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints:

• n == nums1.length == nums2.length
• $1<=n<=10^5$
• $0<=nums1[i],nums2[j]<=10^5$
• 1 <= k <= n

From: LeetCode
Link: 2542. Maximum Subsequence Score

Solution:

Ideas：

1. Data Structure (Data): A struct that pairs elements from nums1 and nums2 together. This allows sorting and processing based on the elements of nums2 while keeping the corresponding nums1 values paired.

2. Sorting (qsort with cmpfunc): The array of Data structs is sorted in descending order based on nums2 values. This sorting helps in selecting the k elements with the highest nums2 values first, which is critical in finding the minimum nums2 value in each iteration.

3. Min Heap Operations:

• Heapify (heapifyMinHeap): Maintains the min heap property in the heap. This is used when the root is deleted or when a new element is inserted.
• Insertion (insertToHeap): Inserts a new element into the min heap. This operation is used to keep track of k elements from nums1.
• Deletion (deleteRootFromHeap): Removes the root (minimum element) from the min heap. This is necessary when moving the window of size k forward.

4. Main Logic (maxScore function):

• An array of Data structs is created and sorted.
• A min heap is used to keep track of the k elements from nums1.
• In each iteration, a new element from the sorted Data array is added to the heap, and the minimum element is removed if the heap size exceeds k.
• The sum of the k elements in the heap and the minimum nums2 value from the k elements chosen so far are used to calculate the score.
• The algorithm looks for the maximum score as it iterates through the sorted Data array.

Code:

typedef long long LL;

typedef struct{
   
    int nums1;
    int nums2;
}Data;

int cmpfunc (const void * a, const void * b){
   
    
    int anums2 = ((Data*)a)->nums2;
    int bnums2 = ((Data*)b)->nums2;

    return (bnums2 - anums2);

}

void swap(int* a, int* b){
   

    int t = *a;

    *a = *b;
    *b = t;

}

void heapifyMinHeap(int* nums, int numsSize, int parentIndex){
   

    int smallest = parentIndex;
    int leftChild  = (smallest << 1) + 1;
    int rightChild = (smallest << 1) + 2;

    if((leftChild < numsSize) && (nums[leftChild] < nums[smallest])){
   
        smallest = leftChild;
    }

    if((rightChild < numsSize) && (nums[rightChild] < nums[smallest])){
   
        smallest = rightChild;
    }

    if(smallest != parentIndex){
   
        swap(&nums[smallest], &nums[parentIndex]);
        heapifyMinHeap(nums, numsSize, smallest);
    }

}

void deleteRootFromHeap(int* nums, int numsSize){
   

    swap(&nums[0], &nums[--numsSize]);
    heapifyMinHeap(nums, numsSize, 0);

}

void insertToHeap(int* nums, int numsSize, int new){
   

    nums[numsSize++] = new;

    int childIndex  = numsSize - 1;
    int parentIndex = (childIndex - 1) >> 1;
    while((childIndex > 0) && (nums[childIndex] < nums[parentIndex])){
   
        swap(&nums[childIndex], &nums[parentIndex]);
        childIndex  = parentIndex;
        parentIndex = (childIndex - 1) >> 1;
    }

}


long long maxScore(int* nums1, int nums1Size, int* nums2, int nums2Size, int k){
   

    Data* data = (Data*)malloc(nums2Size * sizeof(Data));

    for(int i = 0; i < nums2Size; i++){
   
        data[i].nums1 = nums1[i];
        data[i].nums2 = nums2[i];
    }

    qsort(data, nums2Size, sizeof(Data), cmpfunc);

    int* minHeap  = (int*)calloc(k + 1, sizeof(int));
    int  heapSize = 0;

    LL sumNum1  = 0;
    LL minNums2 = 0;
    LL maxScore = 0;
    LL score = 0;

    for(int i = 0; i < k; i++){
   
        sumNum1 += data[i].nums1;
        minNums2 = data[i].nums2;
        insertToHeap(minHeap, heapSize++, data[i].nums1);
    }

    maxScore = sumNum1 * minNums2;

    for(int i = k; i < nums2Size; i++){
   

        sumNum1 += data[i].nums1;
        minNums2 = data[i].nums2;
        insertToHeap(minHeap, heapSize++, data[i].nums1);

        sumNum1 -= minHeap[0];
        deleteRootFromHeap(minHeap, heapSize--);

        score = sumNum1 * minNums2;
        if(score > maxScore){
   
            maxScore = score;
        }

    }

    free(data);
    free(minHeap);

    return maxScore;

}