Find kth smallest pair sum with heaps

Q: Find kth smallest pair sum with heaps

This is a Coding & Algorithms interview question from Meta for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given two nondecreasing arrays A (length n) and B (length m) of non-negative integers and an integer k (1 <= k <= nm). Return the k-th smallest value among all pair sums A[i] + B[j]. Avoid generating all pairs. Target complexity: O(k log min(n, m)) time and O(min(n, m)) space using a heap-based approach. Discuss handling duplicate sums, boundary cases (k=1, k=nm), and prove correctness.

Find kth smallest pair sum with heaps

Comments (0)