LeetCode #632: Minimum Range

$\mathtt{Solution REFERENCE}$ @ LeetCode #632

Smallest Range : Problem Definition

This is a LeetCode Problem. You can find it HERE

Given $k$ lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each the lists.

The range $[a,b]$ is smaller than the range $[c,d]$ if $b-a < d -c$ OR $a < c\ if\ b-a == d-c$

Solution

Brute Force Solution

The straight forward solution would be to consider every possible set that includes at least one element from each of the list and find the minimum range out of those all sets.

The problem is, there are exponential number of possible sets to be considered. If we consider sets with one element from each list, then we already have $k^n$ sets. So this is not practical.

Efficient Solution

If we have a list, then to minimize the range, we either need to increase the minimum value or decrease the maxmimum value in the set.

We start by considering a set of $k$ elements which will have one item from each of the given list. At each step we keep track of $MAX$ and $Min-Range$ and it can be done in constant time $O(1)$. Now at each step, we remove the minimum element from set. To maintain constraint of having at least one element from each list, to compensate the removal of minimum element, we insert the next element from the list to which the minimum element we just removed belongs.

After each step we update $MAX$ and $Min-Range$ if necessary.

Once one of the list exhausts, we can safely return the $Min-Range$ as our result because we cannot have other lists which includes at least one element from each list.

Time and Space Complexity

Talking about Time Complexity, at the worst we will need to go through all the elements in all the $k$ lists which is O(nk) assuming each list has $n$ elements. Remember that we are removing the minimum element from the set and then push new element to it. So we must be able to identify the minimum element each time. If we iterate through all elements in the set to find the minimum, it will take $O(k)$ time. Therefore the overall time complexity will be $O(nk^2)$.

We can make this better by using $Min-Heap$. Instead of using set to store $k$ elements, we use $min-heap$ where we can find minimum element in $O(1)$ time, remove and add element in $O(logk)$ time. So the overall time complexity will be $O(nklogk)$.

The Space complexity will be $O(k)$ to store $k$ elements at each step.

Min Heap

It is not enough to store only the elements from the input lists.

When we remove an element from the heap, we should be able to identify to which list this element belongs to and at which index because after its removal we need to add next item from the same list. For this reason, items pushed into the heap should have information:

1. actual element from lists
2. list to which the element belongs (index)
3. index where this element lies in the list (index)

This implies we could use array of 3 elements as an item of the heap: $[<item>, <index\ of\ list>, <index\ within\ the\ list>]$

Implementation

	/**
	* @author Sabbir Manandhar
	* ManandharSabbir@gmail.com
	*/
	class MinimumRange {
	public int[] smallestRange(List<List<Integer>> nums) {
	// Min heap to store intermediate k elements
	PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
	public int compare(int[] a, int[] b) {
	return a[0] - b[0];
	}
	});
	// keep track of max in the heap to compute range
	int maxSoFar = Integer.MIN_VALUE;
	// start with minimum elements from the lists into our heap
	for(int i = 0; i < nums.size(); i++) {
	int num = nums.get(i).get(0);
	heap.offer(new int[]{num, i, 0});
	maxSoFar = Math.max(maxSoFar, num);
	}
	// keep track of minimum range
	int rangeS = heap.peek()[0];
	int rangeE = maxSoFar;
	while(true) {
	// remove minimum element from the heap
	int[] min = heap.poll();
	int nextIdx = min[2] + 1;
	// once one of the list exhausts return
	if(nextIdx == nums.get(min[1]).size()) {
	break;
	}
	// insert next element fromt the list
	int nextNum = nums.get(min[1]).get(nextIdx);
	heap.offer(new int[]{nextNum, min[1], nextIdx});
	// update max so far and minimum range
	maxSoFar = Math.max(maxSoFar, nextNum);
	int newRangeS = heap.peek()[0];
	int newRangeE = maxSoFar;
	if (newRangeE - newRangeS < rangeE - rangeS) {
	rangeS = newRangeS;
	rangeE = newRangeE;
	}
	}
	return new int[]{rangeS, rangeE};
	}
	}

view raw MinimumRange.java hosted with ❤ by GitHub

---

---

---