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

Kth Smallest Number in M Sorted Lists

Understand how to determine the kth smallest element among multiple sorted lists by applying key merging techniques. This lesson guides you through handling duplicates, edge cases, and constraints while implementing an efficient solution.

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;
    }
}