Kth Smallest Number in M Sorted Lists

Given an m number of sorted lists in ascending order and an integer, k, find the kth smallest number among all the given lists.

Kth Smallest Number in M Sorted Lists

Problem Statement

You are given m sorted lists, each arranged in ascending order, and an integer k. Your task is to find the kth smallest number across all the given lists combined.

Even if there are repeated values across the lists, each element is counted as its own unique entry. So repeated values still count separately when finding the kth smallest.

• If k is greater than the total number of elements across all lists, return the greatest element found in all the lists.
• If there are no elements at all in the input lists, return 0.

Constraints

• 1 ≤ m ≤ 300
• 0 ≤ list[i].length ≤ 300
• −10⁹ ≤ list[i][j] ≤ 10⁹
• 1 ≤ k ≤ 10⁹

Examples

Example 1

Input:

• lists = [[2, 6, 8], [3, 6, 7], [1, 3, 4]]
• k = 5

Explanation:

Combining all elements: [2, 6, 8, 3, 6, 7, 1, 3, 4].

Sorting them: [1, 2, 3, 3, 4, 6, 6, 7, 8].

The 5th smallest element is 4.

Output: 4

Example 2

Input:

• lists = [[1, 2], [3], [4, 5, 6]]
• k = 10

Explanation:

Combining all elements: [1, 2, 3, 4, 5, 6]. This has only 6 elements in total.

Since k = 10 is greater than the total number of elements, we return the greatest element, which is 6.

Output: 6

Example 3

Input:

• lists = []
• k = 3

Explanation:

There are no elements at all in the input lists, so we return 0.

Output: 0

Solution

We use a min heap to solve this efficiently.

Steps

• We push the first element of each list into the heap. Along with each value, we also store which list it came from, and its position (index) within that list.
• We then repeatedly pop the smallest value from the heap:
  • Each time we pop a value, we count it as one more number checked.
  • If this is the kth number we've checked, we return it right away — that's our answer.
  • Otherwise, we check if there's a next element in the same list this value came from. If there is, we push that next element into the heap, so it can be considered in future comparisons.
• We keep doing this until either we find the kth smallest value, or the heap runs out of elements.

Code

function findKsmallet(lists, k) {
    let heap = new MinHeap();
    let numsChecked = 0;

    for (let i = 0; i < lists.length; i++) {
        if (lists[i].length === 0) continue;

        heap.offer([lists[i][0], i, 0]);
    }

    while (heap.size() > 0) {
        const [num, listIndex, numIndex] = heap.poll();

        numsChecked++;

        if (numsChecked === k) {
            return num;
        }

        if (numIndex + 1 < lists[listIndex].length) {
            heap.offer([
                lists[listIndex][numIndex + 1],
                listIndex,
                numIndex + 1
            ]);
        }
    }

    return 0;
}