Find the K Closest Pairs in a Sorted Array

Problem Statement

Given a strictly increasing sorted array of integers nums and an integer k, return the k pairs of elements (nums[i], nums[j]) with i < j that have the smallest absolute differences nums[j] - nums[i].

The returned list should be ordered from smallest difference to largest difference. If two pairs have identical differences, break ties by ordering them by the first element nums[i] in ascending order, and then by the second element nums[j] in ascending order.

Function Signature

def k_closest_pairs(nums: list[int], k: int) -> list[tuple[int, int]]:
    pass

Constraints

• 2 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is strictly increasing (nums[i] < nums[i + 1] for all 0 <= i < len(nums) - 1)
• 1 <= k <= min(10^5, len(nums) * (len(nums) - 1) // 2)

Examples

Example 1:

Input: nums = [1, 2, 5, 8], k = 3
Output: [(1, 2), (2, 5), (5, 8)]
Explanation:
All possible pairs and their differences:
- (1, 2) -> diff 1
- (2, 5) -> diff 3
- (5, 8) -> diff 3
- (1, 5) -> diff 4
- (2, 8) -> diff 6
- (1, 8) -> diff 7
The 3 pairs with the smallest differences are (1, 2), (2, 5), and (5, 8).

Example 2:

Input: nums = [1, 3, 4, 7, 10], k = 2
Output: [(3, 4), (1, 3)]
Explanation:
The smallest difference is between 3 and 4 (diff = 1).
The second smallest difference is between 1 and 3 (diff = 2).

Edge Cases to Consider

• k equals n * (n - 1) // 2: All pairs must be returned.
• Minimum array size len(nums) == 2: Exactly one pair exists.
• Arrays with negative numbers or large values where differences could approach 2 * 10^9.