Grokking the Coding Interview: Patterns for Coding Questions
Vote

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.

Why this is a K-way Merge problem

What the question saysThe signal it matches

.....

.....

.....

Like the course? Get enrolled and start learning!
Joshua Ferguson

Joshua Ferguson

· 3 months 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

Show 1 reply
Miguel Rodriguez

Miguel Rodriguez

· a year 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.

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))
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
J

Jonathan

· 4 years ago

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

Show 1 reply
A

Athanasios Petsas

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

Reading Progress

0%

Vote for new content