Find K Pairs with Smallest Sums

📋

Find K Pairs with Smallest Sums

Edge cases:

</>

IDE

def kSmallestPairs(nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k)vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k)function kSmallestPairs(nums1, nums2, k)

def kSmallestPairs(nums1, nums2, k):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    // Write your solution here
    return {};
}

function kSmallestPairs(nums1, nums2, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,2],[2,1],[1,4]]Greedy approach picking pairs by smallest first element without considering sums.✅ Use a min-heap keyed by sum and expand pairs lazily by advancing indices.

Wrong: [[1,1],[1,1],[1,2],[1,2],[1,1]]Reusing pairs multiple times causing duplicates and infinite loops.✅ Track visited pairs and only push new pairs with unique indices.

Wrong: [[1,2],[1,4]]Fails to handle empty input arrays or returns partial results.✅ Add early return if either input array is empty.

Wrong: [[1,3],[1,4]]Returns fewer pairs than k when k exceeds total pairs.✅ Return all pairs sorted by sum if k is larger than total pairs.

Wrong: Timeout or no outputBrute force approach enumerating all pairs causing TLE.✅ Implement min-heap lazy expansion approach with O(k log k) complexity.

✓

Test Cases

Try testing your code with empty and minimal inputs to catch base case bugs.

Consider tricky cases with duplicates and negative numbers to expose algorithmic mistakes.

Test performance with large inputs to ensure your solution scales efficiently.

t1_01basic

Input{"nums1":[1,7,11],"nums2":[2,4,6],"k":3}

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

⏱ Performance - must finish in 2000ms

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

💡 Use a min-heap to efficiently find the smallest sum pairs.

💡 Initialize the heap with pairs combining the first element of nums1 with each element of nums2.

💡 Pop from heap and push next pairs by advancing indices to generate pairs lazily.

Why it failed: Failed to produce correct smallest pairs; likely incorrect heap initialization or pair generation logic. Fix by ensuring pairs are pushed in order and heap always contains next candidate pairs.

✓ Correctly returns the k pairs with smallest sums using heap-based approach.

t1_02basic

Input{"nums1":[1,1,2],"nums2":[1,2,3],"k":2}

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

⏱ Performance - must finish in 2000ms

The smallest sums are (1,1)=2 and (1,1)=2 from the first two pairs.

💡 Duplicates in arrays can produce pairs with same sums; handle duplicates correctly.

💡 Heap should allow multiple pairs with same sums and different indices.

💡 Ensure pairs are generated in order and duplicates are not skipped.

Why it failed: Incorrect handling of duplicates or pair ordering; possibly skipping pairs with equal sums. Fix by allowing duplicates and maintaining correct order in heap.

✓ Correctly handles duplicates and returns pairs with smallest sums in order.

t2_01edge

Input{"nums1":[],"nums2":[1,2,3],"k":3}

Expected[]

⏱ Performance - must finish in 2000ms

Empty nums1 means no pairs can be formed; result is empty list.

💡 Check for empty input arrays before processing.

💡 If either array is empty, return empty list immediately.

💡 Add a guard clause to handle empty inputs.

Why it failed: Code does not handle empty input arrays; returns non-empty or errors. Fix by adding early return if nums1 or nums2 is empty.

✓ Correctly returns empty list when one input array is empty.

t2_02edge

Input{"nums1":[5],"nums2":[10],"k":1}

Expected[[5,10]]

⏱ Performance - must finish in 2000ms

Single element arrays produce exactly one pair.

💡 Handle single-element arrays correctly.

💡 Ensure code does not assume multiple elements for iteration.

💡 Return the single pair if k >= 1.

Why it failed: Fails on single-element arrays; possibly index errors or incorrect loop bounds. Fix by handling single-element arrays without assumptions.

✓ Correctly returns the single pair from single-element arrays.

t2_03edge

Input{"nums1":[1,2],"nums2":[3,4],"k":10}

Expected[[1,3],[1,4],[2,3],[2,4]]

⏱ Performance - must finish in 2000ms

k larger than total pairs (4) returns all pairs sorted by sum.

💡 Check if k exceeds total possible pairs (nums1.length * nums2.length).

💡 Return all pairs if k is larger than total pairs.

💡 Sort all pairs by sum if returning all.

Why it failed: Fails to return all pairs when k is too large; returns fewer pairs or errors. Fix by bounding k to total pairs and returning all pairs sorted.

✓ Correctly returns all pairs when k exceeds total possible pairs.

t2_04edge

Input{"nums1":[-5,-3,-1],"nums2":[-2,0,2],"k":4}

Expected[[-5,-2],[-5,0],[-3,-2],[-5,2]]

⏱ Performance - must finish in 2000ms

Handles negative numbers correctly in pairs with smallest sums.

💡 Negative numbers can produce smaller sums; do not ignore negative values.

💡 Heap-based approach naturally handles negative and positive values.

💡 Ensure pairs are generated in order by sum, including negatives.

Why it failed: Fails to handle negative numbers correctly; returns wrong pairs or misses pairs. Fix by not filtering negatives and allowing all pairs.

✓ Correctly returns smallest sum pairs including negatives.

t3_01corner

Input{"nums1":[1,2,3],"nums2":[1,2,3],"k":5}

Expected[[1,1],[1,2],[2,1],[1,3],[2,2]]

⏱ Performance - must finish in 2000ms

Greedy approach picking pairs by smallest first element fails; correct pairs require heap-based expansion.

💡 Greedy approach picking pairs only by smallest first element is incorrect.

💡 Use min-heap to explore pairs by sum, not just first element.

💡 Push next candidate pairs by advancing second array index for each popped pair.

Why it failed: Greedy approach returns incorrect pairs missing smaller sums; fix by using min-heap with lazy expansion of pairs.

✓ Correctly returns smallest sum pairs avoiding greedy trap.

t3_02corner

Input{"nums1":[1,1,2],"nums2":[1,2,3],"k":4}

Expected[[1,1],[1,1],[1,2],[1,2]]

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded: each pair can be used once; do not reuse pairs multiple times.

💡 Pairs are unique combinations of indices; do not reuse pairs multiple times.

💡 Track indices used to avoid duplicates and infinite loops.

💡 Use a visited set or careful index advancement to avoid reusing pairs.

Why it failed: Incorrectly reuses pairs multiple times causing duplicates and infinite loops; fix by tracking visited pairs and advancing indices properly.

✓ Correctly handles unique pairs without reuse.

t3_03corner

Input{"nums1":[-10,-4,0,0,6],"nums2":[3,5,6,7,8,100],"k":10}

Expected[[-10,3],[-10,5],[-4,3],[-10,6],[-4,5],[-10,7],[-4,6],[0,3],[0,5],[0,6]]

⏱ Performance - must finish in 2000ms

Handles negative numbers and duplicates correctly in pairs with smallest sums.

💡 Negative numbers can produce smaller sums; do not ignore negative values.

💡 Duplicates in nums1 or nums2 can produce duplicate sums; handle all pairs.

💡 Heap-based approach naturally handles negative and duplicate values.

Why it failed: Fails to handle negative numbers or duplicates correctly; returns wrong pairs or misses pairs. Fix by not filtering negatives and allowing duplicates.

✓ Correctly returns smallest sum pairs including negatives and duplicates.

t4_01performance

Input{"nums1":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"nums2":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":10000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, k=10000; O(k log k) heap approach must complete within 2 seconds.

💡 Brute force O(n*m) approach will time out for large inputs.

💡 Use min-heap with lazy expansion to achieve O(k log k) time.

💡 Avoid enumerating all pairs; generate pairs on demand.

Why it failed: Brute force or naive approach causes TLE due to O(n*m) complexity; fix by implementing min-heap lazy expansion with O(k log k) complexity.

✓ Efficient heap-based solution runs within time limits.

Practice

1. You are given two sorted arrays and need to find the k-th smallest sum formed by adding one element from each array. Which approach guarantees an optimal solution in terms of time complexity for large input sizes?

easy

A. Use binary search on the sum range combined with a counting function to find how many pairs have sums less than or equal to mid.

B. Use dynamic programming to build a table of sums and select the k-th smallest.

C. Use a greedy approach by always picking the smallest available sum without revisiting pairs.

D. Generate all possible sums, sort them, and pick the k-th smallest sum.

Solution

1. Step 1: Understand problem constraints

   Brute force (generating all sums) is too slow for large inputs.

2. Step 2: Identify efficient approach

   Binary search on sum range with counting pairs ≤ mid efficiently narrows down the k-th smallest sum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search reduces search space logarithmically [OK]

Hint: Binary search on sums beats brute force for large inputs [OK]

Common Mistakes:

• Assuming greedy approach always works
• Using DP which is inefficient here

2. You need to generate the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently merges multiple sorted sequences generated by multiplying previously found numbers by these primes?

easy

A. Use a min-heap to merge multiple sorted sequences generated by multiplying known ugly numbers by 2, 3, and 5, while avoiding duplicates.

B. Use a greedy approach that picks the smallest next candidate without tracking duplicates or previously generated numbers.

C. Use a brute force check for each number to test if it only has 2, 3, and 5 as prime factors.

D. Use a dynamic programming approach with three pointers to merge sequences but without a heap.

Solution

1. Step 1: Understand the problem structure

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, which can be seen as merging three sorted sequences: multiples of 2, 3, and 5 of previously found ugly numbers.

2. Step 2: Identify the optimal merging technique

   A min-heap efficiently merges these sequences by always extracting the smallest next candidate and avoids duplicates by tracking seen numbers, ensuring optimal time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap merges k sorted sequences optimally [OK]

Hint: Min-heap merges multiple sorted sequences efficiently [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Ignoring duplicates in merging
• Using greedy without tracking duplicates

3. What is the time complexity of the optimal binary search on value range approach to find the median of K sorted arrays, each of average length N, with value range size M?

medium

A. O(K * log M * log N)

B. O(K * N * log M)

C. O(K * N * log N)

D. O(K * log N * log M)

Solution

1. Step 1: Analyze binary search outer loop

   Binary search on value range M takes O(log M) steps.

2. Step 2: Analyze counting elements ≤ mid

   Counting uses binary search on each array of length N, costing O(log N) per array, total O(K log N).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(K log M log N) [OK]

Hint: Counting uses binary search per array, not linear scan [OK]

Common Mistakes:

• Assuming linear scan over arrays (O(KN))
• Confusing N and M in complexity
• Ignoring binary search inside counting

4. Consider this modified code snippet for nth super ugly number. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line where val is appended to ugly without checking duplicates

B. Line where initial primes are pushed into the heap

C. Line where heap is initialized as an empty list

D. Line where new heap element is pushed with updated index

Solution

1. Step 1: Identify difference from correct code

   The original code checks if val != ugly[-1] before appending to avoid duplicates.

2. Step 2: Understand impact of missing duplicate check

   Appending duplicates causes the sequence to have repeated numbers, leading to incorrect nth number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate values break the strictly increasing sequence [OK]

Hint: Check for duplicate filtering when appending new ugly numbers [OK]

Common Mistakes:

• Forgetting to skip duplicates when popping from heap
• Incorrect heap push indices
• Misinitializing heap elements

5. 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