Ebay OA Interview Problem: Find the Kth Element Across Multiple Sorted Arrays

65 Views
No Comments

Given n sorted arrays, find the kth element among all elements in these arrays.

The key idea is to treat all sorted arrays as one merged sorted sequence and extract the kth element without fully merging everything. A min-heap is the standard approach: push the first element of each array, repeatedly pop the smallest element, and push the next element from the same array until the kth pop. This keeps the solution efficient, typically O(k log n) time where n is the number of arrays, and avoids storing all elements in one combined array.

END
 0