Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Kth Smallest Number in M Sorted Lists

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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))
A

Anonymous

· 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
A

Anonymous

· 4 years ago

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

Show 1 reply
A

Anonymous

· 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