Kth Smallest Sum in Two Sorted Arrays

📋

Kth Smallest Sum in Two Sorted Arrays

Edge cases:

</>

IDE

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

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

class Solution {
    public int kthSmallestSum(int[] nums1, int[] nums2, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: Incorrect sum smaller than expectedGreedy approach picking smallest elements independently without proper pair expansion.✅ Use a min-heap to expand pairs by indices (i+1,j) and (i,j+1) with a visited set to avoid duplicates.

Wrong: IndexError or out-of-range exceptionNot checking array bounds when pushing next pairs into heap.✅ Check indices before pushing (i+1,j) or (i,j+1) into heap to avoid out-of-range errors.

Wrong: Wrong sum due to ignoring duplicatesVisited set tracks sums instead of pairs of indices, causing duplicate sums to be skipped.✅ Track visited pairs by their indices (i,j) to correctly handle duplicates.

Wrong: TLE or timeoutBrute force approach enumerating all pairs and sorting them.✅ Implement min-heap with pair expansion and visited set for O(k log k) complexity.

Wrong: Off-by-one error returning wrong k-th sumIncorrect loop count or indexing when popping from heap.✅ Pop exactly k times from the min-heap and return the last popped sum.

✓

Test Cases

Focus on handling smallest and largest k values and arrays with negative numbers.

Watch out for greedy traps and duplicates; ensure your visited set tracks pairs correctly.

Optimize your solution to avoid enumerating all pairs; use a min-heap with pair expansion.

t1_01basic

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

Expected7

⏱ Performance - must finish in 2000ms

The pairs sorted by sum are (1+2=3), (1+4=5), (1+6=7), (7+2=9), (7+4=11), (11+2=13), ... The 3rd smallest sum is 7.

💡 Think about merging sorted pairs using a min-heap.

💡 Use a min-heap to track the next smallest pair sums and a visited set to avoid duplicates.

💡 Initialize heap with (nums1[0]+nums2[0]) and expand pairs by incrementing indices carefully.

Why it failed: Returned wrong sum for canonical example; likely missing pair expansion or visited set check. Fix by pushing next pairs (i+1,j) and (i,j+1) into heap only if not visited.

✓ Correctly finds the 3rd smallest sum using heap-based pair expansion.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

Pairs sums sorted: 2(1+1), 3(1+2), 3(2+1), 4(1+3), ... The 4th smallest sum is 3 (the second occurrence of sum=3).

💡 Remember sums can repeat; track pairs uniquely with indices.

💡 Use a min-heap and a visited set to avoid counting duplicates incorrectly.

💡 Pop k times from heap; the k-th popped sum is the answer.

Why it failed: Incorrect output due to ignoring duplicates or not using visited set; fix by storing visited pairs and pushing neighbors only once.

✓ Handles duplicates correctly and returns the correct k-th smallest sum.

t2_01edge

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

Expected3

⏱ Performance - must finish in 2000ms

Only one pair (1+2=3), so k=1 returns 3.

💡 Check behavior when arrays have only one element each.

💡 The smallest sum is simply nums1[0] + nums2[0].

💡 Return sum directly without complex logic for single-element arrays.

Why it failed: Fails single-element case by overcomplicating or indexing out of range; fix by handling single-element arrays correctly.

✓ Correctly returns sum for single-element arrays.

t2_02edge

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

Expected6

⏱ Performance - must finish in 2000ms

All pairs sums: 4(1+3),5(1+4),5(2+3),6(2+4). The 4th smallest sum is 6.

💡 Test the exact boundary where k equals total pairs count.

💡 Ensure algorithm handles k = len(nums1)*len(nums2) correctly.

💡 Return the largest pair sum when k equals total pairs.

Why it failed: Fails boundary k by returning smaller sums or indexing errors; fix by allowing full enumeration or correct heap expansion until k-th sum.

✓ Correctly returns largest sum when k equals total pairs.

t2_03edge

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

Expected-2

⏱ Performance - must finish in 2000ms

Pairs sums sorted: -7(-5+-2), -4(-5+1), -3(-3+-2), -2(-3+1), 0(0+-2), ... The 5th smallest sum is -2.

💡 Arrays can contain negative numbers; sums may be negative.

💡 Ensure heap and visited set handle negative sums correctly.

💡 Do not assume sums are always positive; compare sums properly.

Why it failed: Fails negative sums by assuming non-negative or incorrect comparisons; fix by using correct sum comparisons and heap ordering.

✓ Handles negative sums correctly and returns accurate k-th smallest sum.

t2_04edge

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

Expected5

⏱ Performance - must finish in 2000ms

All pairs sum to 5 (2+3). The 5th smallest sum is 5.

💡 Arrays contain duplicates; sums may repeat.

💡 Ensure visited set tracks pairs by indices, not sums.

💡 Return sum of first pair popped from heap if all sums equal.

Why it failed: Fails duplicate sums by skipping or merging duplicates incorrectly; fix by tracking visited pairs by indices.

✓ Handles duplicates correctly and returns the correct sum.

t3_01corner

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

Expected22

⏱ Performance - must finish in 2000ms

Pairs sums sorted: 11(1+10),12(2+10),13(3+10),21(1+20),22(2+20),23(3+20), ... The 5th smallest sum is 22.

💡 Beware of greedy approach picking smallest elements independently without proper pair expansion.

💡 Use min-heap with pair expansion to correctly explore sums.

💡 Push neighbors (i+1,j) and (i,j+1) to heap to avoid missing sums.

Why it failed: Fails greedy trap by incorrectly assuming sums increase linearly; fix by using min-heap with pair expansion.

✓ Correctly avoids greedy trap and finds accurate k-th smallest sum.

t3_02corner

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

Expected2

⏱ Performance - must finish in 2000ms

All pairs sum to 2 (1+1). The 5th smallest sum is 2.

💡 Arrays contain duplicates; sums may repeat.

💡 Ensure visited set tracks pairs by indices, not sums.

💡 Return sum of first pair popped from heap if all sums equal.

Why it failed: Fails duplicate sums by skipping or merging duplicates incorrectly; fix by tracking visited pairs by indices.

✓ Handles duplicates correctly and returns the correct sum.

t3_03corner

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

Expected11

⏱ Performance - must finish in 2000ms

Total pairs = 9; largest sum is 11 (5+6). The 9th smallest sum is 11.

💡 Check off-by-one errors when k equals total pairs.

💡 Ensure heap expansion covers all pairs without missing last.

💡 Return last popped sum after k pops from heap.

Why it failed: Off-by-one error causes returning smaller sum or index error; fix by popping exactly k times from heap.

✓ Correctly handles off-by-one and returns largest sum for k=total pairs.

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":5000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, k=5000; O(k log k) heap approach must complete within 2 seconds; brute force O(n*m) = 10,000 pairs is too slow.

💡 Brute force enumerating all pairs is O(n*m) and will TLE.

💡 Use min-heap with pair expansion and visited set for O(k log k) complexity.

💡 Avoid generating all pairs; expand only k pairs from heap.

Why it failed: TLE due to brute force O(n*m) approach; fix by implementing min-heap with pair expansion and visited set for O(k log k).

✓ Efficient heap-based solution runs within time limit.

Practice

1. What is the time complexity of the divide and conquer approach to merge k sorted arrays with a total of N elements?

medium

A. O(N log N) because each merge sorts the combined arrays

B. O(N log k) because merging pairs reduces arrays by half each iteration

C. O(k N) because each of the k arrays is merged sequentially

D. O(N k) because each element is compared with k arrays

Solution

1. Step 1: Identify number of merge rounds

   Divide and conquer merges pairs of arrays, halving the number of arrays each round, so log k rounds.

2. Step 2: Calculate work per round

   Each round merges all N elements once, so O(N) per round.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   O(N) work per round x log k rounds -> O(N log k) [OK]

Hint: Divide and conquer halves arrays each round -> log k rounds [OK]

Common Mistakes:

• Confusing total elements N with number of arrays k
• Assuming sorting entire array each time
• Multiplying N by k incorrectly

2. Consider the following buggy code snippet for merging two sorted linked lists. Which line contains the subtle bug that can cause an infinite loop or lost nodes?

medium

A. Line advancing l1 or l2 pointer

B. Line missing advancement of current pointer after assignment

C. Line assigning current.next inside the if block

D. Line assigning current.next to remaining list after loop

Solution

1. Step 1: Identify pointer updates inside loop

   current.next is assigned but current pointer is not advanced.

2. Step 2: Consequence of missing current advancement

   Without current = current.next, current.next keeps overwriting same node, causing infinite loop or lost nodes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing current pointer advancement causes infinite loop [OK]

Hint: Always advance current pointer after linking a node [OK]

Common Mistakes:

• Forgetting to move current pointer after linking
• Misplacing pointer updates causing lost nodes
• Confusing l1/l2 advancement with current advancement

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

4. Suppose the problem is modified so that elements from nums2 can be reused multiple times in pairs (i.e., pairs can reuse the same element from nums2 multiple times). Which modification to the min-heap approach correctly handles this variant?

hard

A. Push all pairs (nums1[i] + nums2[j]) for all i, j into the heap initially and pop k times.

B. After popping a pair (i, j), push (i, j+1) and also push (i+1, j) if within bounds, allowing reuse of nums2 elements.

C. After popping a pair (i, j), push (i, j) again to allow reuse of nums2[j].

D. Modify the heap to store sums with counts of usage and only push new pairs when usage count is less than k.

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse of nums2 elements means after using nums2[j], we can also try nums2[j+1] and nums2[j] again with next nums1 element.

2. Step 2: Modify heap push logic

   After popping (i, j), pushing (i, j+1) continues along nums2, and pushing (i+1, j) allows pairing next nums1 element with the same nums2[j], enabling reuse.

3. Step 3: Reject other options

   Push all pairs (nums1[i] + nums2[j]) for all i, j into the heap initially and pop k times. is brute force and inefficient. After popping a pair (i, j), push (i, j) again to allow reuse of nums2[j]. causes infinite loops by pushing same pair repeatedly. Modify the heap to store sums with counts of usage and only push new pairs when usage count is less than k. is unnecessarily complex and not standard.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   After popping a pair (i, j), push (i, j+1) and also push (i+1, j) if within bounds, allowing reuse of nums2 elements. correctly expands pairs to allow reuse without infinite loops [OK]

Hint: Push next nums1 with same nums2 to allow reuse [OK]

Common Mistakes:

• Pushing same pair repeatedly causing infinite loops
• Brute forcing all pairs initially
• Overcomplicating usage counts

5. Suppose the problem changes: now you want to find the nth ugly number but you can reuse the same ugly number multiple times in generating new numbers (i.e., duplicates allowed). Which modification to the min-heap approach correctly handles this variant without losing correctness or efficiency?

hard

A. Remove the 'seen' set entirely and push all generated numbers into the heap, allowing duplicates.

B. Keep the 'seen' set but reset it after every iteration to allow reuse of numbers in the next iteration.

C. Use a counter map to track how many times each number is generated and only push if count is below a threshold.

D. Keep the 'seen' set as is to avoid duplicates, since duplicates do not affect correctness or efficiency.

Solution

1. Step 1: Understand the variant allowing duplicates

   Allowing reuse means duplicates are valid and should be generated and processed multiple times.

2. Step 2: Modify the algorithm accordingly

   Removing the 'seen' set allows duplicates to be pushed and popped, correctly reflecting the new problem constraints.

3. Step 3: Consider efficiency

   Though duplicates increase heap size, this is necessary to correctly generate all numbers under the new rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing 'seen' allows duplicates as required [OK]

Hint: Allow duplicates by removing 'seen' when reuse is allowed [OK]

Common Mistakes:

• Keeping 'seen' and missing duplicates
• Resetting 'seen' incorrectly
• Using counters unnecessarily