How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Find k Smallest Pair Sums | Apple Coding Question

Find k Smallest Pair Sums

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order, and an integer `k`, return the `k` pairs with the smallest sums, where each pair contains one element from `nums1` and one element from `nums2`. If there are fewer than `k` possible pairs, return all of them. The output should be ordered by increasing pair sum; if multiple pairs have the same sum, any order among those ties is acceptable. You should implement a solution more efficient than generating every possible pair. In the interview, you are also expected to write a few tests and run the code. Example: - `nums1 = [1, 7, 11]` - `nums2 = [2, 4, 6]` - `k = 3` - Output: `[[1, 2], [1, 4], [1, 6]]`

Quick Answer: This question evaluates skills in algorithm design, working with sorted arrays, pairing and ordering elements, and analyzing time and space complexity within the Coding & Algorithms domain.

Given two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order, and an integer `k`, return the `k` pairs `[u, v]` (with `u` from `nums1` and `v` from `nums2`) that have the smallest sums. If there are fewer than `k` possible pairs, return all of them. The output must be ordered by increasing pair sum; if multiple pairs have the same sum, any order among those ties is acceptable. Your solution should be more efficient than generating every possible pair (which is O(m·n)). A min-heap approach achieves O(k·log k). Example: - `nums1 = [1, 7, 11]`, `nums2 = [2, 4, 6]`, `k = 3` - Output: `[[1, 2], [1, 4], [1, 6]]` (sums 3, 5, 7)

Constraints

1 <= nums1.length, nums2.length <= 10^5 (either may be empty in edge handling)
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1 and nums2 are sorted in non-decreasing order
1 <= k <= 10^4 (return fewer if fewer pairs exist)

Examples

Input: ([1, 7, 11], [2, 4, 6], 3)

Expected Output: [[1, 2], [1, 4], [1, 6]]

Explanation: Sums are 3, 5, 7 — the three smallest all pair 1 from nums1 with each of nums2.

Input: ([1, 1, 2], [1, 2, 3], 2)

Expected Output: [[1, 1], [1, 1]]

Explanation: The two smallest sums both equal 2, formed by either 1 in nums1 with the 1 in nums2.

Input: ([1, 2], [3], 3)

Expected Output: [[1, 3], [2, 3]]

Explanation: Only 2 pairs exist, fewer than k=3, so return both ordered by sum (4, 5).

Input: ([], [1, 2], 5)

Expected Output: []

Explanation: Empty input array means no pairs can be formed.

Input: ([2], [3], 0)

Expected Output: []

Explanation: k=0 requests no pairs.

Input: ([-5, -2, 0], [-3, 1, 4], 3)

Expected Output: [[-5, -3], [-2, -3], [-5, 1]]

Explanation: Sums -8, -5, -4 are the three smallest; negatives are handled correctly.

Hints

Brute force generates all m·n pairs and sorts them — too slow. Exploit the sortedness.
Use a min-heap keyed on pair sum. Initialize it with pairs (nums1[i], nums2[0]) for the first k rows.
When you pop (i, j), the next candidate from the same row is (i, j+1). Push it so the heap always contains the frontier of unexplored pairs.

Quick Overview

This question evaluates skills in algorithm design, working with sorted arrays, pairing and ordering elements, and analyzing time and space complexity within the Coding & Algorithms domain.