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.


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[].


  • 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:


Smallest Range is: 2 from 1 To 3

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

1 Response

  1. jafar basha says:

    In this code we are using extra space O(n)
    Here is the simple solution in min(O(n),O(m),O(l)) and constant extra space

Leave a Reply to jafar basha Cancel reply

Your email address will not be published. Required fields are marked *

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

%d bloggers like this: