Home/

...

/

Smallest Number Range (Hard)

Smallest Number Range (Hard)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Smallest Number Range (Hard) lesson:

Press + to interact
Python 3.5
from heapq import *
import math
def find_smallest_range(lists):
  minHeap = []
  rangeStart, rangeEnd = 0, math.inf
  currentMaxNumber = -math.inf
  # put the 1st element of each array in the min heap
  for arr in lists:
    heappush(minHeap, (arr[0], 0, arr))
    currentMaxNumber = max(currentMaxNumber, arr[0])
  # take the smallest(top) element form the min heap, if it gives us smaller range, update the ranges
  # if the array of the top element has more elements, insert the next element in the heap
  while len(minHeap) == len(lists):
    num, i, arr = heappop(minHeap)
    if rangeEnd - rangeStart > currentMaxNumber - num:
      rangeStart = num
      rangeEnd = currentMaxNumber
    if len(arr) > i+1:
      # insert the next element in the heap
      heappush(minHeap, (arr[i+1], i+1, arr))
      currentMaxNumber = max(currentMaxNumber, arr[i+1])
  return [rangeStart, rangeEnd]
def main():
  print("Smallest range is: " +
        str(find_smallest_range([[1, 5, 8], [4, 12], [7, 8, 10]])))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

lists: [[1, 2], [3,4], [5,6]]

Iteration No.

Line No.

minHeap

currentMaxNumber

num,

i,

arr

rangeStart -- rangeEnd

-

6-8

[]

-infinity

-

0 - infinity

1

11-13

[(1, 0, [1, 2])]

1

-

0 - infinity

2

11-13

[(1, 0, [1, 2]), (3, 0, [3, 4])]

3

-

0 - infinity

3

11-13

[(1, 0, [1, 2]), (3, 0, [3, 4]), (5, 0, [5, 6])]

5

-

0 - infinity

1

18

[(3, 0, [3, 4]), (5, 0, [5, 6])]

5

1,0,[1, 2]

0 - infinity

1

19-21

[(3, 0, [3, 4]), (5, 0, [5, 6])]

5

1,0,[1, 2]

1- 5

1

23-26

[(2, 1, [1, 2]), (5, 0, [5, 6]), (3, 0, [3, 4])]

5

1,0,[1, 2]

1- 5

2

18

[(5, 0, [5, 6]), (3, 0, [3, 4])]

5

2,1,[1, 2]

1 - 5

2

19-21

[(5, 0, [5, 6]), (3, 0, [3, 4])]

5

2,1,[1, 2]

2 - 5

Sample Input #2

lists: [[10, 20, 30], [1, 2, 3], [7, 8, 19]]

Iteration No.

Line No.

minHeap

currentMaxNumber

num,

i,

arr

rangeStart -- rangeEnd

-

6-8

[]

-infinity

-

0 - infinity

1

11-13

[(10, 0, [10, 20, 30])]

10

-

0 - infinity

2

11-13

[(1, 0, [1, 2, 3]), (10, 0, [10, 20, 30])]

10

-

0 - infinity

3

11-13

[(1, 0, [1, 2, 3]), (10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

-

0 - infinity

1

18

[(10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

1,0,[1, 2, 3]

0 - infinity

1

19-21

[(10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

1,0,[1, 2, 3]

1- 10

1

23-26

[(2, 1, [1, 2, 3]), (10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

1,0,[1, 2, 3]

1- 10

2

18

[(10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

2,1,[1, 2, 3]

1 - 10

2

19-21

[(10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

2,1,[1, 2, 3]

2 - 10

2

23-26

[(3, 2, [1, 2, 3]), (10, 0, [10, 20, 30]), (7, 0, [7, 8, 19])]

10

2,1,[1, 2, 3]

2 - 10

3

18

[(7, 0, [7, 8, 19]), (10, 0, [10, 20, 30])]

10

3,2,[1, 2, 3]

2-10

3

19-21

[(7, 0, [7, 8, 19]), (10, 0, [10, 20, 30])]

10

3,2,[1, 2, 3]

3-10

Step-by-step solution construction

Initially, we need to add the first element of each list to the minHeap. At the same time, we update currentMaxNumber with every insertion, to keep track of the largest number encountered so far.

In the following code, on line 14, we take the first element of the current list arr and insert it into minHeap along with its index, 0, in arr, and the current list arr itself.

On line 16, we update currentMaxNumber if the newly inserted number is greater than the currentMaxNumber.

Press + to interact
Python 3.5
from heapq import *
import math
def find_smallest_range(lists):
  print("Input lists:", lists)
  minHeap = []
  rangeStart, rangeEnd = 0, math.inf
  currentMaxNumber = -math.inf
  print("Inserting 1st element of each array in the minHeap")
  # put the 1st element of each array in the min heap
  for arr in lists:
    heappush(minHeap, (arr[0], 0, arr))
    print("minHeap: " + str(minHeap))
    currentMaxNumber = max(currentMaxNumber, arr[0])
    print("currentMaxNumber: " + str(currentMaxNumber))
  return [rangeStart, rangeEnd]
def main():
  lists = [[[2, 3], [4,5], [6,7]],[[1, 2, 30], [9, 10,15], [7, 8, 10]]]
  for i in range(len(lists)):
    [rangeStart,rangeEnd] = find_smallest_range(lists[i])
    print("Smallest range in " + str(lists[i]) + " is: " + str(rangeStart) + "-" + str(rangeEnd))
    print("-"*100)
main()

Let’s add a loop that will continue to iterate as long as there are as many elements in the heap as there are input lists.

Each iteration of the loop will pop the minimum element from the minHeap (line 28) and push the next element from the list that contains the element just popped (line 35).

For example, if the second element belonging to the third list was just popped, then if the third list has a third element, that element is pushed on to the heap.

This pairing of pop and push ensures that the heap always contains one element each from each of the k input lists.

We also update currentMaxNumber if the newly inserted element is greater than the current value of currentMaxNumber (line 36).

We are not yet updating rangeStart and rangeEnd.

Press + to interact
Python 3.5
from heapq import *
import math
def find_smallest_range(lists):
  print("Input lists:", lists)
  minHeap = []
  rangeStart, rangeEnd = 0, math.inf
  currentMaxNumber = -math.inf
  print("Inserting 1st element of each array in the minHeap")
  # put the 1st element of each array in the min heap
  for arr in lists:
    heappush(minHeap, (arr[0], 0, arr))
    print("minHeap: " + str(minHeap))
    currentMaxNumber = max(currentMaxNumber, arr[0])
    print("currentMaxNumber: " + str(currentMaxNumber))
  print("Set-up complete. About to start pop-and-push cycle:\n")
  iteration = 0;
  # pop the smallest(top) element from the min heap
  # if there are elements left in the array to which the top element belongs, 
  # push the next element from that array on to the heap
  while len(minHeap) == len(lists):
    print("\nIteration: "+str(iteration+1))
    iteration +=1
    print("\tminHeap: " + str(minHeap))
    num, i, arr = heappop(minHeap)
    print("\tnum, i, arr: "+str(num)+", "+str(i)+", "+str(arr))
    print("\tCurrent Range: " + str(rangeStart) + "-" + str(rangeEnd))
    print("\tcurrentMaxNumber: "+str(currentMaxNumber))
    
    if len(arr) > i+1:
      # insert the next element in the heap
      heappush(minHeap, (arr[i+1], i+1, arr))
      currentMaxNumber = max(currentMaxNumber, arr[i+1])
  return [rangeStart, rangeEnd]
def main():
  lists = [[[2, 3], [4,5], [6,7]],[[1, 2, 30], [9, 10,15], [7, 8, 10]]]
  for i in range(len(lists)):
    [rangeStart,rangeEnd] = find_smallest_range(lists[i])
    print("Smallest range in " + str(lists[i]) + " is: " + str(rangeStart) + "-" + str(rangeEnd))
    print("-"*100)
main()

As a final step, we need to add conditions to update the range if the popped element and the currentMaxNumber make a smaller range than rangeStart - rangeEnd.

In the following code, we apply this condition on lines 32 - 35.

The solution works because at every stage, we make sure that the minHeap contains one element each from each of the k input lists. The popped element, in each iteration, is the minimum of k values being considered, hence, it’s a valid candidate to become the lower boundary of the smallest range. Similarly, as we push the next larger number on to the heap, we check if it is greater than the largest number encountered so far. These two factors ensure the correctness of the condition on line 32.

Press + to interact
Python 3.5
from heapq import *
import math
def find_smallest_range(lists):
  print("Input lists:", lists)
  minHeap = []
  rangeStart, rangeEnd = 0, math.inf
  currentMaxNumber = -math.inf
  print("Inserting 1st element of each array in the minHeap")
  # put the 1st element of each array in the min heap
  for arr in lists:
    heappush(minHeap, (arr[0], 0, arr))
    print("minHeap: " + str(minHeap))
    currentMaxNumber = max(currentMaxNumber, arr[0])
    print("currentMaxNumber: " + str(currentMaxNumber))
  print("Set-up complete. About to start pop-and-push cycle:\n")
  iteration = 0;
  # take the smallest(top) element from the min heap, 
  # if it gives us a smaller range, update the range
  # if there are elements left in the array to which the top element belongs, 
  # push the next element from that array on to the heap
  while len(minHeap) == len(lists):
    print("\nIteration: "+str(iteration+1))
    iteration +=1
    print("\tminHeap: " + str(minHeap))
    num, i, arr = heappop(minHeap)
    print("\tnum, i, arr: "+str(num)+", "+str(i)+", "+str(arr))
    print("\tCurrent Range: " + str(rangeStart) + "-" + str(rangeEnd))
    print("\tcurrentMaxNumber: "+str(currentMaxNumber))
    if rangeEnd - rangeStart > currentMaxNumber - num:
      rangeStart = num
      rangeEnd = currentMaxNumber
      print("\t\tRange updated: "+str(rangeStart)+"-"+str(rangeEnd))
    if len(arr) > i+1:
      # insert the next element in the heap
      heappush(minHeap, (arr[i+1], i+1, arr))
      currentMaxNumber = max(currentMaxNumber, arr[i+1])
  return [rangeStart, rangeEnd]
def main():
  lists = [[[2, 3], [4,5], [6,7]],[[1, 2, 30], [9, 10,15], [7, 8, 10]]]
  for i in range(len(lists)):
    [rangeStart,rangeEnd] = find_smallest_range(lists[i])
    print("Smallest range in " + str(lists[i]) + " is: " + str(rangeStart) + "-" + str(rangeEnd))
    print("-"*100)
main()