Now that I can find the kth smallest element in a sorted n×n matrix in time O(min(n, k)), I can finally solve this problem in O(k).

**The idea:**

- If
`nums1`

or`nums2`

are larger than`k`

, shrink them to size`k`

. - Build a virtual matrix of the pair sums, i.e.,
`matrix[i][j] = nums1[i] + nums2[j]`

. Make it a square matrix by padding with "infinity" if necessary. With "virtual" I mean its entries will be computed on the fly, and only those that are needed. This is necessary to stay within O(k) time. - Find the kth smallest sum
`kthSum`

by using that other algorithm. - Use a saddleback search variation to discount the pairs with sum
**smaller**than`kthSum`

. After this,`k`

tells how many pairs we need whose sum**equals**`kthSum`

. - Collect all pairs with sum smaller than
`kthSum`

as well as`k`

pairs whose sum equals`kthSum`

.

Each of those steps only takes O(k) time.

The code (minus the code for kthSmallest, which you can copy verbatim from my solution to the other problem):

```
class Solution(object):
def kSmallestPairs(self, nums1_, nums2_, k):
# Use at most the first k of each, then get the sizes.
nums1 = nums1_[:k]
nums2 = nums2_[:k]
m, n = len(nums1), len(nums2)
# Gotta Catch 'Em All?
if k >= m * n:
return [[a, b] for a in nums1 for b in nums2]
# Build a virtual matrix.
N, inf = max(m, n), float('inf')
class Row:
def __init__(self, i):
self.i = i
def __getitem__(self, j):
return nums1[self.i] + nums2[j] if self.i < m and j < n else inf
matrix = map(Row, range(N))
# Get the k-th sum.
kthSum = self.kthSmallest(matrix, k)
# Discount the pairs with sum smaller than the k-th.
j = min(k, n)
for a in nums1:
while j and a + nums2[j-1] >= kthSum:
j -= 1
k -= j
# Collect and return the pairs.
pairs = []
for a in nums1:
for b in nums2:
if a + b >= kthSum + (k > 0):
break
pairs.append([a, b])
k -= a + b == kthSum
return pairs
def kthSmallest(self, matrix, k):
# copy & paste from https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows
```

Thanks to @zhiqing_xiao for pointing out that my previous way of capping the input lists might not be O(k). It was this:

```
def kSmallestPairs(self, nums1, nums2, k):
del nums1[k:]
del nums2[k:]
```