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

Kth Smallest Number in M Sorted Lists

Explore how to find the kth smallest number across multiple sorted lists using the k-way merge approach. Understand how to handle duplicate elements and edge cases, and implement an efficient solution to retrieve the desired element or the largest value when k exceeds the total elements.

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 the following coding playground.

JavaScript
usercode > Solution.js
import { MinHeap, MaxHeap } from "./Heap.js";



/* The following definition is for MinHeap.



  You can use the same methods for MaxHeap.

  class MinHeap {



    size();          // return number of elements

    peek();          // return top element without removing

    push(val);       // insert element

    pop();           // remove and return top element

  }

*/



function kSmallestNumber(lists, k){



    // Replace this placeholder return statement with your code

    return -1

}



export {

    kSmallestNumber

}
Kth Smallest Number in M Sorted Lists