Interview Bootcamp

0% completed

​

Solution: Kth Smallest Number in M Sorted Lists

Problem Statement

Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.

Example 1:

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4], K=5
Output: 4
Explanation: The 5th smallest number among all the arrays is 4, this can be verified from 
the merged list of all the arrays: [1, 2, 3, 3, 4, 6, 6, 7, 8]

Example 2:

Input: L1=[5, 8, 9], L2=[1, 7], K=3
Output: 7
Explanation: The 3rd smallest number among all the arrays is 7.

Solution

This problem follows the K-way merge pattern and we can follow a similar approach as discussed in

.....

.....

.....

Like the course? Get enrolled and start learning!
I

Ike Nwankwo

· 3 years ago

The provided python solution uses a tuple containing, the first element, index of said element, and the list itself. However python heaps will by default determine priority using the first element of the list, meaning you don't need to keep track of all of that.

Show 1 reply
M

mariana.lopez.jaimez

· 2 years ago

In the Python solution, when we push a tuple of the form (number, number_index, list), we are actually storing a reference to the list into the heap. Alternatively, we could save the index of each list. For example:

    for i, a_list in enumerate(lists):
      heappush(min_heap, (a_list[0], 0, i))

    count = 0

    while min_heap:
      number, number_idx, list_idx = heappop(min_heap)
      count += 1

      if count == k:
        return number
      
      curr_list = lists[list_idx]
      if len(curr_list) > number_idx + 1:
        heappush(min_heap, (curr_list[number_idx + 1], number_idx + 1, list_idx))
Miguel Rodriguez

Miguel Rodriguez

· 10 months ago

Better to add to a list then call heapify, cost will be O(M) for this operation vs O(M Log M) in the solution.

A

Athanasios Petsas

· 4 years ago

For the C++ solution, instead of pair of pairs we could use std::tuple to create a triplet, to make it more clear:

std::tuple triplet;

or a struct:

struct triplet { int val, array_idx, elem_idx; };

J

Jonathan

· 4 years ago

why is len(list) > i + 1, and not len(list) > i?

Show 1 reply
Joshua Ferguson

Joshua Ferguson

· a month ago

most of these solutions get a lot cleaner if you define a "popush" helper fuction:

def popush(heap, lists, idxs):
  (v, i) = heappop(heap)
  idxs[i]+=1
  if idxs[i]< len(lists[i]):
    heappush(heap,(lists[i][idxs[i]], i))
  return v

in this case the idxs is just tracking the individual