What is the pattern for solving Find K Pairs with Smallest Sums?

The primary pattern involves using arrays in conjunction with a heap (priority queue) to efficiently select the k smallest sum pairs from the two sorted arrays.

How does the sorted order of nums1 and nums2 affect the solution?

The sorted order allows for efficient pair generation and prioritization of smaller sums in the heap, making the solution optimal in both time and space.

What is the time complexity of this solution?

The time complexity is O(min(k * log k, m * n * log (m * n))), where k is the number of pairs to find, and m and n are the lengths of the arrays.

How does the heap (priority queue) work in this problem?

The heap is used to efficiently manage the smallest sum pairs by always extracting the smallest pair and pushing the next viable pair into the heap.

What are the common mistakes when solving this problem?

Common mistakes include overpopulating the heap with all pairs, mismanaging heap transitions, or ignoring the sorted order of arrays for optimization.

#373

Medium

auto_awesome堆

LeetCode 题解工作台

查找和最小的 K 对数字

给定两个以非递减顺序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v) ，其中第一个元素来自 nums1 ，第二个元素来自 nums2 。请找到和最小的 k 个数对 (u 1 ,v 1 ) , (u 2 ,v 2 ) ... (u k ,v k ) 。…

数组堆（优先队列）

题目描述

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u₁,v₁), (u₂,v₂) ... (u_k,v_k) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [[1,2],[1,4],[1,6]]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [[1,1],[1,1]]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

提示:

1 <= nums1.length, nums2.length <= 10⁵
-10⁹ <= nums1[i], nums2[i] <= 10⁹
nums1 和 nums2 均为 升序排列
1 <= k <= 10⁴
k <= nums1.length * nums2.length

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def kSmallestPairs(
        self, nums1: List[int], nums2: List[int], k: int
    ) -> List[List[int]]:
        q = [[u + nums2[0], i, 0] for i, u in enumerate(nums1[:k])]
        heapify(q)
        ans = []
        while q and k > 0:
            _, i, j = heappop(q)
            ans.append([nums1[i], nums2[j]])
            k -= 1
            if j + 1 < len(nums2):
                heappush(q, [nums1[i] + nums2[j + 1], i, j + 1])
        return ans

speed

复杂度分析

指标	值
时间	O(\min(k \cdot \log k, m \cdot n \cdot \log (m \cdot n)))
空间	O(\min(k, m \cdot n))

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently combine array traversal with heap operations?
question_mark
How well does the candidate manage the heap size and limit unnecessary operations?
question_mark
Does the candidate understand the trade-off between time and space complexity in heap-based solutions?

warning

常见陷阱

外企场景

error
Overpopulating the heap with all possible pairs instead of strategically pushing only potential candidates.
error
Incorrectly handling the heap extraction order or failing to manage heap transitions between pairs.
error
Failing to account for the sorted nature of the arrays, which can optimize the pairing strategy.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the arrays are unsorted? This would require sorting the arrays first before applying the heap method.
arrow_right_alt
What if k exceeds the possible pairs from the arrays? In such cases, ensure the solution handles this scenario gracefully by limiting the output to the available pairs.
arrow_right_alt
Handling arrays with duplicate elements. The solution should still work and return the correct k smallest sums, regardless of duplicates.

help

常见问题

外企场景

继续练习

#378 有序矩阵中第 K 小的元素 #347 前 K 个高频元素 #407 接雨水 II