Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Kth Smallest Number in M Sorted Lists

Explore how to find the kth smallest number from multiple sorted lists using efficient merging algorithms. This lesson helps you understand treating duplicates as unique and managing edge cases like empty lists or out-of-range k values. You will practice implementing these concepts to prepare for interview challenges involving merged sorted data.

We'll cover the following...

Statement

Given a list, lists, containing mm sorted lists of integers in ascending order, and an integer k, find the kthk^{th} smallest element among all the lists.

Even if some values appear multiple times across the lists, each occurrence is treated as a unique element when determining the kthk^{th} smallest number.

If k exceeds the total number of elements across all lists, return the largest element among them. If the lists are empty, return 0.

Constraints:

  • 1≤m≤501\leq m \leq50
  • 0≤0\leq lists[i].length ≤50\leq 50
  • −109≤-10^9\leq lists[i][j] ≤109\leq 10^9
  • 1≤1\leq k ≤109\leq 10^9

Examples

canvasAnimation-image
1 / 5

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?

list1 = [1, 4, 5]

list2 = [4, 7, 8]

list3 = [2, 6, 9]

k = 5

A.

7

B.

5

C.

6

1 / 3

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in FindSmallestNumber.java in the following coding playground.

Java
usercode > FindSmallestNumber.java
import java.util.*;
class FindSmallestNumber {
    public static int kSmallestNumber(List<List<Integer>> lists, int k) {
        // Replace this placeholder return statement with your code
        return -1;
    }
}