Practice/Meta/Given M Sorted Lists, Print the Kth Smallest/Largest Value

Given M Sorted Lists, Print the Kth Smallest/Largest Value

CodingMust

Problem

You are given m sorted arrays (each sorted in ascending order) and an integer k. Your task is to find the kth smallest element across all the arrays combined.

Each array may have a different length, and k is guaranteed to be valid (1 ≤ k ≤ total number of elements across all arrays).

Requirements

1. Each input array is already sorted in ascending order
2. Return the kth smallest element where k is 1-indexed (k=1 returns the smallest element)
3. You must handle arrays of varying lengths
4. The solution should be more efficient than merging all arrays and sorting

Constraints

• 1 ≤ m ≤ 500 (number of arrays)
• 0 ≤ length of each array ≤ 500
• 1 ≤ k ≤ total number of elements
• All elements are integers
• Target time complexity: O(k log m) or better
• Target space complexity: O(m)

Examples

Example 1:

Input: arrays = [[1, 5, 9], [2, 6, 10], [3, 7, 11]], k = 5 Output: 6 Explanation: If we merge all arrays in sorted order, we get [1, 2, 3, 5, 6, 7, 9, 10, 11]. The 5th smallest element is 6.

Example 2:

Input: arrays = [[1, 4, 7], [2, 5, 8], [3, 6, 9]], k = 1 Output: 1 Explanation: The smallest element across all arrays is 1.

Example 3:

Input: arrays = [[10, 20, 30]], k = 2 Output: 20 Explanation: With a single array, the 2nd smallest element is 20.

Example 4:

Input: arrays = [[1], [2], [3], [4], [5]], k = 3 Output: 3 Explanation: Each array contains one element. The 3rd smallest is 3.