Problem
Ask
Submissions
Home
Courses
Grokking the Coding Interview Patterns

Problem: Kth Smallest Number in M Sorted Lists

Medium
30 min
Explore how to determine the kth smallest number among multiple sorted integer lists using a k-way merge approach. This lesson helps you understand handling duplicates as unique elements, managing edge cases like empty lists or large k values, and implementing efficient merging strategies. Gain practical coding skills to tackle such problems confidently in interviews.

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
Similar Problems
K-th Smallest Prime Fraction
Super Ugly Number
Merge Sorted Array
Find K Pairs with Smallest Sums
Merge K Sorted Lists
Kth Smallest Element in a Sorted Matrix
⋮
Problem
Ask
Submissions
Home
Courses
Grokking the Coding Interview Patterns

Problem: Kth Smallest Number in M Sorted Lists

Medium
30 min
Explore how to determine the kth smallest number among multiple sorted integer lists using a k-way merge approach. This lesson helps you understand handling duplicates as unique elements, managing edge cases like empty lists or large k values, and implementing efficient merging strategies. Gain practical coding skills to tackle such problems confidently in interviews.

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
Similar Problems
K-th Smallest Prime Fraction
Super Ugly Number
Merge Sorted Array
Find K Pairs with Smallest Sums
Merge K Sorted Lists
Kth Smallest Element in a Sorted Matrix