Find K Pairs with Smallest Sums - Practice Coding Problems

Find K Pairs with Smallest Sums - Problem

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 (u₁, v₁), (u₂, v₂), ..., (uₖ, vₖ) with the smallest sums.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3

› Output: [[1,2],[1,4],[1,6]]

💡 Note: The first 3 pairs with smallest sums are: (1,2)→3, (1,4)→5, (1,6)→7. All pairs from nums1[0] have the smallest possible sums.

Example 2 — Mixed Selection

$ Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2

› Output: [[1,1],[1,1]]

💡 Note: The pairs with smallest sums are: (1,1)→2 and (1,1)→2. Both nums1[0] and nums1[1] paired with nums2[0] give the minimum sum.

Example 3 — Single Elements

$ Input: nums1 = [1,2], nums2 = [3], k = 3

› Output: [[1,3],[2,3]]

💡 Note: Only 2 pairs are possible: (1,3)→4 and (2,3)→5. Since k=3 but only 2 pairs exist, we return all available pairs.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
-10⁹ ≤ nums1[i], nums2[i] ≤ 10⁹
nums1 and nums2 both are sorted in non-decreasing order
1 ≤ k ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two sorted arrays nums1=[1,7,11] and nums2=[2,4,6], k=3

Find Pairs

Systematically find pairs with smallest sums

Output Result

Return first k pairs: [[1,2], [1,4], [1,6]]

Key Takeaway

🎯 Key Insight: Use a min-heap to efficiently explore pairs in ascending order of their sums, starting from the guaranteed minimum

Asked in

G Google 45 a Amazon 32 M Microsoft 28

The key insight is to use a min-heap to systematically explore pairs in order of their sum values, starting from the smallest possible pair. Best approach uses heap optimization with Time: O(k×log(min(k,m))), Space: O(min(k,m)) which is much more efficient than generating all possible pairs.

Common Approaches

Approach	Time	Space	Notes
✓ Min-Heap Optimization	O(k×log(min(k,m)))	O(min(k,m))	Use a min-heap to efficiently find k smallest sum pairs without generating all combinations
Brute Force - Generate All Pairs	O(m×n×log(m×n))	O(m×n)	Generate all possible pairs, sort by sum, return first k pairs

Min-Heap Optimization — Algorithm Steps

Initialize heap with pairs from nums1[0] with all elements of nums2
Extract minimum sum pair from heap
Add neighboring pairs to heap (next element from nums1)
Repeat until we have k pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with the smallest possible pair (0,0)

Expand

Add adjacent pairs to heap and extract minimum

Continue

Repeat until we have k pairs

Code -

solution.c — C

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

typedef struct {
    int sum, i, j;
} HeapItem;

typedef struct {
    HeapItem* items;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->items = (HeapItem*)malloc(capacity * sizeof(HeapItem));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MinHeap* heap, int index) {
    if (index == 0) return;
    int parent = (index - 1) / 2;
    if (heap->items[parent].sum > heap->items[index].sum) {
        HeapItem temp = heap->items[parent];
        heap->items[parent] = heap->items[index];
        heap->items[index] = temp;
        heapifyUp(heap, parent);
    }
}

void heapifyDown(MinHeap* heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;
    
    if (left < heap->size && heap->items[left].sum < heap->items[smallest].sum)
        smallest = left;
    if (right < heap->size && heap->items[right].sum < heap->items[smallest].sum)
        smallest = right;
    
    if (smallest != index) {
        HeapItem temp = heap->items[index];
        heap->items[index] = heap->items[smallest];
        heap->items[smallest] = temp;
        heapifyDown(heap, smallest);
    }
}

void push(MinHeap* heap, int sum, int i, int j) {
    heap->items[heap->size].sum = sum;
    heap->items[heap->size].i = i;
    heap->items[heap->size].j = j;
    heap->size++;
    heapifyUp(heap, heap->size - 1);
}

HeapItem pop(MinHeap* heap) {
    HeapItem result = heap->items[0];
    heap->items[0] = heap->items[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return result;
}

int** solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes) {
    if (nums1Size == 0 || nums2Size == 0 || k == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    MinHeap* heap = createHeap(k * 2);
    int visited[1000][1000] = {0}; // Simple visited array for demo
    
    push(heap, nums1[0] + nums2[0], 0, 0);
    visited[0][0] = 1;
    
    int** result = (int**)malloc(k * sizeof(int*));
    *returnColumnSizes = (int*)malloc(k * sizeof(int));
    *returnSize = 0;
    
    while (*returnSize < k && heap->size > 0) {
        HeapItem item = pop(heap);
        
        result[*returnSize] = (int*)malloc(2 * sizeof(int));
        result[*returnSize][0] = nums1[item.i];
        result[*returnSize][1] = nums2[item.j];
        (*returnColumnSizes)[*returnSize] = 2;
        (*returnSize)++;
        
        if (item.i + 1 < nums1Size && !visited[item.i + 1][item.j]) {
            push(heap, nums1[item.i + 1] + nums2[item.j], item.i + 1, item.j);
            visited[item.i + 1][item.j] = 1;
        }
        
        if (item.j + 1 < nums2Size && !visited[item.i][item.j + 1]) {
            push(heap, nums1[item.i] + nums2[item.j + 1], item.i, item.j + 1);
            visited[item.i][item.j + 1] = 1;
        }
    }
    
    free(heap->items);
    free(heap);
    return result;
}

int main() {
    // Simplified demo version
    int nums1[] = {1, 7, 11};
    int nums2[] = {2, 4, 6};
    int k = 3;
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(nums1, 3, nums2, 3, k, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k×log(min(k,m)))

We process k pairs, each heap operation takes O(log(min(k,m))) time where m is length of nums1

⚡ Linearithmic

Space Complexity

O(min(k,m))

Heap stores at most min(k,m) pairs at any time, plus result array

⚡ Linearithmic Space

142.5K Views

Medium Frequency

~25 min Avg. Time

2.8K 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

Min-Heap Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler