java-LeetCode //C - 373. Find K Pairs with Smallest Sums

373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), …, (uk, vk) with the smallest sums.
 

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

Constraints:

• $1<=nums1.length,nums2.length<=10^5$
• $-10^9<=nums1[i],nums2[i]<=10^9$
• nums1 and nums2 both are sorted in non-decreasing order.
• $1<=k<=10^4$

From: LeetCode
Link: 373. Find K Pairs with Smallest Sums

Solution:

Ideas：

1. Initialization: The function first checks if either of the arrays is empty or if k is 0, in which case it returns NULL since no pairs can be formed.

2. Handling Large Values: To avoid integer overflow when calculating the minimum number of pairs to consider, it casts the sizes of the arrays to long long before multiplying. This ensures that the multiplication doesn’t exceed the limits of int.

3. Heap Creation: A min-heap is created to store the pairs, but instead of storing the actual pair, we store a HeapNode struct which contains the sum of the pair and the indices of the elements in the two arrays that form the pair.

4. Heap Initialization: The heap is initially populated with pairs formed by combining each element from nums1 with the first element of nums2. This step assumes that the smallest pair includes the first element of nums2 and some element from nums1.

5. Finding k Smallest Pairs:

• The algorithm repeatedly extracts the smallest sum pair from the heap (which is the root of the min-heap) until it has found k pairs or the heap is empty.
• For each pair extracted, if there’s a next element in nums2, a new pair is formed by the current element from nums1 and the next element of nums2, and this new pair is added to the heap. This exploits the sorted property of nums2 to efficiently find the next smallest pair.
• The sum and indices in the HeapNode allow the algorithm to track and create the next potential smallest sum pair without generating all possible pairs at once, which would be inefficient.

6. Storing Results: The actual pairs are then formed using the indices from the HeapNode and stored in the result array.

7. Memory Management: The heap is freed after its use, and the result array is returned along with the returnColumnSizes which helps the caller know how many items are in each sub-array (always 2 in this case).

This approach is efficient for several reasons:

• Space Efficiency: It doesn’t generate all possible pairs, which would take up a lot of space especially when the input arrays are large.
• Time Efficiency: It takes advantage of the sorted property of the input arrays, so it doesn’t need to compare every possible pair.
• Priority Queue: The min-heap (priority queue) allows the algorithm to always have access to the current smallest pair without having to search for it, which saves time.

Code:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
typedef struct {
    
    int sum;
    int i;
    int j;
} HeapNode;

void swap(HeapNode *a, HeapNode *b) {
    
    HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(HeapNode *heap, int heapSize, int i) {
    
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < heapSize && heap[left].sum < heap[smallest].sum) {
    
        smallest = left;
    }

    if (right < heapSize && heap[right].sum < heap[smallest].sum) {
    
        smallest = right;
    }

    if (smallest != i) {
    
        swap(&heap[i], &heap[smallest]);
        heapify(heap, heapSize, smallest);
    }
}

HeapNode heapPop(HeapNode *heap, int *heapSize) {
    
    HeapNode minElement = heap[0];
    heap[0] = heap[*heapSize - 1];
    *heapSize = *heapSize - 1;
    heapify(heap, *heapSize, 0);
    return minElement;
}

void heapPush(HeapNode *heap, int *heapSize, HeapNode value) {
    
    heap[*heapSize] = value;
    int i = *heapSize;
    *heapSize = *heapSize + 1;

    while (i != 0 && heap[(i - 1) / 2].sum > heap[i].sum) {
    
        swap(&heap[(i - 1) / 2], &heap[i]);
        i = (i - 1) / 2;
    }
}

int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes) {
    
    *returnSize = 0;
    if (nums1Size == 0 || nums2Size == 0 || k == 0) {
    
        return NULL;
    }

    // Calculate the minimum number of pairs without causing integer overflow
    long long product = (long long)nums1Size * (long long)nums2Size;
    long long minPairs = product < (long long)k ? product : (long long)k;

    HeapNode *heap = (HeapNode *)malloc(sizeof(HeapNode) * nums1Size);
    int heapSize = 0;

    // Initialize the heap with the first element of nums2 paired with every element of nums1
    for (int i = 0; i < nums1Size && i < minPairs; i++) {
    
        heapPush(heap, &heapSize, (HeapNode){
    nums1[i] + nums2[0], i, 0});
    }

    int **result = (int **)malloc(sizeof(int *) * minPairs);
    *returnColumnSizes = (int *)malloc(sizeof(int) * minPairs);

    // Extract the smallest pairs from the heap up to k times
    while (heapSize > 0 && *returnSize < minPairs) {
    
        HeapNode node = heapPop(heap, &heapSize);
        int *pair = (int *)malloc(sizeof(int) * 2);
        pair[0] = nums1[node.i];
        pair[1] = nums2[node.j];
        result[*returnSize] = pair;
        (*returnColumnSizes)[*returnSize] = 2;
        (*returnSize)++;

        if (node.j + 1 < nums2Size) {
    
            heapPush(heap, &heapSize, (HeapNode){
    nums1[node.i] + nums2[node.j + 1], node.i, node.j + 1});
        }
    }

    free(heap);
    return result;
}