Find K Pairs with Smallest Sums

▶

Steps

setup

Initialize min-heap with first pairs

Push pairs formed by each element in nums1 with the first element in nums2 into the min-heap. This sets up the initial candidates for smallest sums.

💡 Initializing the heap with these pairs allows the algorithm to efficiently track the smallest sums starting from the smallest elements in nums2.

Line:

for i in range(min(k, n1)):
    heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))

💡 The heap now contains pairs (3,0,0), (9,1,0), and (13,2,0), representing sums 3, 9, and 13 respectively.

delete

Extract smallest pair from heap

Pop the root of the heap, which is the pair with the smallest sum (3, corresponding to nums1[0]=1 and nums2[0]=2). Add this pair to the result.

💡 Extracting the smallest pair ensures we add pairs to the result in ascending order of their sums.

Line:

current_sum, i, j = heapq.heappop(min_heap)
result.append([nums1[i], nums2[j]])

💡 The pair (1,2) with sum 3 is confirmed as the smallest and added to the output.

insert

Push next pair from nums2 for extracted nums1 index

Since the extracted pair used nums2 index 0, push the next pair with nums2 index 1 for the same nums1 index (0). This pair is (1 + 4 = 5).

💡 Adding the next pair from nums2 for the same nums1 element keeps the heap updated with the next smallest possible sums.

Line:

if j + 1 < n2:
    heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))

💡 The heap now contains pairs with sums 5, 9, and 13, maintaining candidates for smallest sums.

delete

Extract next smallest pair from heap

Pop the root of the heap, which now is the pair with sum 5 (nums1[0]=1, nums2[1]=4). Add this pair to the result.

💡 Continuing to extract the smallest pair ensures the result list is sorted by sum.

Line:

current_sum, i, j = heapq.heappop(min_heap)
result.append([nums1[i], nums2[j]])

💡 The pair (1,4) with sum 5 is the next smallest and added to the output.

insert

Push next pair from nums2 for extracted nums1 index

For the extracted pair with nums1 index 0 and nums2 index 1, push the next pair with nums2 index 2: (1 + 6 = 7).

💡 This step continues to explore pairs along nums2 for the same nums1 element, ensuring no smaller pairs are missed.

Line:

if j + 1 < n2:
    heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))

💡 The heap now contains pairs with sums 7, 9, and 13.

delete

Extract next smallest pair from heap

Pop the root of the heap, which is the pair with sum 7 (nums1[0]=1, nums2[2]=6). Add this pair to the result.

💡 Extracting this pair completes the required k=3 pairs with smallest sums.

Line:

current_sum, i, j = heapq.heappop(min_heap)
result.append([nums1[i], nums2[j]])

💡 The pair (1,6) with sum 7 is the third smallest and added to the output.

compare

Check if more pairs needed

Check if the result length has reached k=3. Since it has, the algorithm will stop and return the result.

💡 This condition prevents unnecessary processing once the required number of pairs is found.

Line:

while min_heap and len(result) < k:

💡 The algorithm terminates early, optimizing performance.

heapify_down

Heapify down after insertion to maintain heap property

After inserting a new pair, the heapify_down operation ensures the min-heap property is maintained by swapping elements as needed.

💡 Heapify down is crucial to keep the smallest sum pair at the root after insertions.

Line:

heapq._siftup(min_heap, 0)  # Conceptual operation to maintain heap

💡 Heapify down maintains the heap invariant, ensuring efficient extraction of the smallest pair.

heapify_down

Heapify down after extraction to maintain heap property

After extracting the root, heapify_down restores the min-heap property by moving the new root down as needed.

💡 Heapify down after extraction ensures the next smallest pair is at the root for the next extraction.

Line:

heapq._siftup(min_heap, 0)  # Conceptual operation after pop

💡 Maintaining the heap invariant after extraction is key to the algorithm's correctness.

reconstruct

Final result assembled

Return the collected pairs [[1,2],[1,4],[1,6]] as the k pairs with smallest sums.

💡 The final step confirms the output matches the expected smallest sum pairs.

Line:

return result

💡 The heap-based approach efficiently finds the smallest pairs without enumerating all combinations.

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)
    # STEP 1: Initialize heap with pairs (nums1[i], nums2[0])
    for i in range(min(k, n1)):
        heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
    # STEP 2-7: Extract min and push next pairs until k pairs collected
    while min_heap and len(result) < k:
        current_sum, i, j = heapq.heappop(min_heap)  # STEP 2,4,6
        result.append([nums1[i], nums2[j]])          # STEP 2,4,6
        if j + 1 < n2:                              # STEP 3,5
            heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))
    # STEP 8: Return result
    return result

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

📊

Find K Pairs with Smallest Sums - Watch the Algorithm Execute, Step by Step

Watching the heap operations step-by-step reveals how the algorithm efficiently merges pairs without enumerating all combinations, which is key to understanding the optimization.

insertmin-heap

3,0,0

0

9,1,0

1

13,2,0

2

extract_minmin-heap

9,1,0

0

13,2,0

1

Added: [1,2]

insertmin-heapswap [0↔2]

5,0,1

0

13,2,0

1

9,1,0

2

extract_minmin-heap

9,1,0

0

13,2,0

1

Added: [1,4]

insertmin-heapswap [0↔2]

7,0,2

0

13,2,0

1

9,1,0

2

extract_minmin-heap

9,1,0

0

13,2,0

1

Added: [1,6]

peekmin-heap

9,1,0

0

13,2,0

1

heapify_downmin-heapswap [0↔2]

7,0,2

0

13,2,0

1

9,1,0

2

heapify_downmin-heap

9,1,0

0

13,2,0

1

peekmin-heap

9,1,0

0

13,2,0

1

Added: [[1,2],[1,4],[1,6]]

Key Takeaways

✓ The min-heap efficiently tracks the next smallest pair sums without enumerating all pairs.

This insight is hard to see from code alone because the heap operations abstract away the merging process.

✓ Pairs are incrementally generated by advancing the index in nums2 for each nums1 element, ensuring no pairs are missed.

Visualizing this incremental exploration clarifies how the algorithm avoids redundant computations.

✓ Early termination occurs as soon as k pairs are collected, optimizing runtime.

Seeing the condition checked after each extraction helps understand why the algorithm stops promptly.

Practice

1. You need to generate the nth number whose prime factors come only from a given list of k primes. Which approach guarantees an optimal solution with time complexity better than brute force?

easy

A. Use a dynamic programming approach with a 2D table tracking multiples of each prime and the current ugly number index.

B. Use brute force by generating all multiples of primes and checking if they are super ugly numbers.

C. Use a greedy approach that picks the smallest prime factor at each step without tracking duplicates.

D. Use a min-heap to merge sorted sequences generated by multiplying each prime with previously found ugly numbers (k-way merge).

Solution

1. Step 1: Understand problem constraints

   The problem requires generating numbers whose prime factors are limited to a given set of primes, efficiently finding the nth such number.

2. Step 2: Identify the optimal pattern

   Using a min-heap to merge k sorted sequences (each sequence generated by multiplying a prime with previously found ugly numbers) efficiently produces the sequence in ascending order without duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges k sorted lists in O(n log k) time [OK]

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

Common Mistakes:

• Greedy approach misses duplicates and ordering
• Brute force is too slow for large n
• DP without heap is less efficient

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

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. What is the time complexity of the optimal min-heap based algorithm to find the nth super ugly number given k primes?

medium

A. O(n log k) -- because each of the n iterations involves a heap operation on size k

B. O(nk) -- because each of the n ugly numbers is generated by multiplying with k primes

C. O(n log n) -- because the heap size grows with n as new numbers are pushed

D. O(k log n) -- because k primes are processed with log n complexity each

Solution

1. Step 1: Identify heap size and operations per iteration

   The heap size is fixed at k, as each prime contributes one element at a time.

2. Step 2: Calculate total complexity

   For n ugly numbers, each iteration pops and pushes one element, each heap operation O(log k), total O(n log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size does not grow with n, so complexity depends on k, not n [OK]

Hint: Heap size fixed at k -> O(n log k) time [OK]

Common Mistakes:

• Assuming heap grows with n, leading to O(n log n)
• Confusing k and n in complexity
• Ignoring heap operation cost

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