# Shortest Range in K-sorted Lists

Objective: You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.

This is very nice and tricky solution, This problem was asked in the Google interview for software engineer position.

Example:

Smallest range will be 2, [1,3], it will contain 3 from list A[], 1 from list B[] and 2 from list C[].

Approach:

• We will modify the heap implementation for this solution. This approach will be quite similar to “Merge k-sorted array” solution we had discussed.
• Create Min-Heap of type HeapNode.( HeapNode- Every Node will store the data and the list no from which it belongs).
• Now take one element from each of the K list and create HeapNode object and insert into min-Heap.
• While inserting keep track of maximum value node inserted, call it as currMax.
• Extract the minimum Node from the min-Heap call it as min, calculate the range = currMax-min.
• The extracted node will also contain the list to which it belongs, insert the next element from that list into min-Heap.
• Keep track of the minimum range after every iteration of extracting min node and inserting new node into the heap.
• If any point of time any list gets over, return the range, this will be the smallest range in K-list which contains at least one element from each list.
• See the gif below for better understanding.

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class SmallestRangeInKList { public int size; public HeapNode[] Heap; public int position; static int gMax; static int gMin; int currMax; //tracks the max entry in the heap int range = Integer.MAX_VALUE; public SmallestRangeInKList(int k) { this.size = k; Heap = new HeapNode[k + 1]; // size+1 because index 0 will be empty position = 0; Heap[0] = new HeapNode(0, –1); // put some junk values at 0th index node } public int merge(int[][] A, int k, int n) { int nk = n * k; int count = 0; int[] ptrs = new int[k]; // create index pointer for every list. for (int i = 0; i < ptrs.length; i++) { ptrs[i] = 0; } for (int i = 0; i < k; i++) { insert(A[i][ptrs[i]], i); // insert the element into heap } while (count < nk) { HeapNode h = extractMin(); // get the min node from the heap. int min = h.data; // this is min among all the values in the heap if (range > currMax – min) { // check if current difference > range gMin = min; gMax = currMax; range = gMax – gMin; } ptrs[h.listNo]++; // increase the particular list pointer if (ptrs[h.listNo] < n) { // check if list is not burns out insert(A[h.listNo][ptrs[h.listNo]], h.listNo); // insert the // next element // from the list } else { return range; // if any of this list // burns out, return range } count++; } return range; } public void insert(int data, int listNo) { // keep track of max element entered in Heap till now if (data != Integer.MAX_VALUE && currMax < data) { currMax = data; } if (position == 0) { // check if Heap is empty Heap[position + 1] = new HeapNode(data, listNo); // insert the first // element in // heap position = 2; } else { Heap[position++] = new HeapNode(data, listNo);// insert the element // to the end bubbleUp(); // call the bubble up operation } } public HeapNode extractMin() { HeapNode min = Heap[1]; // extract the root Heap[1] = Heap[position – 1]; // replace the root with the last element // in // the heap Heap[position – 1] = null; // set the last Node as NULL position—; // reduce the position pointer sinkDown(1); // sink down the root to its correct position return min; } public void sinkDown(int k) { int smallest = k; // check which is smaller child , 2k or 2k+1. if (2 * k < position && Heap[smallest].data > Heap[2 * k].data) { smallest = 2 * k; } if (2 * k + 1 < position && Heap[smallest].data > Heap[2 * k + 1].data) { smallest = 2 * k + 1; } if (smallest != k) { // if any if the child is small, swap swap(k, smallest); sinkDown(smallest); // call recursively } } public void swap(int a, int b) { // System.out.println("swappinh" + mH[a] + " and " + mH[b]); HeapNode temp = Heap[a]; Heap[a] = Heap[b]; Heap[b] = temp; } public void bubbleUp() { int pos = position – 1; // last position while (pos > 0 && Heap[pos / 2].data > Heap[pos].data) { // check if its // parent is // greater. HeapNode y = Heap[pos]; // if yes, then swap Heap[pos] = Heap[pos / 2]; Heap[pos / 2] = y; pos = pos / 2; // make pos to its parent for next iteration. } } public static void main(String[] args) { // TODO Auto-generated method stub int[][] A = new int[3][]; A[0] = new int[] { 3, 10, 15, 24 }; A[1] = new int[] { 0, 1, 2, 20 }; A[2] = new int[] { 1, 18, 21, 30 }; SmallestRangeInKList m = new SmallestRangeInKList(A.length); int rng = m.merge(A, A.length, A[0].length); System.out.println("Smallest Range is: " + rng + " from " + gMin + " To " + gMax); } } class HeapNode { int data; int listNo; public HeapNode(int data, int listNo) { this.data = data; this.listNo = listNo; } }

Output:

```Smallest Range is: 2 from 1 To 3
```

### 1 thought on “Shortest Range in K-sorted Lists”

This site uses Akismet to reduce spam. Learn how your comment data is processed.