# [Amazon] Mininum Range That Includes at Least One

### Question

There are many sorted arrays. Find a minimum range, so that in each array there’s at least one integer within this range.

### Solution

Min-heap. source

There are k lists of sorted integers. Make a min heap of size k containing 1 element from each list. Keep track of min and max element and calculate the range.

In min heap, minimum element is at top. Delete the minimum element and another element instead of that from the same list to which minimum element belong. Repeat the process till any one of the k list gets empty.

### Code

``````public void printMinRange(int[][] input) {
Comparator<Pointer> compr = new HeapComparator(input);
// Note that we pass in 'input' arrays to the comparator
PriorityQueue<Pointer> heap = new PriorityQueue<Pointer>(SIZE, compr);

int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < SIZE; i++) {
// insert the head of each array into the heap
maxVal = Math.max(maxVal, input[i][0]);
// keep additional value to keep track of the max value in heap
}

int left = 0;
int right = Integer.MAX_VALUE;
while (heap.size() == SIZE) {
Pointer p = heap.remove();
// first, update the range
if (maxVal - input[p.index][p.position] < right - left) {
right = maxVal;
left = input[p.index][p.position];
}
// then, push the next element after 'p' to the heap
// meanwhile, update 'maxVal'
if (p.position + 1 < input[p.index].length) {
Pointer nextP = new Pointer(p.index, p.position + 1);
maxVal = Math.max(maxVal, input[nextP.index][nextP.position]);
}
// when 'p' is the last element in the row, terminate loop
}
System.out.println("Left boundary: " + left);
System.out.println("Right boundary: " + right);
}

class HeapComparator implements Comparator<Pointer> {

int[][] arrays = null;

public HeapComparator(int[][] input) {
arrays = input;
}

public int compare(Pointer p1, Pointer p2) {
return arrays[p1.index][p1.position]
- arrays[p2.index][p2.position];
}
}

class Pointer {
int index, position;

public Pointer(int x, int y) {
index = x;
position = y;
}
}
``````