Find K Pairs with Smallest Sums

🎯

Find K Pairs with Smallest Sums

mediumHEAPAmazonGoogleFacebook

Imagine you have two sorted lists of prices from two different stores, and you want to find the k cheapest combined purchase options by pairing one item from each store.

💡 This problem involves combining two sorted arrays to find pairs with the smallest sums. Beginners often struggle because the naive approach is too slow, and understanding how to efficiently generate pairs without enumerating all possibilities requires grasping heap-based lazy expansion.

📋

Problem Statement

Given two integer arrays nums1 and nums2 sorted in ascending order, and an integer k, return the k pairs (u,v) which consist of one element from nums1 and one from nums2 such that the sums of u + v are the smallest. If there are fewer than k pairs, return all possible pairs.

1 ≤ nums1.length, nums2.length ≤ 10^5-10^9 ≤ nums1[i], nums2[i] ≤ 10^9nums1 and nums2 are sorted in ascending order1 ≤ k ≤ 10^4

💡

Example

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

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

The pairs with the smallest sums are (1,2)=3, (1,4)=5, and (1,6)=7.

• One or both arrays empty → return empty list
• k larger than total possible pairs → return all pairs
• Arrays with negative numbers → still find smallest sums correctly
• Arrays with duplicates → pairs with same sums included

⚠️

Common Mistakes

Enumerating all pairs without pruning

Time limit exceeded on large inputs

✅ Use min-heap lazy expansion to generate pairs on demand

Pushing duplicate pairs into the heap

Heap grows too large, inefficient runtime

✅ Only push next pair in nums2 for each nums1 index to avoid duplicates

Not handling empty input arrays

Runtime errors or incorrect empty output

✅ Check for empty arrays and return empty list early

Incorrectly indexing nums2 when pushing new pairs

Index out of bounds errors or missing pairs

✅ Always check j + 1 < len(nums2) before pushing new pair

Sorting pairs by sum but returning pairs unsorted

Output order does not match expected smallest sums

✅ Return pairs in sorted order or use heap to maintain order

🧠

Brute Force (Enumerate All Pairs)

💡 This approach exists to build intuition by directly enumerating all pairs and sorting them, which is conceptually simple but inefficient for large inputs.

Intuition

Generate every possible pair from nums1 and nums2, compute their sums, then sort all pairs to pick the smallest k sums.

Algorithm

1. Initialize an empty list to store all pairs and their sums.
2. Use nested loops to generate every pair (nums1[i], nums2[j]).
3. Add each pair and its sum to the list.
4. Sort the list by sum and return the first k pairs.

💡 The nested loops and sorting make this approach straightforward but slow, especially when input arrays are large.

</>

Code

from typing import List

def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    pairs = []
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            pairs.append((nums1[i] + nums2[j], [nums1[i], nums2[j]]))
    pairs.sort(key=lambda x: x[0])
    return [pair[1] for pair in pairs[:k]]

# Example usage
if __name__ == '__main__':
    print(kSmallestPairs([1,7,11], [2,4,6], 3))

Line Notes

pairs = []Initialize list to store all pairs with their sums

for i in range(len(nums1))Outer loop to pick each element from nums1

for j in range(len(nums2))Inner loop to pair with each element from nums2

pairs.append((nums1[i] + nums2[j], [nums1[i], nums2[j]]))Store sum and pair for sorting later

pairs.sort(key=lambda x: x[0])Sort pairs by their sum to find smallest sums

return [pair[1] for pair in pairs[:k]]Extract only the pairs from sorted list, limited to k

import java.util.*;

public class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<Pair> pairs = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                pairs.add(new Pair(nums1[i] + nums2[j], nums1[i], nums2[j]));
            }
        }
        Collections.sort(pairs, Comparator.comparingInt(p -> p.sum));
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.min(k, pairs.size()); i++) {
            Pair p = pairs.get(i);
            result.add(Arrays.asList(p.num1, p.num2));
        }
        return result;
    }

    static class Pair {
        int sum, num1, num2;
        Pair(int sum, int num1, int num2) {
            this.sum = sum;
            this.num1 = num1;
            this.num2 = num2;
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.kSmallestPairs(new int[]{1,7,11}, new int[]{2,4,6}, 3));
    }
}

Line Notes

List<Pair> pairs = new ArrayList<>();Create list to hold all pairs with sums

for (int i = 0; i < nums1.length; i++)Outer loop over nums1 elements

for (int j = 0; j < nums2.length; j++)Inner loop over nums2 elements

pairs.add(new Pair(nums1[i] + nums2[j], nums1[i], nums2[j]));Add pair and sum to list

Collections.sort(pairs, Comparator.comparingInt(p -> p.sum));Sort pairs by sum ascending

for (int i = 0; i < Math.min(k, pairs.size()); i++)Collect first k pairs after sorting

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<pair<int, vector<int>>> pairs;
    for (int i = 0; i < (int)nums1.size(); i++) {
        for (int j = 0; j < (int)nums2.size(); j++) {
            pairs.push_back({nums1[i] + nums2[j], {nums1[i], nums2[j]}});
        }
    }
    sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a.first < b.first; });
    vector<vector<int>> result;
    for (int i = 0; i < min(k, (int)pairs.size()); i++) {
        result.push_back(pairs[i].second);
    }
    return result;
}

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    int k = 3;
    vector<vector<int>> res = kSmallestPairs(nums1, nums2, k);
    for (auto &p : res) {
        cout << '[' << p[0] << ',' << p[1] << ']';
    }
    cout << '\n';
    return 0;
}

Line Notes

vector<pair<int, vector<int>>> pairs;Store pairs with their sums for sorting

for (int i = 0; i < (int)nums1.size(); i++)Outer loop over nums1

for (int j = 0; j < (int)nums2.size(); j++)Inner loop over nums2

pairs.push_back({nums1[i] + nums2[j], {nums1[i], nums2[j]}});Add sum and pair to vector

sort(pairs.begin(), pairs.end(), [](auto &a, auto &b) { return a.first < b.first; });Sort pairs by sum ascending

for (int i = 0; i < min(k, (int)pairs.size()); i++)Collect first k pairs after sorting

function kSmallestPairs(nums1, nums2, k) {
    const pairs = [];
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++) {
            pairs.push({sum: nums1[i] + nums2[j], pair: [nums1[i], nums2[j]]});
        }
    }
    pairs.sort((a, b) => a.sum - b.sum);
    return pairs.slice(0, k).map(p => p.pair);
}

// Example usage
console.log(kSmallestPairs([1,7,11], [2,4,6], 3));

Line Notes

const pairs = []Initialize array to hold all pairs with sums

for (let i = 0; i < nums1.length; i++)Outer loop over nums1 elements

for (let j = 0; j < nums2.length; j++)Inner loop over nums2 elements

pairs.push({sum: nums1[i] + nums2[j], pair: [nums1[i], nums2[j]]});Store sum and pair for sorting

pairs.sort((a, b) => a.sum - b.sum);Sort pairs by sum ascending

return pairs.slice(0, k).map(p => p.pair);Return only the pairs, limited to k

⏱

Complexity

TimeO(n*m log(n*m)) where n and m are lengths of nums1 and nums2

SpaceO(n*m) to store all pairs

We generate all pairs (n*m), then sort them which takes O(n*m log(n*m)) time.

💡 For n=1000 and m=1000, this means 1,000,000 pairs and sorting them is very expensive.

Interview Verdict: TLE for large inputs; only useful to introduce problem

This approach is too slow for large inputs but helps understand the problem and correctness.

🧠

Min-Heap with Lazy Expansion

💡 This approach improves efficiency by using a min-heap to generate pairs on demand, avoiding enumerating all pairs upfront.

Intuition

Start with the smallest possible pair, then incrementally add next candidates by moving pointers in nums2, always extracting the smallest sum pair from a min-heap.

Algorithm

1. Initialize a min-heap and push pairs combining nums1[i] with nums2[0] for i in [0, min(k, len(nums1))].
2. Pop the smallest sum pair from the heap and add it to the result list.
3. If the popped pair used nums2[j], push the pair (nums1[i], nums2[j+1]) into the heap if j+1 < len(nums2).
4. Repeat until k pairs are extracted or heap is empty.

💡 This algorithm efficiently explores pairs in ascending order of sums without generating all pairs.

</>

Code

from typing import List
import heapq

def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    if not nums1 or not nums2 or k == 0:
        return []
    min_heap = []
    result = []
    for i in range(min(k, len(nums1))):
        heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
    while min_heap and len(result) < k:
        current_sum, i, j = heapq.heappop(min_heap)
        result.append([nums1[i], nums2[j]])
        if j + 1 < len(nums2):
            heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))
    return result

# Example usage
if __name__ == '__main__':
    print(kSmallestPairs([1,7,11], [2,4,6], 3))

Line Notes

if not nums1 or not nums2 or k == 0:Handle edge cases with empty inputs or zero k

for i in range(min(k, len(nums1))):Initialize heap with pairs from nums1[i] and nums2[0]

heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))Push sum and indices to heap for ordering

current_sum, i, j = heapq.heappop(min_heap)Extract smallest sum pair from heap

result.append([nums1[i], nums2[j]])Add extracted pair to result

if j + 1 < len(nums2):If next element in nums2 exists, push new pair to heap

heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))Push next candidate pair to heap

import java.util.*;

public class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0 || k == 0) return result;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            minHeap.offer(new int[]{nums1[i] + nums2[0], i, 0});
        }
        while (k > 0 && !minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int i = cur[1], j = cur[2];
            result.add(Arrays.asList(nums1[i], nums2[j]));
            if (j + 1 < nums2.length) {
                minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
            k--;
        }
        return result;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.kSmallestPairs(new int[]{1,7,11}, new int[]{2,4,6}, 3));
    }
}

Line Notes

if (nums1.length == 0 || nums2.length == 0 || k == 0) return result;Handle empty inputs or zero k early

PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));Min-heap ordered by sum

for (int i = 0; i < Math.min(k, nums1.length); i++)Initialize heap with pairs from nums1[i] and nums2[0]

minHeap.offer(new int[]{nums1[i] + nums2[0], i, 0});Push sum and indices to heap

int[] cur = minHeap.poll();Extract smallest sum pair

if (j + 1 < nums2.length)Check if next element in nums2 exists

minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});Push next candidate pair

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<vector<int>> result;
    if (nums1.empty() || nums2.empty() || k == 0) return result;
    auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp);
    for (int i = 0; i < min((int)nums1.size(), k); i++) {
        minHeap.emplace(nums1[i] + nums2[0], i, 0);
    }
    while (k-- > 0 && !minHeap.empty()) {
        auto [sum, i, j] = minHeap.top();
        minHeap.pop();
        result.push_back({nums1[i], nums2[j]});
        if (j + 1 < (int)nums2.size()) {
            minHeap.emplace(nums1[i] + nums2[j + 1], i, j + 1);
        }
    }
    return result;
}

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    int k = 3;
    vector<vector<int>> res = kSmallestPairs(nums1, nums2, k);
    for (auto &p : res) {
        cout << '[' << p[0] << ',' << p[1] << ']';
    }
    cout << '\n';
    return 0;
}

Line Notes

if (nums1.empty() || nums2.empty() || k == 0) return result;Handle edge cases early

auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b)Comparator for min-heap based on sum

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp);Declare min-heap with custom comparator

for (int i = 0; i < min((int)nums1.size(), k); i++)Initialize heap with pairs from nums1[i] and nums2[0]

minHeap.emplace(nums1[i] + nums2[0], i, 0);Push sum and indices to heap

auto [sum, i, j] = minHeap.top();Extract smallest sum pair

if (j + 1 < (int)nums2.size())Check if next element in nums2 exists

minHeap.emplace(nums1[i] + nums2[j + 1], i, j + 1);Push next candidate pair

function kSmallestPairs(nums1, nums2, k) {
    if (nums1.length === 0 || nums2.length === 0 || k === 0) return [];
    const minHeap = new MinPriorityQueue({priority: x => x.sum});
    const result = [];
    for (let i = 0; i < Math.min(k, nums1.length); i++) {
        minHeap.enqueue({sum: nums1[i] + nums2[0], i: i, j: 0});
    }
    while (k > 0 && !minHeap.isEmpty()) {
        const {element} = minHeap.dequeue();
        const {i, j} = element;
        result.push([nums1[i], nums2[j]]);
        if (j + 1 < nums2.length) {
            minHeap.enqueue({sum: nums1[i] + nums2[j + 1], i: i, j: j + 1});
        }
        k--;
    }
    return result;
}

// Example usage
// Note: MinPriorityQueue is available in modern JS environments or via libraries like @datastructures-js/priority-queue
// For demonstration, assume MinPriorityQueue is available

// Uncomment below lines if MinPriorityQueue is available
// console.log(kSmallestPairs([1,7,11], [2,4,6], 3));

Line Notes

if (nums1.length === 0 || nums2.length === 0 || k === 0) return [];Handle empty inputs or zero k early

const minHeap = new MinPriorityQueue({priority: x => x.sum});Initialize min-heap ordered by sum

for (let i = 0; i < Math.min(k, nums1.length); i++)Seed heap with pairs from nums1[i] and nums2[0]

minHeap.enqueue({sum: nums1[i] + nums2[0], i: i, j: 0});Push initial pairs to heap

const {element} = minHeap.dequeue();Extract smallest sum pair

if (j + 1 < nums2.length)Check if next element in nums2 exists

minHeap.enqueue({sum: nums1[i] + nums2[j + 1], i: i, j: j + 1});Push next candidate pair

⏱

Complexity

TimeO(k log k)

SpaceO(k)

We push at most k elements into the heap, each heap operation costs O(log k).

💡 For k=1000, this means roughly 1000 * 10 = 10,000 operations, which is efficient.

Interview Verdict: Accepted and optimal for large inputs

This approach balances efficiency and simplicity, making it ideal for interviews.

🧠

Optimized Min-Heap with Early Termination

💡 This approach is a refinement of the previous heap method, adding early termination and limiting initial heap size to improve performance.

Intuition

Only initialize the heap with the first min(k, len(nums1)) pairs, and stop as soon as k pairs are found, avoiding unnecessary heap operations.

Algorithm

1. Initialize a min-heap with pairs (nums1[i], nums2[0]) for i in [0, min(k, len(nums1))].
2. Pop the smallest pair from the heap and add it to the result.
3. If the next element in nums2 exists for the popped pair, push it into the heap.
4. Stop when k pairs are collected or heap is empty.

💡 This approach avoids pushing unnecessary pairs and terminates early, improving runtime.

</>

Code

from typing import List
import heapq

def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    if not nums1 or not nums2 or k == 0:
        return []
    min_heap = []
    result = []
    n1, n2 = len(nums1), len(nums2)
    for i in range(min(k, n1)):
        heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
    while min_heap and len(result) < k:
        current_sum, i, j = heapq.heappop(min_heap)
        result.append([nums1[i], nums2[j]])
        if j + 1 < n2:
            heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))
    return result

# Example usage
if __name__ == '__main__':
    print(kSmallestPairs([1,7,11], [2,4,6], 3))

Line Notes

n1, n2 = len(nums1), len(nums2)Store lengths to avoid repeated calls

for i in range(min(k, n1))Limit initial heap size to k or nums1 length

heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))Push initial pairs to heap

while min_heap and len(result) < kStop early when k pairs collected

current_sum, i, j = heapq.heappop(min_heap)Extract smallest sum pair

if j + 1 < n2Check if next element in nums2 exists

heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))Push next candidate pair

import java.util.*;

public class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int n1 = nums1.length, n2 = nums2.length;
        if (n1 == 0 || n2 == 0 || k == 0) return result;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < Math.min(k, n1); i++) {
            minHeap.offer(new int[]{nums1[i] + nums2[0], i, 0});
        }
        while (k > 0 && !minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int i = cur[1], j = cur[2];
            result.add(Arrays.asList(nums1[i], nums2[j]));
            if (j + 1 < n2) {
                minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
            k--;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.kSmallestPairs(new int[]{1,7,11}, new int[]{2,4,6}, 3));
    }
}

Line Notes

int n1 = nums1.length, n2 = nums2.length;Store lengths for efficiency

if (n1 == 0 || n2 == 0 || k == 0) return result;Handle edge cases early

for (int i = 0; i < Math.min(k, n1); i++)Limit initial heap size

minHeap.offer(new int[]{nums1[i] + nums2[0], i, 0});Push initial pairs

while (k > 0 && !minHeap.isEmpty())Stop early when k pairs collected

if (j + 1 < n2)Check if next element in nums2 exists

minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});Push next candidate pair

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<vector<int>> result;
    int n1 = nums1.size(), n2 = nums2.size();
    if (n1 == 0 || n2 == 0 || k == 0) return result;
    auto cmp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp);
    for (int i = 0; i < min(n1, k); i++) {
        minHeap.emplace(nums1[i] + nums2[0], i, 0);
    }
    while (k-- > 0 && !minHeap.empty()) {
        auto [sum, i, j] = minHeap.top();
        minHeap.pop();
        result.push_back({nums1[i], nums2[j]});
        if (j + 1 < n2) {
            minHeap.emplace(nums1[i] + nums2[j + 1], i, j + 1);
        }
    }
    return result;
}

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    int k = 3;
    vector<vector<int>> res = kSmallestPairs(nums1, nums2, k);
    for (auto &p : res) {
        cout << '[' << p[0] << ',' << p[1] << ']';
    }
    cout << '\n';
    return 0;
}

Line Notes

int n1 = nums1.size(), n2 = nums2.size();Store lengths for efficiency

if (n1 == 0 || n2 == 0 || k == 0) return result;Handle edge cases early

for (int i = 0; i < min(n1, k); i++)Limit initial heap size

minHeap.emplace(nums1[i] + nums2[0], i, 0);Push initial pairs

while (k-- > 0 && !minHeap.empty())Stop early when k pairs collected

if (j + 1 < n2)Check if next element in nums2 exists

minHeap.emplace(nums1[i] + nums2[j + 1], i, j + 1);Push next candidate pair

function kSmallestPairs(nums1, nums2, k) {
    if (nums1.length === 0 || nums2.length === 0 || k === 0) return [];
    const minHeap = new MinPriorityQueue({priority: x => x.sum});
    const result = [];
    const n1 = nums1.length, n2 = nums2.length;
    for (let i = 0; i < Math.min(k, n1); i++) {
        minHeap.enqueue({sum: nums1[i] + nums2[0], i: i, j: 0});
    }
    while (k > 0 && !minHeap.isEmpty()) {
        const {element} = minHeap.dequeue();
        const {i, j} = element;
        result.push([nums1[i], nums2[j]]);
        if (j + 1 < n2) {
            minHeap.enqueue({sum: nums1[i] + nums2[j + 1], i: i, j: j + 1});
        }
        k--;
    }
    return result;
}

// Example usage
// console.log(kSmallestPairs([1,7,11], [2,4,6], 3));

Line Notes

const n1 = nums1.length, n2 = nums2.length;Store lengths for efficiency

if (nums1.length === 0 || nums2.length === 0 || k === 0) return [];Handle edge cases early

for (let i = 0; i < Math.min(k, n1); i++)Limit initial heap size

minHeap.enqueue({sum: nums1[i] + nums2[0], i: i, j: 0});Push initial pairs

while (k > 0 && !minHeap.isEmpty())Stop early when k pairs collected

if (j + 1 < n2)Check if next element in nums2 exists

minHeap.enqueue({sum: nums1[i] + nums2[j + 1], i: i, j: j + 1});Push next candidate pair

⏱

Complexity

TimeO(k log k)

SpaceO(k)

Same as previous approach but with early termination to avoid unnecessary work.

💡 This approach is the most efficient practical solution for large inputs.

Interview Verdict: Accepted and preferred in interviews

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 The min-heap lazy expansion approach is the best to implement in interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m log(n*m))	O(n*m)	No	Yes	Mention only - never code
2. Min-Heap with Lazy Expansion	O(k log k)	O(k)	No	Yes	Code this approach
3. Optimized Min-Heap with Early Termination	O(k log k)	O(k)	No	Yes	Code this approach if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient and introduce the min-heap approach.Step 4: Code the min-heap solution carefully, explaining each step.Step 5: Discuss optimizations and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to optimize naive solutions, use heaps correctly, and handle edge cases efficiently.

Common Follow-ups

• What if nums1 or nums2 is very large but k is small? → Use min-heap lazy expansion.
• Can you handle duplicates in arrays? → Yes, pairs with same sums are included.
• What if arrays are not sorted? → Sort first or use a different approach.
• How to extend to k-way merges? → Generalize heap initialization and expansion.

💡 These follow-ups test your understanding of constraints, edge cases, and generalization of the pattern.

🔍

Pattern Recognition

When to Use

1) Two sorted arrays or lists, 2) Need to find k smallest/largest pairs or sums, 3) Naive enumeration is too slow, 4) Min-heap or priority queue can be used to generate pairs lazily.

Signature Phrases

'k pairs with smallest sums''two sorted arrays''find k smallest/largest combinations''min heap to generate pairs'

NOT This Pattern When

Problems that require all pairs or sums without k-limiting, or those that use DP instead of heaps.

Similar Problems

Merge K Sorted Lists - similar heap-based mergingFind K Closest Points to Origin - similar k smallest pairs patternTop K Frequent Elements - uses heap to find top k elements

Practice

1. Given the following code snippet for merging k sorted lists using divide and conquer, what is the value of lists[0] after the first iteration of the outer while loop when input lists are:
List 0: 1 -> 4 -> 5
List 1: 1 -> 3 -> 4
List 2: 2 -> 6

easy

A. Merged list starting with 1 -> 1 -> 3 -> 4 -> 4 -> 5

B. Merged list starting with 1 -> 2 -> 3 -> 4 -> 5 -> 6

C. Merged list starting with 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

D. Merged list starting with 1 -> 3 -> 4 -> 5 -> 6

Solution

1. Step 1: Trace first iteration of outer while loop

   Interval = 1, merge lists[0] and lists[1]: merge (1->4->5) and (1->3->4).

2. Step 2: Result of mergeTwoLists(lists[0], lists[1])

   Merged list is 1 -> 1 -> 3 -> 4 -> 4 -> 5. lists[2] remains unchanged.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only first two lists merged in first iteration [OK]

Hint: First merge merges pairs at interval 1 only [OK]

Common Mistakes:

• Merging all lists at once instead of pairs
• Confusing interval doubling
• Assuming full merge after first iteration

2. What is the time complexity of the optimal min-heap based algorithm for finding the smallest range covering k sorted lists, where N is the total number of elements across all lists and k is the number of lists?

medium

A. O(N log k) because each of the N elements is pushed and popped from a heap of size k.

B. O(k log N) because the heap size grows with total elements N and operations depend on k.

C. O(N * k) because each element is processed k times in the heap operations.

D. O(N) because each element is processed exactly once without extra overhead.

Solution

1. Step 1: Analyze heap operations

   Heap size is at most k since it stores one element from each list at a time.

2. Step 2: Count total operations

   Each of the N elements is pushed and popped exactly once, each heap operation costs O(log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size k leads to O(log k) per operation, total N elements processed [OK]

Hint: Heap size k means log k per operation, total N elements [OK]

Common Mistakes:

• Assuming heap size grows with N, confusing log N vs log k
• Multiplying N by k incorrectly
• Ignoring heap operation cost

3. Suppose you want to find the median of K sorted arrays where elements can be reused infinitely (i.e., arrays represent multisets with unlimited copies). Which modification to the optimal binary search approach is correct?

hard

A. Use the same binary search counting method since counts remain valid with infinite reuse.

B. Modify counting to multiply bisect counts by infinity, which is not feasible; thus binary search fails here.

C. Use binary search on value range but replace counting with a formula based on frequency and reuse constraints.

D. Switch to a heap-based approach that tracks counts and duplicates explicitly to handle infinite reuse.

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means counts are unbounded; naive counting fails.

2. Step 2: Adapt counting method

   Counting must use frequency and reuse constraints to compute how many elements ≤ mid considering infinite copies.

3. Step 3: Modify binary search accordingly

   Binary search on value range remains valid but counting function must be formula-based, not bisect-based.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Counting must reflect reuse; naive bisect counting breaks [OK]

Hint: Infinite reuse breaks bisect counting; formula needed [OK]

Common Mistakes:

• Assuming bisect counting works with infinite reuse
• Switching to heap unnecessarily
• Ignoring reuse constraints in counting

4. Suppose the problem changes so that elements from the arrays can be reused multiple times to form sums (i.e., pairs can include the same element multiple times). Which modification to the binary search approach is necessary to correctly find the k-th smallest sum?

hard

A. No modification needed; reuse does not affect counting pairs.

B. Use a min-heap approach with a visited set to handle duplicates and reuse correctly.

C. Modify countPairs to count pairs with replacement by resetting pointer j for each i.

D. Use binary search but countPairs must be replaced with a formula counting sums with repetition.

Solution

1. Step 1: Understand reuse effect on counting

   With reuse allowed, pairs are not limited to unique indices; counting must consider all j for each i.

2. Step 2: Modify countPairs

   Resetting j for each i allows counting all pairs with sums ≤ mid including repeated elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting j ensures correct counting with reuse [OK]

Hint: Reusing elements breaks monotonic pointer j; must reset per i [OK]

Common Mistakes:

• Assuming original countPairs works with reuse
• Using heap without visited set causes duplicates

5. Suppose you want to merge k sorted lists but now each list can contain duplicate values that must be preserved, and you want to return the top M smallest elements overall efficiently. Which modification to the standard divide and conquer approach is best?

hard

A. Continue using divide and conquer merging all lists fully, then slice the first M elements from the merged list.

B. Use dynamic programming to memoize merged prefixes and retrieve top M elements.

C. Concatenate all lists, sort them fully, then return first M elements.

D. Use a min heap to always extract the smallest current node among all lists until M elements are collected.

Solution

1. Step 1: Understand the requirement for top M elements

   We only need the first M smallest elements, not the full merged list.

2. Step 2: Analyze approaches for efficiency

   Divide and conquer merges all lists fully (O(N log k)), which is wasteful if M << N. Concatenation and sort is O(N log N). Min heap approach extracts smallest nodes one by one, stopping after M elements, achieving O(M log k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min heap approach efficiently returns top M elements without full merge [OK]

Hint: Min heap extracts smallest nodes incrementally, ideal for top M [OK]

Common Mistakes:

• Merging all lists fully then slicing wastes time
• Sorting all nodes is inefficient for partial results
• Dynamic programming is not applicable here