Find k pairs with smallest sums

Array Heap (Priority Queue)

41.6% acceptance

Jan 12, 2026

6910

495

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k. Define a pair (u, v) which consists of one element from the first array and one element from the second array. Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::cmp::Reverse;

impl Solution {
  pub fn k_smallest_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    if nums1.is_empty() || nums2.is_empty() {
      return result;
    }
    
    let mut heap = std::collections::BinaryHeap::new();
    for i in 0..nums1.len().min(k as usize) {
      heap.push(Reverse((nums1[i] + nums2[0], i, 0)));
    }
    
    while result.len() < k as usize && !heap.is_empty() {
      let Reverse((_, i, j)) = heap.pop().unwrap();
      result.push(vec![nums1[i], nums2[j]]);
      
      if j + 1 < nums2.len() {
        heap.push(Reverse((nums1[i] + nums2[j + 1], i, j + 1)));
      }
    }
    
    result
  }
}