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:

Shortest Range in K-sorted Lists - Example
Shortest Range in K-sorted Lists – 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.
Shortest Range in K-sorted Lists
Shortest Range in K-sorted Lists

Complete Code:

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