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.

Base Case

Merge K sorted List

1. Put first elements of each list to min heap.
2. While queue is not empty take element add it to result or assign pointers and put next element back.

public ListNode<Integer> mergeKLists(ListNode<Integer>[] lists) {
    PriorityQueue<ListNode<Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(l -> l.value));
    Collections.addAll(queue, lists);
    var dummyNode = new ListNode<>(0);
    var curr = dummyNode;
    while (!queue.isEmpty()) {
        var node = queue.poll();
        curr.next = node;
        queue.add(node.next);
        curr = curr.next;
    }
    return dummyNode.next;
}

Kth Smallest Number In N Sorted Lists

The same as above but we can create Node class to track arrayIndex and element Index.

While adding check elementIndex < array.length.

public static int findKthSmallest(List<Integer[]> lists, int k) {
    PriorityQueue<Node> minHeap = new PriorityQueue<Node>(
        (n1, n2) -> lists.get(n1.arrayIndex)[n1.elementIndex] - lists.get(n2.arrayIndex)[n2.elementIndex]);

    // put the 1st element of each array in the min heap
    for (int i = 0; i < lists.size(); i++)
      if (lists.get(i) != null)
        minHeap.add(new Node(0, i));

    // take the smallest (top) element form the min heap, if the running count is equal to k return the number
    // if the array of the top element has more elements, add the next element to the heap
    int numberCount = 0, result = 0;
    while (!minHeap.isEmpty()) {
      Node node = minHeap.poll();
      result = lists.get(node.arrayIndex)[node.elementIndex];
      if (++numberCount == k)
        break;
      node.elementIndex++;
      if (lists.get(node.arrayIndex).length > node.elementIndex)
        minHeap.add(node);
    }
    return result;
  }

class Node {
  int elementIndex;
  int arrayIndex;

  Node(int elementIndex, int arrayIndex) {
    this.elementIndex = elementIndex;
    this.arrayIndex = arrayIndex;
  }
}

K Pairs with Smallest/Largest Sum

In this case we need to put all possible pairs from two arrays and fetch it back in order.

1. So, we add nums1[0] + nums2[j] in first iteration.
2. And while iterating again we take pair from queue, adding it to result and putting back

nums1[t.x + 1] + nums2[t.y].

public List<int[]> kSmallestPairsDiscuss(int[] nums1, int[] nums2, int k) {
    PriorityQueue<Tuple> pq = new PriorityQueue<>();
    int m = nums1.length, n = nums2.length;
    List<int[]> res = new ArrayList<>();
    if (nums1.length == 0 || nums2.length == 0 || k <= 0) return res;

    for (int j = 0; j <= n - 1; j++) {
        pq.offer(new Tuple(0, j, nums1[0] + nums2[j]));
    }

    for (int i = 0; i < Math.min(k, m * n); i++) {
        Tuple t = pq.poll();
        res.add(new int[]{nums1[t.x], nums2[t.y]});
        if (t.x == m - 1) continue;
        pq.offer(new Tuple(t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y]));
    }
    return res;
}
static class Tuple implements Comparable<Tuple> {
    int x, y, val;

    public Tuple(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }

    @Override
    public int compareTo(Tuple that) {
        return this.val - that.val;
    }
}

Smallest Number Range

In this case we add nodes to min heap and tracking distance between first value from heap and maxNumber.

1. Spread first nums to queue.