Sponsored
Sponsored
This approach utilizes a min-heap to efficiently get the smallest sums. We initialize the heap with pairs consisting of the first element from nums1 and each element from nums2. We then extract the minimum sum from the heap, track the index of the element from nums2, and push the next pair from nums1 onto the heap. Repeat the process until we've found k pairs or exhausted possibilities.
Time Complexity: O(k * log(min(k, n))) where n is the length of nums2.
Space Complexity: O(min(k, m*n)) used by the heap where m and n are the lengths of nums1 and nums2, respectively.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct {
5 int sum;
6 int i;
7 int j;
8} Pair;
9
10int compare(const void* a, const void* b) {
11 return ((Pair*)a)->sum - ((Pair*)b)->sum;
12}
13
14Pair* create_pair(int sum, int i, int j) {
15 Pair* p = (Pair*)malloc(sizeof(Pair));
16 p->sum = sum;
17 p->i = i;
18 p->j = j;
19 return p;
20}
21
22void add_to_heap(Pair** heap, int* size, int capacity, int sum, int i, int j) {
23 if (*size < capacity) {
24 heap[*size] = create_pair(sum, i, j);
25 qsort(heap, *size + 1, sizeof(Pair*), compare);
26 (*size)++;
27 }
28}
29
30int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes) {
31 *returnSize = 0;
32 Pair** heap = (Pair**)malloc(k * sizeof(Pair*));
33 int heapSize = 0;
34 for (int j = 0; j < nums2Size && j < k; j++)
35 add_to_heap(heap, &heapSize, k, nums1[0] + nums2[j], 0, j);
36
37 int** result = (int**)malloc(k * sizeof(int*));
38 *returnColumnSizes = (int*)malloc(k * sizeof(int));
39
40 while (*returnSize < k && heapSize > 0) {
41 Pair* smallest = heap[0];
42 result[*returnSize] = (int*)malloc(2 * sizeof(int));
43 (*returnColumnSizes)[*returnSize] = 2;
44 result[*returnSize][0] = nums1[smallest->i];
45 result[*returnSize][1] = nums2[smallest->j];
46 (*returnSize)++;
47
48 heap[0] = heap[heapSize - 1];
49 heapSize--;
50 qsort(heap, heapSize, sizeof(Pair*), compare);
51
52 if (smallest->i + 1 < nums1Size)
53 add_to_heap(heap, &heapSize, k, nums1[smallest->i + 1] + nums2[smallest->j], smallest->i + 1, smallest->j);
54
55 free(smallest);
56 }
57
58 free(heap);
59 return result;
60}In C, dynamic memory allocation is used alongside custom sorting functions to handle the min-heap operations manually since C lacks a built-in heap type. The implementation carefully manages the pairs of indices and their sums.
In this naive approach, we first generate all possible pairs and their sums, storing them in a list. After generating the pairs, we sort them based on their sums and simply return the first k pairs. This approach, while straightforward, is computationally expensive for large input sizes.
Time Complexity: O(m * n * log(m * n)) where m and n are the lengths of nums1 and nums2, respectively.
Space Complexity: O(m * n) for storing all pairs.
In this Python example, all pairwise sums are precomputed and stored in a list, which is then sorted to extract the first k pairs. The computational cost is high due to full pair generation and sorting.