DSA Day 95/250: Find K Pairs with Smallest Sums (LeetCode 373)

[Click here to read for free.]

373. Find K Pairs with Smallest Sums

Difficulty: Medium Topics: Array, Heap (Priority Queue) Platform: LeetCode

Problem Statement

You are given two sorted arrays:

nums1
nums2

A pair consists of:

(nums1[i], nums2[j])

Your task is to return:

The k pairs having the smallest sums.

Practice System Design Interviews

If you want to practice real-world system design and technical interview questions, I’ve been exploring PracHub recently. It has company-specific interview questions, mock interview-style problems, and structured practice content for engineering interviews.

Practice here:

[embed]PracHub - Practice Tech Interview Questions (Updated 2026) Master your tech interviews with 8,500+ questions from top companies, validated by real candidates. Practice coding…prachub.com

Example 1

Input

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

Output

[[1,2],[1,4],[1,6]]

Example 2

Input

nums1 = [1,1,2]
nums2 = [1,2,3]
k = 2

Output

[[1,1],[1,1]]

Intuition (Important)

A brute-force approach would generate every possible pair.

For arrays of size:

m and n

Total pairs become:

m × n

Then we would sort all pairs by sum.

This requires:

O(m × n log(m × n))

which becomes very expensive.

The key observation is that both arrays are already sorted.

We should use this property instead of generating every pair.

Key Idea

Suppose:

nums1 = [1,7,11]
nums2 = [2,4,6]

The smallest possible pair must be:

(1,2)

After that, the next smallest candidate involving 1 is:

(1,4)

Then:

(1,6)

This looks very similar to merging sorted lists.

We can use a Min Heap to always extract the current smallest pair.

Heap Strategy

Instead of generating all pairs:

Push only:

(nums1[i], nums2[0])

for the first few rows.

For each extracted pair:

(i,j)

we insert:

(i,j+1)

This way we gradually explore only the pairs that can contribute to the answer.

Visual Understanding

Input

nums1 = [1,7,11]
nums2 = [2,4,6]

Initial Heap

(1,2) sum=3
(7,2) sum=9
(11,2) sum=13

Heap top:

(1,2)

Extract it.

Now push:

(1,4)

because it is the next pair in the same row.

Heap becomes:

(1,4)
(7,2)
(11,2)

Again extract minimum.

Continue until k pairs are found.

Iteration Flow (Detailed Dry Run)

Input

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

Step 1: Build Initial Heap

Insert:

(1,2) -> sum=3
(7,2) -> sum=9
(11,2) -> sum=13

Heap:

[
 (1,2),
 (7,2),
 (11,2)
]

Step 2: Extract Minimum

Remove:

(1,2)

Answer:

[[1,2]]

Push next pair from same row:

(1,4)

Heap:

[
 (1,4),
 (7,2),
 (11,2)
]

Step 3: Extract Minimum

Remove:

(1,4)

Answer:

[[1,2],[1,4]]

Push:

(1,6)

Heap:

[
 (1,6),
 (7,2),
 (11,2)
]

Step 4: Extract Minimum

Remove:

(1,6)

Answer:

[[1,2],[1,4],[1,6]]

We already have:

k = 3

Stop.

Final Result

[[1,2],[1,4],[1,6]]

Correct Answer

Approach

We use a Min Heap where each heap node stores:

[
 sum,
 index in nums1,
 index in nums2
]

Initially, we push:

(nums1[i], nums2[0])

for the first:

min(k, nums1.length)

rows.

Then:

• Extract the smallest pair
• Add it to answer
• Push the next pair from the same row

This guarantees that pairs are processed in increasing order of sums.

🧑‍💻 Optimized JavaScript Solution

class MinHeap {
    constructor() {
        this.heap = [];
    }
    size() {
        return this.heap.length;
    }
    push(val) {
        this.heap.push(val);
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent][0] <= this.heap[idx][0]) break;
            [this.heap[parent], this.heap[idx]] =
            [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        let top = this.heap[0];
        this.heap[0] = this.heap.pop();
        let idx = 0;
        while (true) {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let smallest = idx;
            if (
                left < this.heap.length &&
                this.heap[left][0] < this.heap[smallest][0]
            ) {
                smallest = left;
            }
            if (
                right < this.heap.length &&
                this.heap[right][0] < this.heap[smallest][0]
            ) {
                smallest = right;
            }
            if (smallest === idx) break;
            [this.heap[idx], this.heap[smallest]] =
            [this.heap[smallest], this.heap[idx]];
            idx = smallest;
        }
        return top;
    }
}
var kSmallestPairs = function(nums1, nums2, k) {
    let result = [];
    let heap = new MinHeap();
    for (
        let i = 0;
        i < Math.min(k, nums1.length);
        i++
    ) {
        heap.push([
            nums1[i] + nums2[0],
            i,
            0
        ]);
    }
    while (k > 0 && heap.size() > 0) {
        let [sum, i, j] = heap.pop();
        result.push([
            nums1[i],
            nums2[j]
        ]);
        if (j + 1 < nums2.length) {
            heap.push([
                nums1[i] + nums2[j + 1],
                i,
                j + 1
            ]);
        }
        k--;
    }
    return result;
};

Code Dry Run (Step-by-Step Execution)

Initial Heap

(1,2) -> 3
(7,2) -> 9
(11,2) -> 13

Extract #1

(1,2)

Push:

(1,4)

Extract #2

(1,4)

Push:

(1,6)

Extract #3

(1,6)

Answer:

[
 [1,2],
 [1,4],
 [1,6]
]

Final Output

Complexity Analysis

Time Complexity

Heap size remains at most:

min(k, nums1.length)

For k operations:

O(k log k)

Space Complexity

O(k)

for the heap.

Why This Problem Is Important

This problem teaches a powerful interview pattern:

K Smallest / K Largest using Heap

The same pattern appears in:

• K Closest Points to Origin
• Kth Largest Element
• Top K Frequent Elements
• Merge K Sorted Lists

Key Takeaways

✔ Do not generate all possible pairs ✔ Use sorted array properties ✔ Heap helps process candidates lazily ✔ Top-K problems often use Priority Queues

🎓 Structured Learning Beyond Blogs

Courses

• DSA Course: ₹99
• System Design Course: ₹99
• DSA + System Design Combo: ₹149

Explore here:

[embed]Notes | Linktree linktr.ee

Day 95/250 Completed

Today we learned:

✔ Heap-based pair generation ✔ K smallest pattern ✔ Sorted array optimization ✔ Lazy exploration technique

This is one of the most important Heap + Top K interview problems and frequently appears in coding interviews.