loading

Find K Pairs with Smallest Sums — Step-by-Step Visualization

mediumLeetCode #373ArrayHeap (Priority Queue)

Given two sorted arrays nums1 and nums2, return k pairs [u,v] with smallest sums.

Algorithm Pattern

Min-Heap Expansion

Key Idea

Start with (nums1[i], nums2[0]) for each i. Expand (i,j) → (i, j+1).

Step-by-Step Approach

  1. Push (nums1[i]+nums2[0], i, 0) for each i
  2. Pop min, record pair
  3. Push (nums1[i]+nums2[j+1], i, j+1) if valid
  4. Repeat k times

Related Problems

← All problems