This pattern helps us solve problems that involve a list of sorted arrays.

Whenever we are given ‘K’ sorted arrays, we can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays. We can push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum. While inserting elements to the Min Heap we keep track of which array the element came from. We can, then, remove the top element from the heap to get the smallest element and push the next element from the same array, to which this smallest element belonged, to the heap. We can repeat this process to make a sorted traversal of all elements.

Merge K Sorted Lists

from __future__ import print_function
from heapq import *


class ListNode:
  def __init__(self, value):
    self.value = value
    self.next = None

  def __lt__(self, other):
    return self.value < other.value


def merge_lists(lists):
  minHeap = []
  resultHead, resultTail = None, None
 
  # Put Head of each list into minHeap
  for root in lists:
    if root is not None:
      heappush(minHeap, root)

  # While minHeap contains nodes, pop root
  while minHeap:
    node = heappop(minHeap)

    # If resultHead is None, set resultHead
    # Else, update resultTail.next and set resultTail to current Node
    if resultHead is None:
      resultHead = node
      resultTail = node
    else:
      resultTail.next = node
      resultTail = node

    # If the corresponding list has a next, add to minHeap
    if node.next is not None:
      heappush(minHeap, node.next)
  
  return resultHead


def main():
  l1 = ListNode(2)
  l1.next = ListNode(6)
  l1.next.next = ListNode(8)

  l2 = ListNode(3)
  l2.next = ListNode(6)
  l2.next.next = ListNode(7)

  l3 = ListNode(1)
  l3.next = ListNode(3)
  l3.next.next = ListNode(4)

  result = merge_lists([l1, l2, l3])
  print("Here are the elements form the merged list: ", end='')
  while result != None:
    print(str(result.value) + " ", end='')
    result = result.next


main()

Kth Smallest Number in M Sorted Lists

from heapq import *

def find_Kth_smallest(lists, k):
  minHeap = []
  count = 1
  returnVal = -1

  # minHeap will contain tuple: (value, index into list, list)

  for i in range(len(lists)):
    if lists[i] is not None:
      heappush(minHeap, (lists[i][0], 0, lists[i]))

  while minHeap:
    val, index, list = heappop(minHeap)
    if count == k:
      returnVal = val
      break

    count += 1

    if index + 1 < len(list):
      heappush(minHeap, (list[index+1], index+1, list))

  return returnVal

  return number


def main():
  print("Kth smallest number is: " +
        str(find_Kth_smallest([2, 6, 8], [3, 6, 7], [1, 3, 4](/kjingers/Grokking-Notes/wiki/2,-6,-8],-[3,-6,-7],-[1,-3,-4), 5)))


main()

Kth Smallest Element in a Sorted Matrix

from heapq import *

def find_Kth_smallest(matrix, k):
  minHeap = []
  count = 1

  # minHeap will contain tuple with:
  # (value, index, row)

  # Push the first element of each row into minHeap
  for row in matrix:
    if row is not None:
      heappush(minHeap, (row[0], 0, row))

  number = -1
  while minHeap:

    number, index, row = heappop(minHeap)

    if count == k:
      break
    
    count += 1

    if index + 1 < len(row):
      heappush(minHeap, (row[index + 1], index + 1, row))
  
  return number


def main():
  print("Kth smallest number is: " +
        str(find_Kth_smallest([2, 6, 8], [3, 7, 10], [5, 8, 11](/kjingers/Grokking-Notes/wiki/2,-6,-8],-[3,-7,-10],-[5,-8,-11), 5)))


main()

Smallest Range Covering Elements from K Lists

'''
Smallest range: smallest difference between largest and smallest
element that contains a number from all lists.

- Can use K Way Merge to store one element from each array into Min Heap
- Can keep track of the largest value inserted into array
- Each loop, calculate max - min. Update global min if needed.

- If ranges are the same, the one with the smallest element is smaller
'''

from heapq import *
import math

def find_smallest_range(lists):
  minHeap = []
  resultMin = 0
  resultMax = math.inf
  currMax = -math.inf

  # If any list is empty, then no valid answer
  if any(list is False for list in lists):
    return [-1, -1]

  # minHeap contains (value, index, list)
  # Push the first element from each list onto minHeap
  for list in lists:
    if list is not None:
      heappush(minHeap, (list[0], 0, list))
      currMax = max(currMax, list[0])

  while len(minHeap) == len(lists):
    val, index, list = heappop(minHeap)
    
    # If current Max and Min is smaller than previous, then update
    if (currMax - val) < (resultMax - resultMin):
      resultMax = currMax
      resultMin = val

    # Push next element of list into minHeap
    # Update current Max value in heap
    if index + 1 < len(list):
      heappush(minHeap, (list[index + 1], index + 1, list))
      currMax = max(currMax, list[index + 1])

  return [resultMin, resultMax]



def main():
  print("Smallest range is: " +
        str(find_smallest_range([1, 5, 8], [4, 12], [7, 8, 10](/kjingers/Grokking-Notes/wiki/1,-5,-8],-[4,-12],-[7,-8,-10))))
  print("Smallest range is: " +
        str(find_smallest_range([1, 9], [4, 12], [7, 10, 16](/kjingers/Grokking-Notes/wiki/1,-9],-[4,-12],-[7,-10,-16))))


main()