373.Find K Pairs with Smallest Sums

Description

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/

Solution

Solution 1

Add all pairs to a minHeap, and pop k elements.

• Time complexity: O($$NLogN$$), where N is $$num1.length * num2.length$$
• Space complexity: O($$nums1.length * nums2.length$$)

Solution 2

Source Code

Maintain a minHeap of an array

Step 1. Put all pairs (nums1[i], nums2[j], j)into minHeap

Step 2. Pop the head, and add such an new array to the minheap if appliance (whenj < nums2.length - 1)

new int[] {popped[0], nums[popped[2] + 1], popped[2] + 1}

• Time complexity: O($$KLogK$$), where K is Math.min(k, nums1.length, nums2.length)

• Space complexity: O(K)