Find k pairs with smallest sums
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given two **sorted** integer arrays `arr1` and `arr2` (each sorted in non-decreasing order), and an integer `k`.
Consider all possible pairs formed by taking one element from `arr1` and one element from `arr2`. For indices `i` and `j`, the pair is `(arr1[i], arr2[j])` with sum `arr1[i] + arr2[j]`.
Your task is to return the **k pairs** `(arr1[i], arr2[j])` with the smallest sums. If there are fewer than `k` total possible pairs, return all possible pairs.
You may return the pairs in any order.
---
### Function Signature (one possible form)
```text
kSmallestPairs(arr1: List[int], arr2: List[int], k: int) -> List[Tuple[int, int]]
```
---
### Example
```text
arr1 = [1, 7, 11]
arr2 = [2, 4, 6]
k = 3
```
All possible pairs and their sums are:
- (1, 2) -> 3
- (1, 4) -> 5
- (1, 6) -> 7
- (7, 2) -> 9
- (7, 4) -> 11
- (7, 6) -> 13
- (11, 2) -> 13
- (11, 4) -> 15
- (11, 6) -> 17
The 3 pairs with the smallest sums are:
```text
[(1, 2), (1, 4), (1, 6)]
```
(The order among these returned pairs does not matter.)
Explain an efficient algorithm to solve this problem and analyze its time and space complexity. You may assume the arrays are large, so a solution that explicitly generates and sorts all `len(arr1) * len(arr2)` pairs is too slow.
Quick Answer: This question evaluates algorithmic problem-solving with ordered data structures, specifically understanding how to combine two sorted arrays efficiently, priority-queue or merge-based reasoning, and time/space complexity analysis in the coding and algorithms domain.
Given two sorted arrays, return up to k value pairs with the smallest sums. This console uses deterministic ordering by heap key (sum, arr1 index, arr2 index).
Constraints
- arr1 and arr2 are sorted non-decreasing
- Return all possible pairs if fewer than k exist
Examples
Input: ([1, 7, 11], [2, 4, 6], 3)
Expected Output: [[1, 2], [1, 4], [1, 6]]
Input: ([1, 1, 2], [1, 2, 3], 5)
Expected Output: [[1, 1], [1, 1], [1, 2], [1, 2], [2, 1]]
Input: ([], [1], 3)
Expected Output: []
Input: ([1], [2], 5)
Expected Output: [[1, 2]]
Hints
- Seed a min-heap with the first pair from each arr1 index.
- After popping (i,j), push (i,j+1).