Kth Smallest Sum in Two Sorted Arrays

▶

Steps

setup

Initialize low and high bounds

Set low to the smallest possible sum (nums1[0] + nums2[0] = 1+2=3) and high to the largest possible sum (nums1[-1] + nums2[-1] = 11+6=17). This defines the search range for the k-th smallest sum.

💡 Initializing low and high bounds sets the search space for the binary search, which will narrow down to the exact k-th smallest sum.

Line:

low = nums1[0] + nums2[0]
high = nums1[-1] + nums2[-1]

💡 The algorithm starts with the full possible sum range to search within.

expand

Compute mid = (low + high) // 2

Calculate mid as the midpoint of low and high: (3 + 17) // 2 = 10. This mid value will be used to count how many pairs have sums ≤ 10.

💡 Computing mid focuses the search on the middle of the current range, enabling binary search to efficiently narrow down the answer.

Line:

mid = (low + high) // 2

💡 Mid divides the search range to test how many sums are less than or equal to it.

setup

Initialize count and pointer j for counting pairs

Set count to 0 and pointer j to the last index of nums2 (j = 2). We'll iterate over nums1 and move j to count pairs with sums ≤ mid.

💡 Setting up count and pointer j prepares for the two-pointer counting process that efficiently counts valid pairs.

Line:

count = 0
j = len(nums2) - 1

💡 The counting process uses two pointers to avoid checking all pairs explicitly.

traverse

Count pairs for i=0 (nums1[0]=1)

For i=0, check sums with nums2[j]: 1+6=7 ≤ 10, so no decrement of j. Add j+1=3 to count (pairs: (1,2),(1,4),(1,6)).

💡 Counting how many pairs with nums1[0] have sums ≤ mid shows how many valid pairs exist for this i.

Line:

while j >= 0 and nums1[i] + nums2[j] > mid:
    j -= 1
count += (j + 1)

💡 All pairs with nums1[0] and nums2[0..2] are valid since sums ≤ mid.

traverse

Count pairs for i=1 (nums1[1]=7)

For i=1, check sums with nums2[j]: 7+6=13 > 10, decrement j to 1. Now 7+4=11 > 10, decrement j to 0. Then 7+2=9 ≤ 10, add j+1=1 to count.

💡 Moving pointer j down counts only pairs with sums ≤ mid, skipping invalid pairs efficiently.

Line:

while j >= 0 and nums1[i] + nums2[j] > mid:
    j -= 1
count += (j + 1)

💡 Pointer j moves left to exclude pairs with sums exceeding mid.

traverse

Count pairs for i=2 (nums1[2]=11)

For i=2, check sums with nums2[j]: 11+2=13 > 10, decrement j to -1. Since j < 0, add 0 to count.

💡 When pointer j moves out of bounds, no pairs for this i have sums ≤ mid.

Line:

while j >= 0 and nums1[i] + nums2[j] > mid:
    j -= 1
count += (j + 1)

💡 No valid pairs for nums1[2] with sums ≤ mid.

compare

Compare count with k and update low or high

Total count of pairs with sums ≤ 10 is 4, which is ≥ k=3. So set high = mid = 10 to narrow the search to smaller sums.

💡 If count ≥ k, the k-th smallest sum is ≤ mid, so we reduce the high bound to mid.

Line:

if countPairs(nums1, nums2, mid) < k:
    low = mid + 1
else:
    high = mid

💡 Binary search narrows the range to sums ≤ mid when enough pairs exist.

expand

Compute new mid = (low + high) // 2

Calculate mid as (3 + 10) // 2 = 6 to test a smaller sum range.

💡 Recomputing mid focuses the search on the lower half of the previous range.

Line:

mid = (low + high) // 2

💡 Midpoint recalculation continues binary search refinement.

traverse

Count pairs with sums ≤ 6

Reset count=0, j=2. For i=0: 1+6=7 > 6, decrement j=1; 1+4=5 ≤ 6, add j+1=2. For i=1: 7+4=11 > 6, decrement j=0; 7+2=9 > 6, decrement j=-1; add 0. For i=2: j=-1, add 0. Total count=2.

💡 Counting pairs with sums ≤ 6 shows fewer valid pairs than k, so search will move higher.

Line:

count = 0
j = len(nums2) - 1
for i in range(len(nums1)):
    while j >= 0 and nums1[i] + nums2[j] > mid:
        j -= 1
    count += (j + 1)

💡 Too few pairs ≤ mid means k-th sum is larger than mid.

shrink

Update low to mid + 1 because count < k

Since count=2 < k=3, set low = mid + 1 = 7 to search higher sums.

💡 Increasing low narrows the search to sums greater than mid when not enough pairs are found.

Line:

if countPairs(nums1, nums2, mid) < k:
    low = mid + 1

💡 Binary search moves low bound up to exclude sums too small to contain k pairs.

expand

Compute mid = (low + high) // 2 again

Calculate mid = (7 + 10) // 2 = 8 to test sums in the narrowed range.

💡 Mid recalculation continues binary search refinement within updated bounds.

Line:

mid = (low + high) // 2

💡 Midpoint focuses the search on the middle of the new range.

traverse

Count pairs with sums ≤ 8

Reset count=0, j=2. For i=0: 1+6=7 ≤ 8, add j+1=3. For i=1: 7+6=13 > 8, decrement j=1; 7+4=11 > 8, decrement j=0; 7+2=9 > 8, decrement j=-1; add 0. For i=2: j=-1, add 0. Total count=3.

💡 Counting pairs with sums ≤ 8 finds exactly k=3 pairs, so high will be updated.

Line:

count = 0
j = len(nums2) - 1
for i in range(len(nums1)):
    while j >= 0 and nums1[i] + nums2[j] > mid:
        j -= 1
    count += (j + 1)

💡 Enough pairs ≤ mid means the k-th smallest sum is ≤ mid.

shrink

Update high to mid because count ≥ k

Set high = mid = 8 to narrow the search to sums ≤ 8.

💡 Reducing high bounds the search to sums that still contain at least k pairs.

Line:

else:
    high = mid

💡 Binary search narrows the upper bound to mid when count is sufficient.

expand

Compute mid = (low + high) // 2 again

Calculate mid = (7 + 8) // 2 = 7 to test sums in the tighter range.

💡 Mid recalculation continues binary search refinement.

Line:

mid = (low + high) // 2

💡 Midpoint focuses the search on the middle of the new range.

traverse

Count pairs with sums ≤ 7

Reset count=0, j=2. For i=0: 1+6=7 ≤ 7, add j+1=3. For i=1: 7+6=13 > 7, decrement j=1; 7+4=11 > 7, decrement j=0; 7+2=9 > 7, decrement j=-1; add 0. For i=2: j=-1, add 0. Total count=3.

💡 Counting pairs with sums ≤ 7 finds exactly k=3 pairs again, confirming the k-th smallest sum.

Line:

count = 0
j = len(nums2) - 1
for i in range(len(nums1)):
    while j >= 0 and nums1[i] + nums2[j] > mid:
        j -= 1
    count += (j + 1)

💡 Count confirms that 7 is a valid candidate for the k-th smallest sum.

shrink

Update high to mid again

Set high = mid = 7 to narrow the search to sums ≤ 7.

💡 Reducing high bounds the search to sums that still contain at least k pairs.

Line:

else:
    high = mid

💡 Binary search narrows the upper bound to mid when count is sufficient.

compare

Check if low < high to continue binary search

Since low = 7 and high = 7, low is not less than high, so the binary search loop ends.

💡 When low meets high, the search has converged to the k-th smallest sum.

Line:

while low < high:

💡 Binary search termination condition reached.

reconstruct

Return the k-th smallest sum

Return low (which is 7) as the k-th smallest sum of pairs from nums1 and nums2.

💡 The binary search result low is the exact k-th smallest sum, completing the algorithm.

Line:

return low

💡 The algorithm efficiently finds the k-th smallest sum without enumerating all pairs.

def countPairs(nums1, nums2, mid):  # STEP 3,4,5,6,9,12,15
    count = 0
    j = len(nums2) - 1
    for i in range(len(nums1)):
        while j >= 0 and nums1[i] + nums2[j] > mid:
            j -= 1
        count += (j + 1)
    return count

def kthSmallestSum(nums1, nums2, k):  # STEP 1,2,7,8,10,11,13,14,16,17,18
    low = nums1[0] + nums2[0]  # STEP 1
    high = nums1[-1] + nums2[-1]  # STEP 1
    while low < high:  # STEP 17
        mid = (low + high) // 2  # STEP 2,8,11,14
        if countPairs(nums1, nums2, mid) < k:  # STEP 7,10,13,16
            low = mid + 1
        else:
            high = mid
    return low  # STEP 18

if __name__ == '__main__':
    nums1 = [1,7,11]
    nums2 = [2,4,6]
    k = 3
    print(kthSmallestSum(nums1, nums2, k))  # Output: 7

📊

Kth Smallest Sum in Two Sorted Arrays - Watch the Algorithm Execute, Step by Step

Watching each step of the binary search and counting process reveals how the algorithm narrows down the k-th smallest sum without enumerating all pairs.

insertmin-heap

3

0

17

1

insertmin-heap

3

0

17

1

10

2

insertmin-heap

2

0

comparemin-heap

0

0

2

1

Added: 3

comparemin-heap

1

0

0

1

Added: 4

comparemin-heap

2

0

-1

1

Added: 4

insertmin-heap

3

0

10

1

insertmin-heap

3

0

10

1

6

2

comparemin-heap

0

0

1

1

2

2

Added: 2

insertmin-heap

7

0

10

1

insertmin-heap

7

0

10

1

8

2

comparemin-heap

0

0

2

1

3

2

Added: 3

insertmin-heap

7

0

8

1

insertmin-heap

7

0

8

1

7

2

comparemin-heap

0

0

2

1

3

2

Added: 3

insertmin-heap

7

0

7

1

peekmin-heap

7

0

Added: 7

peekmin-heap

7

0

Added: 7

Key Takeaways

✓ Binary search on the sum range efficiently narrows down the k-th smallest sum without enumerating all pairs.

Reading code alone doesn't reveal how the search space shrinks step-by-step; visualization shows the bounds adjusting clearly.

✓ Two-pointer counting quickly determines how many pairs have sums ≤ mid, enabling the binary search decision.

The pointer j moving left to exclude invalid pairs is easier to grasp visually than from code.

✓ The algorithm converges when low meets high, guaranteeing the exact k-th smallest sum is found.

Understanding the termination condition and final answer extraction is clearer when watching the binary search bounds meet.

Practice

1. You are given k sorted arrays and need to merge them into one sorted array efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Use a divide and conquer approach to iteratively merge pairs of arrays until one remains.

B. Use a greedy approach by always picking the smallest element from any array without additional data structures.

C. Use dynamic programming to build the merged array by choosing elements optimally.

D. Concatenate all arrays and sort the combined array once at the end.

Solution

1. Step 1: Understand the problem constraints

   We have k sorted arrays and want to merge them efficiently into one sorted array.

2. Step 2: Analyze approaches

   Concatenating and sorting is simple but takes O(N log N) time, where N is total elements. Dynamic programming is not applicable here. Greedy without a data structure cannot efficiently find the global minimum across arrays. Divide and conquer merges pairs of arrays repeatedly, reducing the number of arrays by half each iteration, achieving O(N log k) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer merges pairs efficiently -> O(N log k) [OK]

Hint: Divide and conquer merges pairs efficiently [OK]

Common Mistakes:

• Thinking sorting concatenated array is optimal
• Confusing greedy with heap-based approach
• Applying DP where not suitable

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

3. The following code attempts to assign jobs to machines optimally. Which line contains a subtle bug that can cause incorrect scheduling?

medium

A. Line 5: Using enumerate without sorting jobs by start time.

B. Line 9: heapq.heapify(available) to initialize available machines heap.

C. Line 13: While loop condition to free machines before assignment.

D. Line 17: Calculating finish_time as start + duration.

Solution

1. Step 1: Identify the bug

   The code uses indexed_jobs = enumerate(jobs) without sorting jobs by start time, which breaks chronological processing.

2. Step 2: Consequences of missing sorting

   Without sorting, jobs may be assigned out of order, causing machines to be assigned incorrectly or appear busy when they should be free.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting jobs by start time is essential for correct scheduling [OK]

Hint: Jobs must be sorted by start time before assignment [OK]

Common Mistakes:

• Forgetting to sort jobs by start time
• Not freeing machines before assigning new jobs
• Incorrect finish time calculation

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

5. Suppose the problem is modified so that elements in the lists can be reused multiple times (i.e., you can pick the same element multiple times from the same list). Which modification to the optimal min-heap approach correctly handles this variant?

hard

A. Continue using the min-heap approach but do not advance the index in the list after pushing the next element, allowing reuse of the same element.

B. Use a min-heap but track counts of elements used per list and only advance indices when all elements have been used once.

C. Modify the algorithm to allow pushing the same element multiple times without advancing the index, but update current_max accordingly to avoid infinite loops.

D. The min-heap approach cannot be adapted; instead, use a dynamic programming approach to handle reuse.

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means the same element can be counted multiple times, so indices alone do not track usage.

2. Step 2: Modify tracking mechanism

   Tracking counts of usage per list and advancing indices only after all elements are used once prevents infinite loops and ensures coverage.

3. Step 3: Why other options fail

   Not advancing indices leads to infinite loops; pushing same element multiple times without control breaks correctness; DP is inefficient here.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking usage counts ensures correct reuse handling [OK]

Hint: Track usage counts per list to handle reuse correctly [OK]

Common Mistakes:

• Not advancing indices causing infinite loops
• Pushing duplicates without control
• Switching to DP unnecessarily