Solution: Kth Smallest Number in M Sorted Lists

Let's solve the Kth Smallest Number in M Sorted Lists problem using the K-Way Merge pattern.

Statement

Given an mm number of sorted lists in ascending order and an integer, k, find the kthk^{th} smallest number among all the given lists.

Although there can be repeating values in the lists, each element is considered unique and, therefore, contributes to calculating the kthk^{th} smallest element.

If k is greater than the total number of elements in the input lists, return the greatest element from all the lists and if there are no elements in the input lists, return 0.

Constraints:

  • 1≤1\leq m ≤300\leq300
  • 0≤0\leq list[i].length ≤300\leq 300
  • −109≤-10^9\leq list[i][j] ≤109\leq 10^9
  • 1≤1\leq k ≤109\leq 10^9

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.