Kth Smallest Number in M Sorted Lists

Try to solve the Kth Smallest Number in M Sorted Lists problem.

We'll cover the following

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

Examples#

Created with Fabric.js 3.6.6

1 of 3

Created with Fabric.js 3.6.6

2 of 3

Created with Fabric.js 3.6.6

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

KthK^{th} Smallest Number in MM Sorted Lists

1

What is the output if the following lists and the value of k are given as input?

1st1^{st} list = [1, 4, 5]
2nd2^{nd} list = [4, 7, 8]
3rd3^{rd} list = [2, 6, 9]
k = 5

A)

7

B)

5

C)

6

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Push the first element of each list in the min-heap.

Remove the top (root) of the min-heap.

If the popped element has the next element in its list, push the next element in the min-heap.

If kk elements have been removed from the heap, return the last popped element.

Try it yourself#

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Kth Smallest Number in M Sorted Lists

Solution: Merge Sorted Array

Solution: Kth Smallest Number in M Sorted Lists